Online Charging and Routing of Electric Vehicles in Stochastic Time-Varying Networks

Abstract

This paper formulates the problem of online charging and routing of a single electric vehicle in a network with stochastic and time-varying travel times. Public charging stations, with nonidentical electricity prices and charging rates, exist through the network. Upon arrival at each node, the traveler learns the travel time on all downstream arcs and the waiting time at the charging station, if one is available. The traveler aims to minimize the expected generalized cost—formulated as a weighted sum of travel time and charging cost—by considering the current state of the vehicle and availability of information in the future. The paper also discusses an offline algorithm by which all routing and charging decisions are made a priori. The numerical results demonstrate that cost savings of the online policy, compared with that for the offline algorithm, is more significant in larger networks and that the number of charging stations and vehicle efficiency rate have a significant impact on those savings.

Get full access to this article

View all access options for this article.

References

Reinforcement Learning and Control. CS229, Machine Learning, Lecture Notes. Stanford University, Stanford, Calif., n.d. http://cs229.stanford.edu/notes/cs229-notes12.pdf. Accessed July 2016.

Hall

R. W.

The Fastest Path Through a Network with Random Time-Dependent Travel Times. Transportation Science, Vol. 20, No. 3, 1986, pp. 182–188. https://doi.org/10.1287/trsc.20.3.182.

Miller-Hooks

E. D.

, and Mahmassani

H. S.

. Least Possible Time Paths in Stochastic, Time-Varying Networks. Computers & Operations Research, Vol. 25, No. 12, 1998, pp. 1107–1125. https://doi.org/10.1016/S0305-0548(98)00027-6.

Miller-Hooks

E. D.

, and Mahmassani

H. S.

. Least Expected Time Paths in Stochastic, Time-Varying Transportation Networks. Transportation Science, Vol. 34, No. 2, 2000, pp. 198–215. https://doi.org/10.1287/trsc.34.2.198.12304.

Nie

Y. M.

, and Wu

. Shortest Path Problem Considering On-Time Arrival Probability. Transportation Research Part B: Methodological, Vol. 43, No. 6, 2009, pp. 597–613. https://doi.org/10.1016/j.trb.2009.01.008.

Nie

Y. M.

, and Wu

. Reliable a Priori Shortest Path Problem with Limited Spatial and Temporal Dependencies. In Transportation and Traffic Theory 2009: Golden Jubilee ( Lam

, Wong

, and Lo

, eds.), Springer, Boston, Mass., 2009, pp. 169–195. https://doi.org/10.1007/978-1-4419-0820-9_9.

Miller-Hooks

Adaptive Least-Expected Time Paths in Stochastic, Time-Varying Transportation and Data Networks. Networks, Vol. 37, No. 1, 2001, pp. 35–52. https://doi.org/10.1002/1097-0037(200101)37:1<35::AID-NET4>3.0.CO;2-G.

Provan

J. S.

A Polynomial-Time Algorithm to Find Shortest Paths with Recourse. Networks, Vol. 41, No. 2, 2003, pp. 115–125. https://doi.org/10.1002/net.10063.

Waller

S. T.

, and Ziliaskopoulos

A. K.

. On the Online Shortest Path Problem with Limited Arc Cost Dependencies. Networks, Vol. 40, No. 4, 2002, pp. 216–227. https://doi.org/10.1002/net.10049.

10.

Boyles

S. D.

, and Waller

S. T.

. Optimal Information Location for Adaptive Routing. Networks and Spatial Economics, Vol. 11, No. 2, 2011, pp. 233–254. https://doi.org/10.1007/s11067-009-9108-9.

11.

Agrawal

S. K.

, Boyles

S. D.

, Jiang

, Shahabi

, and Unnikrishnan

. Network Route Choice Model for Battery Electric Vehicle Drivers with Different Risk Attitudes. Transportation Research Record: Journal of the Transportation Research Board, No. 2498, 2015, pp. 75–83. https://doi.org/10.3141/2498-09.

12.

Bakker

J. K.

Contesting Range Anxiety: The Role of Electric Vehicle Charging Infrastructure in the Transportation Transition. Master’s thesis. Eindhoven University of Technology, Eindhoven, Netherlands, 2011.

13.

A. S. O.

, Silva

