IDEAS home Printed from https://ideas.repec.org/a/taf/tprsxx/v55y2017i2p519-535.html
   My bibliography  Save this article

Electric vehicle scheduling and optimal charging problem: complexity, exact and heuristic approaches

Author

Listed:
  • Ons Sassi
  • Ammar Oulamara

Abstract

This paper deals with the Electric Vehicle (EV) Scheduling and Optimal Charging Problem. More precisely, given a fleet of EVs and Combustion Engine Vehicles (CVs), a set of tours to be processed by vehicles and a charging infrastructure, the problem aims to optimise the assignment of vehicles to tours and minimise the charging cost of EVs while considering several operational constraints mainly related to chargers, electricity grid and EVs driving range. We prove that the Electric Vehicle Scheduling and Charging Problem (EVSCP) is NP-hard in the ordinary sense. We provide a mixed-integer linear programming formulation to model the EVSCP and use CPLEX to solve small and medium instances. To solve large instances, we propose two heuristics: a Sequential Heuristic (SH) and a Global Heuristic (GH). The SH considers the EVs sequentially. To each EV, it assigns a set of tours and guarantees the feasibility of a charging schedule. Then, it generates an optimal charging schedule for this EV. However, the GH computes, in the first step, a feasible assignment of tours to all EVs. In the second step, it applies a global Min-Cost-Flow-based charging algorithm to minimise the charging cost of the EVs fleet. To evaluate the efficiency of our solving approaches, computational results on a large set of real and randomly generated test instances are reported and compared.

