A bi-objective reliable path-finding algorithm for battery electric vehicle routing

Xiao Wei Chen, Bi Yu Chen, William H.K. Lam, Mei Lam Tam, Wei Ma

Research output: Journal article publicationJournal articleAcademic researchpeer-review

Abstract

This paper proposes a bi-objective reliable path-finding algorithm for routing battery electric vehicles on a road network, with vehicles’ energy consumption uncertainty and travel time uncertainty. A bi-objective stochastic optimization problem is proposed and formulated to simultaneously maximize energy consumption reliability (ECR) and travel time reliability (TTR). ECR is defined as the probability of finishing a trip without exhausting a given battery energy budget, while TTR is the on-time arrival probability with the travel time budget. In this study, the proposed optimization problem is decomposed into two sub-problems: (1) finding K most reliable paths for maximizing the TTR objective and (2) finding the most reliable path for optimizing the ECR objective. Then, a novel ranking algorithm is proposed to exactly solve the formulated optimization problem. A case study is carried out on Hong Kong's road network to demonstrate the efficacy and efficiency of the proposed algorithm for real-world applications.

Original languageEnglish
Article number115228
JournalExpert Systems with Applications
Volume182
DOIs
Publication statusPublished - 15 Nov 2021

Keywords

  • Bi-objective path finding
  • Energy consumption reliability
  • Network uncertainties
  • Travel time reliability

ASJC Scopus subject areas

  • Engineering(all)
  • Computer Science Applications
  • Artificial Intelligence

Cite this