L. L. C.

, Chu

C. L.

, Nascimento

P. T. S.

, and Camargo

A. S.

, Electric Vehicles: Struggles in Creating a Market. 2011 Proceedings of PICMET ’11: Technology Management in the Energy Smart World (PICMET), IEEE, Portland, Ore., 2011, pp. 1–13.

14.

Huang

, Li

, and Qian

Z. S.

. Optimal Deployment of Alternative Fueling Stations on Transportation Networks Considering Deviation Paths. Networks and Spatial Economics, Vol. 15, No. 1, 2015, pp. 183–204. https://doi.org/10.1007/s11067-014-9275-1.

15.

, Huang

, and Mason

S. J.

. A Multi-Period Optimization Model for the Deployment of Public Electric Vehicle Charging Stations on Network. Transportation Research Part C: Emerging Technologies, Vol. 65, 2016, pp. 128–143. https://doi.org/10.1016/j.trc.2016.01.008.

16.

Ghamami

, Zockaie

, and Nie

Y. M.

. A General Corridor Model for Designing Plug-In Electric Vehicle Charging Infrastructure to Support Intercity Travel. Transportation Research Part C: Emerging Technologies, Vol. 68, 2016, pp. 389–402. https://doi.org/10.1016/j.trc.2016.04.016.

17.

Nie

Y. M.

, and Ghamami

. A Corridor-Centric Approach to Planning Electric Vehicle Charging Infrastructure. Transportation Research Part B: Methodological, Vol. 57, 2013, pp. 172–190. https://doi.org/10.1016/j.trb.2013.08.010.

18.

Jafari

, and Boyles

S. D.

. Multicriteria Stochastic Shortest Path Problem for Electric Vehicles. Networks and Spatial Economics, 2017.

19.

Sweda

T. M.

, and Klabjan

. Finding Minimum-Cost Paths for Electric Vehicles. Proceedings of the 2012 International Electric Vehicle Conference, IEEE, Greenville, S.C., pp. 1–4, 2012.

20.

Cassandras

C. G.

, Wang

, and Pourazarm

. Energy-Aware Vehicle Routing in Networks with Charging Nodes. 2014, https://arxiv.org/abs/1401.6478.

21.

Alizadeh

, Wai

H.-T.

, Cassandras

C. G.

, Scaglione

, Goldsmith

, Fan

Y. Y.

, and Javidi

. Optimized Path Planning for Electric Vehicle Routing and Charging. Proceedings of the 52nd Annual Allerton Conference on Communication, Control, and Computing, 2014, IEEE, University of Illinois at Urbana–Champaign, 2014, pp. 25–32. https://doi.org/10.1109/ALLERTON.2014.7028431.

22.

Sweda

T. M.

, Dolinskaya

I. S.

, and Klabjan

. Adaptive Routing and Recharging Policies for Electric Vehicles, Northwestern University, Evanston, Ill., 2014.

23.

Sweda

T. M.

, Dolinskaya

I. S.

, and Klabjan

. Optimal Recharging Policies for Electric Vehicles. Transportation Science, Vol. 51, No. 2, 2017, pp. 457–479.

24.

Korolko

, and Sahinoglu

, Robust Optimization of EV Charging Schedules in Unregulated Electricity Markets. Mitsubishi Electric Research Laboratories, Cambridge, Mass., 2015, pp. 1–9.

25.

Hansen

Bicriterion Path Problems. In Multiple Criteria Decision Making Theory and Application ( Fandel

and Gal

, eds.), Lecture Notes in Economics and Mathematical Systems, Vol. 177. Springer, Berlin, 1980, pp. 109–127. https://doi.org/10.1007/978-3-642-48782-8_9.

26.

Müller-Hannemann

, and Weihe

. On the Cardinality of the Pareto Set in Bicriteria Shortest Path Problems. Annals of Operations Research, Vol. 147, No. 1, 2006, pp. 269–286. https://doi.org/10.1007/s10479-006-0072-1.

27.

Reinhardt

L. B.

, and Pisinger

. Multi-Objective and Multi-Constrained Non-Additive Shortest Path Problems. Computers & Operations Research, Vol. 38, No. 3, 2011, pp. 605–616. https://doi.org/10.1016/j.cor.2010.08.003.