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 -