IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v299y2022i2p526-541.html
   My bibliography  Save this article

Optimal routing for electric vehicle charging systems with stochastic demand: A heavy traffic approximation approach

Author

Listed:
  • Hung, Ying-Chao
  • PakHai Lok, Horace
  • Michailidis, George

Abstract

We consider a general electric vehicle (EV) charging system with stochastic demand, demand request locations, and predetermined charging facilities (including charging station locations and charger capacities). The objective is to design a good routing strategy that accommodates well demand-request dynamics so as to satisfy the charging system’s stability constraints and also minimize the EV’s mean response time. We introduce a class of flexible and measurement-based routing policies called “partition-based random routing” (PBRR) and show that the performance measure of interest can be formulated as a constrained optimization problem with a convex objective function when the system is heavily loaded. This formulation enables us to establish strong theoretical results that are in aid of finding the optimal routing solution; however, in practice, finding this solution requires rather involved numerical calculations. To that end, we propose a surrogate, easy to design and implement, optimization algorithm for finding the desired optimal routing solution. Numerical work based on synthetic data shows that the performance of the developed routing strategy and its fast implementation is highly satisfactory for a number of system settings.

Suggested Citation

  • Hung, Ying-Chao & PakHai Lok, Horace & Michailidis, George, 2022. "Optimal routing for electric vehicle charging systems with stochastic demand: A heavy traffic approximation approach," European Journal of Operational Research, Elsevier, vol. 299(2), pages 526-541.
    • Handle: RePEc:eee:ejores:v:299:y:2022:i:2:p:526-541
    DOI: 10.1016/j.ejor.2021.06.058
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221721005890
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2021.06.058?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Blanc, J.P.C., 2009. "Bad luck when joining the shortest queue," European Journal of Operational Research, Elsevier, vol. 195(1), pages 167-173, May.
    2. Angelos Aveklouris & Maria Vlasiou & Bert Zwart, 2019. "Bounds and limit theorems for a layered queueing model in electric vehicle charging," Queueing Systems: Theory and Applications, Springer, vol. 93(1), pages 83-137, October.
    3. Pillac, Victor & Gendreau, Michel & Guéret, Christelle & Medaglia, Andrés L., 2013. "A review of dynamic vehicle routing problems," European Journal of Operational Research, Elsevier, vol. 225(1), pages 1-11.
    4. Timothy M. Sweda & Irina S. Dolinskaya & Diego Klabjan, 2017. "Adaptive Routing and Recharging Policies for Electric Vehicles," Transportation Science, INFORMS, vol. 51(4), pages 1326-1348, November.
    5. Pelletier, Samuel & Jabali, Ola & Laporte, Gilbert, 2019. "The electric vehicle routing problem with energy consumption uncertainty," Transportation Research Part B: Methodological, Elsevier, vol. 126(C), pages 225-255.
    6. Søren Asmussen, 1992. "Queueing Simulation in Heavy Traffic," Mathematics of Operations Research, INFORMS, vol. 17(1), pages 84-111, February.
    7. Fengjie Fu & Hongzhao Dong, 2019. "Targeted optimal-path problem for electric vehicles with connected charging stations," PLOS ONE, Public Library of Science, vol. 14(8), pages 1-23, August.
    8. Changxi Ma & Wei Hao & Ruichun He & Xiaoyan Jia & Fuquan Pan & Jing Fan & Ruiqi Xiong, 2018. "Distribution path robust optimization of electric vehicle with multiple distribution centers," PLOS ONE, Public Library of Science, vol. 13(3), pages 1-16, March.
    9. J. Barco & A. Guerra & L. Muñoz & N. Quijano, 2017. "Optimal Routing and Scheduling of Charge for Electric Vehicles: A Case Study," Mathematical Problems in Engineering, Hindawi, vol. 2017, pages 1-16, November.
    10. Mark M. Nejad & Lena Mashayekhy & Daniel Grosu & Ratna Babu Chinnam, 2017. "Optimal Routing for Plug-In Hybrid Electric Vehicles," Transportation Science, INFORMS, vol. 51(4), pages 1304-1325, November.
    11. Ward Whitt & Xiaopei Zhang, 2019. "Periodic Little’s Law," Operations Research, INFORMS, vol. 67(1), pages 267-280, January.
    12. Maria-Simona Răboacă & Irina Băncescu & Vasile Preda & Nicu Bizon, 2020. "An Optimization Model for the Temporary Locations of Mobile Charging Stations," Mathematics, MDPI, vol. 8(3), pages 1-20, March.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Yan, Pengyu & Yu, Kaize & Chao, Xiuli & Chen, Zhibin, 2023. "An online reinforcement learning approach to charging and order-dispatching optimization for an e-hailing electric vehicle fleet," European Journal of Operational Research, Elsevier, vol. 310(3), pages 1218-1233.
    2. Pegah Alaee & Julius Bems & Amjad Anvari-Moghaddam, 2023. "A Review of the Latest Trends in Technical and Economic Aspects of EV Charging Management," Energies, MDPI, vol. 16(9), pages 1-28, April.
    3. Kinene, Alan & Birolini, Sebastian & Cattaneo, Mattia & Granberg, Tobias Andersson, 2023. "Electric aircraft charging network design for regional routes: A novel mathematical formulation and kernel search heuristic," European Journal of Operational Research, Elsevier, vol. 309(3), pages 1300-1315.
    4. Witt Andreas, 2023. "Determination of the Number of Required Charging Stations on a German Motorway Based on Real Traffic Data and Discrete Event-Based Simulation," LOGI – Scientific Journal on Transport and Logistics, Sciendo, vol. 14(1), pages 1-11, January.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Asghari, Mohammad & Mirzapour Al-e-hashem, S. Mohammad J., 2021. "Green vehicle routing problem: A state-of-the-art review," International Journal of Production Economics, Elsevier, vol. 231(C).
    2. Mohammad Asghari & Seyed Mohammad Javad Mirzapour Al-E-Hashem, 2021. "Green vehicle routing problem: A state-of-the-art review," Post-Print hal-03182944, HAL.
    3. Maximilian Schiffer & Michael Schneider & Grit Walther & Gilbert Laporte, 2019. "Vehicle Routing and Location Routing with Intermediate Stops: A Review," Transportation Science, INFORMS, vol. 53(2), pages 319-343, March.
    4. Yong Wang & Jingxin Zhou & Yaoyao Sun & Xiuwen Wang & Jiayi Zhe & Haizhong Wang, 2022. "Electric Vehicle Charging Station Location-Routing Problem with Time Windows and Resource Sharing," Sustainability, MDPI, vol. 14(18), pages 1-31, September.
    5. Raeesi, Ramin & Zografos, Konstantinos G., 2022. "Coordinated routing of electric commercial vehicles with intra-route recharging and en-route battery swapping," European Journal of Operational Research, Elsevier, vol. 301(1), pages 82-109.
    6. Azra Ghobadi & Mohammad Fallah & Reza Tavakkoli-Moghaddam & Hamed Kazemipoor, 2022. "A Fuzzy Two-Echelon Model to Optimize Energy Consumption in an Urban Logistics Network with Electric Vehicles," Sustainability, MDPI, vol. 14(21), pages 1-31, October.
    7. LIAN, Ying & LUCAS, Flavien & SÖRENSEN, Kenneth, 2022. "The electric on-demand bus routing problem with partial charging and nonlinear functions," Working Papers 2022005, University of Antwerp, Faculty of Business and Economics.
    8. Maximiliano Cubillos & Mauro Dell’Amico & Ola Jabali & Federico Malucelli & Emanuele Tresoldi, 2023. "An Enhanced Path Planner for Electric Vehicles Considering User-Defined Time Windows and Preferences," Energies, MDPI, vol. 16(10), pages 1-19, May.
    9. Basso, Rafael & Kulcsár, Balázs & Sanchez-Diaz, Ivan & Qu, Xiaobo, 2022. "Dynamic stochastic electric vehicle routing with safe reinforcement learning," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 157(C).
    10. Nicholas D. Kullman & Justin C. Goodson & Jorge E. Mendoza, 2021. "Electric Vehicle Routing with Public Charging Stations," Transportation Science, INFORMS, vol. 55(3), pages 637-659, May.
    11. Reyes, Damián & Erera, Alan L. & Savelsbergh, Martin W.P., 2018. "Complexity of routing problems with release dates and deadlines," European Journal of Operational Research, Elsevier, vol. 266(1), pages 29-34.
    12. Ghotge, Rishabh & van Wijk, Ad & Lukszo, Zofia, 2021. "Off-grid solar charging of electric vehicles at long-term parking locations," Energy, Elsevier, vol. 227(C).
    13. Nicolas Rincon-Garcia & Ben J. Waterson & Tom J. Cherrett, 2018. "Requirements from vehicle routing software: perspectives from literature, developers and the freight industry," Transport Reviews, Taylor & Francis Journals, vol. 38(1), pages 117-138, January.
    14. Dessouky, Maged M & Hu, Shichun, 2021. "Dynamic Routing for Ride-Sharing," Institute of Transportation Studies, Working Paper Series qt6qq8r7hz, Institute of Transportation Studies, UC Davis.
    15. LIAN, Ying & LUCAS, Flavien & SÖRENSEN, Kenneth, 2022. "On-demand bus routing problem with dynamic stochastic requests and prepositioning," Working Papers 2022004, University of Antwerp, Faculty of Business and Economics.
    16. Mathias A. Klapp & Alan L. Erera & Alejandro Toriello, 2018. "The One-Dimensional Dynamic Dispatch Waves Problem," Transportation Science, INFORMS, vol. 52(2), pages 402-415, March.
    17. Sun, Hao & Yang, Jun & Yang, Chao, 2019. "A robust optimization approach to multi-interval location-inventory and recharging planning for electric vehicles," Omega, Elsevier, vol. 86(C), pages 59-75.
    18. Marlin W. Ulmer & Alan Erera & Martin Savelsbergh, 2022. "Dynamic service area sizing in urban delivery," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 44(3), pages 763-793, September.
    19. Feng, Zhanyu & Zhang, Jian & Jiang, Han & Yao, Xuejian & Qian, Yu & Zhang, Haiyan, 2024. "Energy consumption prediction strategy for electric vehicle based on LSTM-transformer framework," Energy, Elsevier, vol. 302(C).
    20. Zhang, Huili & Tong, Weitian & Xu, Yinfeng & Lin, Guohui, 2015. "The Steiner Traveling Salesman Problem with online edge blockages," European Journal of Operational Research, Elsevier, vol. 243(1), pages 30-40.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:ejores:v:299:y:2022:i:2:p:526-541. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.