Suggested Citation

  • Ons Sassi & Ammar Oulamara, 2017. "Electric vehicle scheduling and optimal charging problem: complexity, exact and heuristic approaches," International Journal of Production Research, Taylor & Francis Journals, vol. 55(2), pages 519-535, January.
    • Handle: RePEc:taf:tprsxx:v:55:y:2017:i:2:p:519-535
    DOI: 10.1080/00207543.2016.1192695
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1080/00207543.2016.1192695
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1080/00207543.2016.1192695?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. He, Fang & Wu, Di & Yin, Yafeng & Guan, Yongpei, 2013. "Optimal deployment of public charging stations for plug-in hybrid electric vehicles," Transportation Research Part B: Methodological, Elsevier, vol. 47(C), pages 87-101.
    2. Balachandran Vaidyanathan & Ravindra K. Ahuja, 2010. "Fast Algorithms for Specially Structured Minimum Cost Flow Problems with Applications," Operations Research, INFORMS, vol. 58(6), pages 1681-1696, December.
    3. 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.
    4. James B. Orlin, 1993. "A Faster Strongly Polynomial Minimum Cost Flow Algorithm," Operations Research, INFORMS, vol. 41(2), pages 338-350, April.
    5. Zeyu Chen & Rui Xiong & Kunyu Wang & Bin Jiao, 2015. "Optimal Energy Management Strategy of a Plug-in Hybrid Electric Vehicle Based on a Particle Swarm Optimization Algorithm," Energies, MDPI, vol. 8(5), pages 1-18, April.
    6. Kovalyov, Mikhail Y. & Ng, C.T. & Cheng, T.C. Edwin, 2007. "Fixed interval scheduling: Models, applications, computational complexity and algorithms," European Journal of Operational Research, Elsevier, vol. 178(2), pages 331-342, April.
    7. Antoon W.J. Kolen & Jan Karel Lenstra & Christos H. Papadimitriou & Frits C.R. Spieksma, 2007. "Interval scheduling: A survey," Naval Research Logistics (NRL), John Wiley & Sons, vol. 54(5), pages 530-543, August.
    8. Michael Schneider & Andreas Stenger & Dominik Goeke, 2014. "The Electric Vehicle-Routing Problem with Time Windows and Recharging Stations," Transportation Science, INFORMS, vol. 48(4), pages 500-520, November.
    9. Felipe, Ángel & Ortuño, M. Teresa & Righini, Giovanni & Tirado, Gregorio, 2014. "A heuristic approach for the green vehicle routing problem with multiple technologies and partial recharges," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 71(C), pages 111-128.
    10. Pol Olivella-Rosell & Roberto Villafafila-Robles & Andreas Sumper & Joan Bergas-Jané, 2015. "Probabilistic Agent-Based Model of Electric Vehicle Charging Demand to Analyse the Impact on Distribution Networks," Energies, MDPI, vol. 8(5), pages 1-28, May.
    11. Schneider, M. & Stenger, A. & Goeke, D., 2014. "The Electric Vehicle Routing Problem with Time Windows and Recharging Stations," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 62382, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    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. Xiaolin Chu & Yuntian Ge & Xue Zhou & Lin Li & Dong Yang, 2020. "Modeling and Analysis of Electric Vehicle-Power Grid-Manufacturing Facility (EPM) Energy Sharing System under Time-of-Use Electricity Tariff," Sustainability, MDPI, vol. 12(12), pages 1-27, June.
    2. 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.
    3. Héricles Eduardo Oliveira Farias & Camilo Alberto Sepulveda Rangel & Leonardo Weber Stringini & Luciane Neves Canha & Daniel Pegoraro Bertineti & Wagner da Silva Brignol & Zeno Iensen Nadal, 2021. "Combined Framework with Heuristic Programming and Rule-Based Strategies for Scheduling and Real Time Operation in Electric Vehicle Charging Stations," Energies, MDPI, vol. 14(5), pages 1-27, March.
    4. Diefenbach, Heiko & Emde, Simon & Glock, Christoph H., 2023. "Multi-depot electric vehicle scheduling in in-plant production logistics considering non-linear charging models," European Journal of Operational Research, Elsevier, vol. 306(2), pages 828-848.
    5. Matina L. Y. Chau & Diamanto Koutsompina & Konstantinos Gkiotsalitis, 2024. "The Electric Vehicle Scheduling Problem for Buses in Networks with Multi-Port Charging Stations," Sustainability, MDPI, vol. 16(3), pages 1-21, February.
    6. Zhou, Kaile & Cheng, Lexin & Wen, Lulu & Lu, Xinhui & Ding, Tao, 2020. "A coordinated charging scheduling method for electric vehicles considering different charging demands," Energy, Elsevier, vol. 213(C).
    7. M. E. Kooten Niekerk & J. M. Akker & J. A. Hoogeveen, 2017. "Scheduling electric vehicles," Public Transport, Springer, vol. 9(1), pages 155-176, July.
    8. Qingguang Zhang & Mubasher Ikram & Kun Xu, 2024. "Online Optimization of Vehicle-to-Grid Scheduling to Mitigate Battery Aging," Energies, MDPI, vol. 17(7), pages 1-14, April.
    9. Kazemi, Ahmad & Ernst, Andreas T. & Krishnamoorthy, Mohan & Le Bodic, Pierre, 2021. "Locomotive fuel management with inline refueling," European Journal of Operational Research, Elsevier, vol. 293(3), pages 1077-1096.
    10. Havre, Håkon Furnes & Lien, Ulrik & Ness, Mattias Myklebust & Fagerholt, Kjetil & Rødseth, Kenneth Løvold, 2024. "Network design with route planning for battery electric high-speed passenger vessel services," European Journal of Operational Research, Elsevier, vol. 315(1), pages 102-119.

    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. Goeke, Dominik & Schneider, Michael, 2015. "Routing a mixed fleet of electric and conventional vehicles," European Journal of Operational Research, Elsevier, vol. 245(1), pages 81-99.
    2. Masmoudi, Mohamed Amine & Hosny, Manar & Demir, Emrah & Genikomsakis, Konstantinos N. & Cheikhrouhou, Naoufel, 2018. "The dial-a-ride problem with electric vehicles and battery swapping stations," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 118(C), pages 392-420.
    3. Arslan, Okan & Yıldız, Barış & Karaşan, Oya Ekin, 2015. "Minimum cost path problem for Plug-in Hybrid Electric Vehicles," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 80(C), pages 123-141.
    4. Goeke, D. & Schneider, M., 2015. "Routing a Mixed Fleet of Electric and Conventional Vehicles," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 65939, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    5. Yan, Jianghui & Tseng, Fang-Mei & Lu, Louis Y.Y., 2018. "Developmental trajectories of new energy vehicle research in economic management: Main path analysis," Technological Forecasting and Social Change, Elsevier, vol. 137(C), pages 168-181.
    6. Diefenbach, Heiko & Emde, Simon & Glock, Christoph H., 2023. "Multi-depot electric vehicle scheduling in in-plant production logistics considering non-linear charging models," European Journal of Operational Research, Elsevier, vol. 306(2), pages 828-848.
    7. 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.
    8. Çalık, Hatice & Fortz, Bernard, 2019. "A Benders decomposition method for locating stations in a one-way electric car sharing system under demand uncertainty," Transportation Research Part B: Methodological, Elsevier, vol. 125(C), pages 121-150.
    9. Leggieri, Valeria & Haouari, Mohamed, 2017. "A practical solution approach for the green vehicle routing problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 104(C), pages 97-112.
    10. Cen, Xuekai & Lo, Hong K. & Li, Lu & Lee, Enoch, 2018. "Modeling electric vehicles adoption for urban commute trips," Transportation Research Part B: Methodological, Elsevier, vol. 117(PA), pages 431-454.
    11. 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.
    12. Roel M. Post & Paul Buijs & Michiel A. J. uit het Broek & Jose A. Lopez Alvarez & Nick B. Szirbik & Iris F. A. Vis, 2018. "A solution approach for deriving alternative fuel station infrastructure requirements," Flexible Services and Manufacturing Journal, Springer, vol. 30(3), pages 592-607, September.
    13. Roberti, R. & Wen, M., 2016. "The Electric Traveling Salesman Problem with Time Windows," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 89(C), pages 32-52.
    14. Su, Yue & Dupin, Nicolas & Parragh, Sophie N. & Puchinger, Jakob, 2024. "A Branch-and-Price algorithm for the electric autonomous Dial-A-Ride Problem," Transportation Research Part B: Methodological, Elsevier, vol. 186(C).
    15. 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.
    16. Raeesi, Ramin & Zografos, Konstantinos G., 2020. "The electric vehicle routing problem with time windows and synchronised mobile battery swapping," Transportation Research Part B: Methodological, Elsevier, vol. 140(C), pages 101-129.
    17. Cortés-Murcia, David L. & Prodhon, Caroline & Murat Afsar, H., 2019. "The electric vehicle routing problem with time windows, partial recharges and satellite customers," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 130(C), pages 184-206.
    18. Alberto Ceselli & Ángel Felipe & M. Teresa Ortuño & Giovanni Righini & Gregorio Tirado, 2021. "A Branch-and-Cut-and-Price Algorithm for the Electric Vehicle Routing Problem with Multiple Technologies," SN Operations Research Forum, Springer, vol. 2(1), pages 1-33, March.
    19. 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.
    20. 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.

    More about this item

    Statistics

    Access and download statistics

    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:taf:tprsxx:v:55:y:2017:i:2:p:519-535. 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: Chris Longhurst (email available below). General contact details of provider: http://www.tandfonline.com/TPRS20 .

    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.