TY - JOUR
T1 - Stochastic Optimal Path Problem with Relays
AU - Chen, Peng
AU - Nie, Yu
N1 - Funding Information:
The idea of using the location of Nissan dealers to construct a case study for the Chicago area is credited to Professor David Boyce at Northwestern University. The authors wish to thank his enthusiasm for electric vehicles, which is one of the motivating forces behind this work. Institute for Energy and Sustainability at Northwestern (ISEN) had partially funded a related research project in the year of 2014. The errors are the authors’ alone.
Publisher Copyright:
© 2015 The Authors. © 2015 The Authors. Published by Elsevier B.V.
PY - 2015
Y1 - 2015
N2 - This paper studies the optimal path problem for travelers driving with vehicles of a limited range, such as most battery electric vehicles currently available in the market. The optimal path in this problem often consists of several relay points, where the vehicles can be refueled to extend its range. We propose a stochastic optimal path problem with relays (SOPPR), which aims at minimizing a general expected cost while maintaining a reasonable arrival probability. To account for uncertainty in the road network, the travel speed on a road segment is treated as a discrete random variable, which determines the total energy required to traverse the segment. SOPPR is formulated in two stages in this paper. In the first stage, an optimal routing problem is solved repeatedly to obtain the expected costs and arrival probabilities from any node to all refueling nodes and the destination. With this information, the second stage constructs an auxiliary network, on which the sequence of refueling decisions can be obtained by solving another optimal path problem. Label-correcting algorithms are developed to solve the routing problems in both stages. Numerical experiments are conducted to compare the stochastic and deterministic models, to examine the impact of different parameters on the routing results, and to evaluate the computational performance of the proposed algorithms.
AB - This paper studies the optimal path problem for travelers driving with vehicles of a limited range, such as most battery electric vehicles currently available in the market. The optimal path in this problem often consists of several relay points, where the vehicles can be refueled to extend its range. We propose a stochastic optimal path problem with relays (SOPPR), which aims at minimizing a general expected cost while maintaining a reasonable arrival probability. To account for uncertainty in the road network, the travel speed on a road segment is treated as a discrete random variable, which determines the total energy required to traverse the segment. SOPPR is formulated in two stages in this paper. In the first stage, an optimal routing problem is solved repeatedly to obtain the expected costs and arrival probabilities from any node to all refueling nodes and the destination. With this information, the second stage constructs an auxiliary network, on which the sequence of refueling decisions can be obtained by solving another optimal path problem. Label-correcting algorithms are developed to solve the routing problems in both stages. Numerical experiments are conducted to compare the stochastic and deterministic models, to examine the impact of different parameters on the routing results, and to evaluate the computational performance of the proposed algorithms.
KW - arrival probability
KW - label-correcting algorithm
KW - relays
KW - stochastic optimal path
UR - http://www.scopus.com/inward/record.url?scp=84959361106&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84959361106&partnerID=8YFLogxK
U2 - 10.1016/j.trpro.2015.06.008
DO - 10.1016/j.trpro.2015.06.008
M3 - Article
AN - SCOPUS:84959361106
SN - 2352-1457
VL - 7
SP - 129
EP - 148
JO - Transportation Research Procedia
JF - Transportation Research Procedia
ER -