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

doi:10.1016/j.eswa.2021.115228

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 publication › Journal article › Academic research › peer-review

16 Citations (Scopus)

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 language	English
Article number	115228
Journal	Expert Systems with Applications
Volume	182
DOIs	https://doi.org/10.1016/j.eswa.2021.115228
Publication status	Published - 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

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

More information

10.1016/j.eswa.2021.115228

http://hdl.handle.net/10397/95448

Cite this

@article{a2fbae46ae79403c89b98d92aaab8ae5,

title = "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{\textquoteright} 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.",

keywords = "Bi-objective path finding, Energy consumption reliability, Network uncertainties, Travel time reliability",

author = "Chen, {Xiao Wei} and Chen, {Bi Yu} and Lam, {William H.K.} and Tam, {Mei Lam} and Wei Ma",

note = "Funding Information: The work described in this paper was jointly supported by the National Key Research and Development Program (No. 2017YFB0503600), the Research Grants Council of the Hong Kong Special Administrative Region, China (Project No. PolyU R5029-18), the Dean's Reserve of the Hong Kong Polytechnic University (Project No. 1-ZVSA) and the Natural Science Foundation of Hubei Province (2020CFA054). Publisher Copyright: {\textcopyright} 2021 Elsevier Ltd",

year = "2021",

month = nov,

day = "15",

doi = "10.1016/j.eswa.2021.115228",

language = "English",

volume = "182",

journal = "Expert Systems with Applications",

issn = "0957-4174",

publisher = "Elsevier Ltd",

}

TY - JOUR

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

AU - Chen, Xiao Wei

AU - Chen, Bi Yu

AU - Lam, William H.K.

AU - Tam, Mei Lam

AU - Ma, Wei

N1 - Funding Information: The work described in this paper was jointly supported by the National Key Research and Development Program (No. 2017YFB0503600), the Research Grants Council of the Hong Kong Special Administrative Region, China (Project No. PolyU R5029-18), the Dean's Reserve of the Hong Kong Polytechnic University (Project No. 1-ZVSA) and the Natural Science Foundation of Hubei Province (2020CFA054). Publisher Copyright: © 2021 Elsevier Ltd

PY - 2021/11/15

Y1 - 2021/11/15

N2 - 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.

AB - 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.

KW - Bi-objective path finding

KW - Energy consumption reliability

KW - Network uncertainties

KW - Travel time reliability

UR - http://www.scopus.com/inward/record.url?scp=85106465326&partnerID=8YFLogxK

U2 - 10.1016/j.eswa.2021.115228

DO - 10.1016/j.eswa.2021.115228

M3 - Journal article

AN - SCOPUS:85106465326

SN - 0957-4174

VL - 182

JO - Expert Systems with Applications

JF - Expert Systems with Applications

M1 - 115228

ER -

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

Abstract

Keywords

ASJC Scopus subject areas

UN SDGs

More information

Other files and links

Fingerprint

Cite this