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

An exact algorithm for maximum electric vehicle flow coverage problem with heterogeneous chargers, nonlinear charging time and route deviations

Author

Listed:
  • Park, Hyunwoo
  • Lee, Chungmok

Abstract

Typical electric vehicles (EVs) should be recharged multiple times to reach a long distance due to the limited travel ranges. The EV flow covering problem determines the locations of charging stations to maximize the “covered” OD flows, respecting a given budget for the new charging stations. This paper proposes an exact algorithm for solving the problem by considering the heterogeneous EV chargers, nonlinear charging time, and route deviations from the shortest distance paths. We develop an exact Benders decomposition-based algorithm, in which the Benders subproblem utilizes a nested cut-generation via a customized labeling algorithm. Two methods for solving the Benders subproblem are developed, which are combined to accelerate the Benders cut generation. In addition, we present a heuristic algorithm based on the proposed exact algorithm for the larger-sized problems. The computational results show that the proposed algorithm could solve real-life problems. Especially, the heuristic algorithm could solve problems up to 339 nodes and 500 km of the EV’s travel range. The extensive computational study shows that addressing the multiple charger types, the charging time, and the deviation routes can be crucial to provide realistic charging infrastructure for EVs.

Suggested Citation

  • Park, Hyunwoo & Lee, Chungmok, 2024. "An exact algorithm for maximum electric vehicle flow coverage problem with heterogeneous chargers, nonlinear charging time and route deviations," European Journal of Operational Research, Elsevier, vol. 315(3), pages 926-951.
    • Handle: RePEc:eee:ejores:v:315:y:2024:i:3:p:926-951
    DOI: 10.1016/j.ejor.2023.12.019
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221723009529
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2023.12.019?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. Nicholas D. Kullman & Aurelien Froger & Jorge E. Mendoza & Justin C. Goodson, 2021. "frvcpy: An Open-Source Solver for the Fixed Route Vehicle Charging Problem," INFORMS Journal on Computing, INFORMS, vol. 33(4), pages 1277-1283, October.
    2. Timothy M. Sweda & Irina S. Dolinskaya & Diego Klabjan, 2017. "Optimal Recharging Policies for Electric Vehicles," Transportation Science, INFORMS, vol. 51(2), pages 457-479, May.
    3. Arslan, Okan & Karaşan, Oya Ekin, 2016. "A Benders decomposition approach for the charging station location problem with plug-in hybrid electric vehicles," Transportation Research Part B: Methodological, Elsevier, vol. 93(PA), pages 670-695.
    4. Wang, Ying-Wei & Wang, Chuan-Ren, 2010. "Locating passenger vehicle refueling stations," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 46(5), pages 791-801, September.
    5. S. A. MirHassani & R. Ebrazi, 2013. "A Flexible Reformulation of the Refueling Station Location Problem," Transportation Science, INFORMS, vol. 47(4), pages 617-628, November.
    6. Hof, Julian & Schneider, Michael & Goeke, Dominik, 2017. "Solving the battery swap station location-routing problem with capacitated electric vehicles using an AVNS algorithm for vehicle-routing problems with intermediate stops," Transportation Research Part B: Methodological, Elsevier, vol. 97(C), pages 102-112.
    7. Chung, Sung Hoon & Kwon, Changhyun, 2015. "Multi-period planning for electric car charging station locations: A case of Korean Expressways," European Journal of Operational Research, Elsevier, vol. 242(2), pages 677-687.
    8. He, Fang & Yin, Yafeng & Lawphongpanich, Siriphong, 2014. "Network equilibrium models with battery electric vehicles," Transportation Research Part B: Methodological, Elsevier, vol. 67(C), pages 306-319.
    9. Cavadas, Joana & Homem de Almeida Correia, Gonçalo & Gouveia, João, 2015. "A MIP model for locating slow-charging stations for electric vehicles in urban areas accounting for driver tours," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 75(C), pages 188-201.
    10. Shaohua Cui & Hui Zhao & Huijie Wen & Cuiping Zhang, 2018. "Locating Multiple Size and Multiple Type of Charging Station for Battery Electricity Vehicles," Sustainability, MDPI, vol. 10(9), pages 1-20, September.
    11. Schiffer, Maximilian & Walther, Grit, 2017. "The electric location routing problem with time windows and partial recharging," European Journal of Operational Research, Elsevier, vol. 260(3), pages 995-1013.
    12. Yıldız, Barış & Arslan, Okan & Karaşan, Oya Ekin, 2016. "A branch and price approach for routing and refueling station location model," European Journal of Operational Research, Elsevier, vol. 248(3), pages 815-826.
    13. Xu Ouyang & Min Xu & Bojian Zhou, 2022. "An Elastic Demand Model for Locating Electric Vehicle Charging Stations," Networks and Spatial Economics, Springer, vol. 22(1), pages 1-31, March.
    14. Lee, Chungmok & Han, Jinil, 2017. "Benders-and-Price approach for electric vehicle charging station location problem under probabilistic travel range," Transportation Research Part B: Methodological, Elsevier, vol. 106(C), pages 130-152.
    15. Erdoğan, Sevgi & Miller-Hooks, Elise, 2012. "A Green Vehicle Routing Problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 48(1), pages 100-114.
    16. 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.
    17. Kınay, Ömer Burak & Gzara, Fatma & Alumur, Sibel A., 2021. "Full cover charging station location problem with routing," Transportation Research Part B: Methodological, Elsevier, vol. 144(C), pages 1-22.
    18. Wang, Ying-Wei & Lin, Chuah-Chih, 2013. "Locating multiple types of recharging stations for battery-powered electric vehicle transport," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 58(C), pages 76-87.
    19. Montoya, Alejandro & Guéret, Christelle & Mendoza, Jorge E. & Villegas, Juan G., 2017. "The electric vehicle routing problem with nonlinear charging function," Transportation Research Part B: Methodological, Elsevier, vol. 103(C), pages 87-110.
    20. Kuby, Michael & Lim, Seow, 2005. "The flow-refueling location problem for alternative-fuel vehicles," Socio-Economic Planning Sciences, Elsevier, vol. 39(2), pages 125-145, June.
    21. Ismail Capar & Michael Kuby, 2012. "An efficient formulation of the flow refueling location model for alternative-fuel stations," IISE Transactions, Taylor & Francis Journals, vol. 44(8), pages 622-636.
    22. Rahmaniani, Ragheb & Crainic, Teodor Gabriel & Gendreau, Michel & Rei, Walter, 2017. "The Benders decomposition algorithm: A literature review," European Journal of Operational Research, Elsevier, vol. 259(3), pages 801-817.
    23. Derya Celik Turkoglu & Mujde Erol Genevois, 2020. "A comparative survey of service facility location problems," Annals of Operations Research, Springer, vol. 292(1), pages 399-468, September.
    24. Nie, Yu (Marco) & Ghamami, Mehrnaz & Zockaie, Ali & Xiao, Feng, 2016. "Optimization of incentive polices for plug-in electric vehicles," Transportation Research Part B: Methodological, Elsevier, vol. 84(C), pages 103-123.
    25. David Simchi-Levi & Oded Berman, 1988. "A Heuristic Algorithm for the Traveling Salesman Location Problem on Networks," Operations Research, INFORMS, vol. 36(3), pages 478-484, June.
    26. Georg Brandstätter & Markus Leitner & Ivana Ljubić, 2020. "Location of Charging Stations in Electric Car Sharing Systems," Transportation Science, INFORMS, vol. 54(5), pages 1408-1438, September.
    Full references (including those not matched with items on IDEAS)

    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. Kınay, Ömer Burak & Gzara, Fatma & Alumur, Sibel A., 2021. "Full cover charging station location problem with routing," Transportation Research Part B: Methodological, Elsevier, vol. 144(C), pages 1-22.
    2. Zhang, Anpeng & Kang, Jee Eun & Kwon, Changhyun, 2017. "Incorporating demand dynamics in multi-period capacitated fast-charging location planning for electric vehicles," Transportation Research Part B: Methodological, Elsevier, vol. 103(C), pages 5-29.
    3. Lee, Chungmok & Han, Jinil, 2017. "Benders-and-Price approach for electric vehicle charging station location problem under probabilistic travel range," Transportation Research Part B: Methodological, Elsevier, vol. 106(C), pages 130-152.
    4. Shen, Zuo-Jun Max & Feng, Bo & Mao, Chao & Ran, Lun, 2019. "Optimization models for electric vehicle service operations: A literature review," Transportation Research Part B: Methodological, Elsevier, vol. 128(C), pages 462-477.
    5. Arslan, Okan & Karaşan, Oya Ekin, 2016. "A Benders decomposition approach for the charging station location problem with plug-in hybrid electric vehicles," Transportation Research Part B: Methodological, Elsevier, vol. 93(PA), pages 670-695.
    6. Mahmutoğulları, Özlem & Yaman, Hande, 2023. "Robust alternative fuel refueling station location problem with routing under decision-dependent flow uncertainty," European Journal of Operational Research, Elsevier, vol. 306(1), pages 173-188.
    7. Joonho Ko & Tae-Hyoung Tommy Gim & Randall Guensler, 2017. "Locating refuelling stations for alternative fuel vehicles: a review on models and applications," Transport Reviews, Taylor & Francis Journals, vol. 37(5), pages 551-570, September.
    8. Shaohua Cui & Hui Zhao & Cuiping Zhang, 2018. "Multiple Types of Plug-In Charging Facilities’ Location-Routing Problem with Time Windows for Mobile Charging Vehicles," Sustainability, MDPI, vol. 10(8), pages 1-26, August.
    9. Shaohua Cui & Hui Zhao & Cuiping Zhang, 2018. "Locating Charging Stations of Various Sizes with Different Numbers of Chargers for Battery Electric Vehicles," Energies, MDPI, vol. 11(11), pages 1-22, November.
    10. Anjos, Miguel F. & Gendron, Bernard & Joyce-Moniz, Martim, 2020. "Increasing electric vehicle adoption through the optimal deployment of fast-charging stations for local and long-distance travel," European Journal of Operational Research, Elsevier, vol. 285(1), pages 263-278.
    11. Yıldız, Barış & Arslan, Okan & Karaşan, Oya Ekin, 2016. "A branch and price approach for routing and refueling station location model," European Journal of Operational Research, Elsevier, vol. 248(3), pages 815-826.
    12. Yang, Jun & Guo, Fang & Zhang, Min, 2017. "Optimal planning of swapping/charging station network with customer satisfaction," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 103(C), pages 174-197.
    13. Wang, Mengtong & Miao, Lixin & Zhang, Canrong, 2021. "A branch-and-price algorithm for a green location routing problem with multi-type charging infrastructure," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 156(C).
    14. Schiffer, Maximilian & Walther, Grit, 2017. "The electric location routing problem with time windows and partial recharging," European Journal of Operational Research, Elsevier, vol. 260(3), pages 995-1013.
    15. Göpfert, Paul & Bock, Stefan, 2019. "A Branch&Cut approach to recharging and refueling infrastructure planning," European Journal of Operational Research, Elsevier, vol. 279(3), pages 808-823.
    16. Van Can Nguyen & Chi-Tai Wang & Ying-Jiun Hsieh, 2021. "Electrification of Highway Transportation with Solar and Wind Energy," Sustainability, MDPI, vol. 13(10), pages 1-28, May.
    17. Li, Lei & Al Chami, Zaher & Manier, Hervé & Manier, Marie-Ange & Xue, Jian, 2021. "Incorporating fuel delivery in network design for hydrogen fueling stations: Formulation and two metaheuristic approaches," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 152(C).
    18. 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.
    19. Hosseini, Meysam & MirHassani, S.A., 2015. "Refueling-station location problem under uncertainty," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 84(C), pages 101-116.
    20. Yıldız, Barış & Olcaytu, Evren & Şen, Ahmet, 2019. "The urban recharging infrastructure design problem with stochastic demands and capacitated charging stations," Transportation Research Part B: Methodological, Elsevier, vol. 119(C), pages 22-44.

    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:315:y:2024:i:3:p:926-951. 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.