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

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.