IDEAS home Printed from https://ideas.repec.org/a/eee/transe/v167y2022ics1366554522002940.html
   My bibliography  Save this article

The mixed fleet vehicle routing problem with partial recharging by multiple chargers: Mathematical model and adaptive large neighborhood search

Author

Listed:
  • Dönmez, Sercan
  • Koç, Çağrı
  • Altıparmak, Fulya

Abstract

We introduce the Mixed Fleet Vehicle Routing Problem with Time Windows and Partial Recharging by Multiple Chargers (MF-VRP-MC). It composes of electric and internal combustion vehicles, and consolidates several aspects in a comprehensive unique model. The MF-VRP-MC considers travelled distance and carried load on vehicles in both emission and energy consumption functions. It deals with the minimization of total cost while satisfying customer delivery demands. First, we develop a mixed integer mathematical programming formulation for the MF-VRP-MC. Because of the NP-hardness of the problem, to solve medium and large-size instances, then we develop an Adaptive Large Neighborhood Search (ALNS) based algorithm with introducing new advanced neighborhood mechanisms to successfully handle complex problem constraints. Meantime, new approaches are tailored for boosting diversification effect in addition to new neighborhood scoring policy and new enhancement procedure. Furthermore, selection of recharging technology among the others at charging station is firstly considered in the solution phase of a mixed fleet problem. Extensive computational results indicate that our ALNS performs quite well on benchmark instances.

Suggested Citation

  • Dönmez, Sercan & Koç, Çağrı & Altıparmak, Fulya, 2022. "The mixed fleet vehicle routing problem with partial recharging by multiple chargers: Mathematical model and adaptive large neighborhood search," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 167(C).
    • Handle: RePEc:eee:transe:v:167:y:2022:i:c:s1366554522002940
    DOI: 10.1016/j.tre.2022.102917
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S1366554522002940
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.tre.2022.102917?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. Emna Marrekchi & Walid Besbes & Diala Dhouib & Emrah Demir, 2021. "A review of recent advances in the operations research literature on the green routing problem and its variants," Annals of Operations Research, Springer, vol. 304(1), pages 529-574, September.
    2. Stefan Ropke & David Pisinger, 2006. "An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows," Transportation Science, INFORMS, vol. 40(4), pages 455-472, November.
    3. Xiao, Yiyong & Zhang, Yue & Kaku, Ikou & Kang, Rui & Pan, Xing, 2021. "Electric vehicle routing problem: A systematic review and a new comprehensive model with nonlinear energy recharging and consumption," Renewable and Sustainable Energy Reviews, Elsevier, vol. 151(C).
    4. 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.
    5. Arslan, Okan, 2021. "The location-or-routing problem," Transportation Research Part B: Methodological, Elsevier, vol. 147(C), pages 1-21.
    6. Erfan Ghorbani & Mahdi Alinaghian & Gevork. B. Gharehpetian & Sajad Mohammadi & Guido Perboli, 2020. "A Survey on Environmentally Friendly Vehicle Routing Problem and a Proposal of Its Classification," Sustainability, MDPI, vol. 12(21), pages 1-71, October.
    7. Sadati, Mir Ehsan Hesam & Çatay, Bülent, 2021. "A hybrid variable neighborhood search approach for the multi-depot green vehicle routing problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 149(C).
    8. Vidal, Thibaut & Laporte, Gilbert & Matl, Piotr, 2020. "A concise guide to existing and emerging vehicle routing problem variants," European Journal of Operational Research, Elsevier, vol. 286(2), pages 401-416.
    9. Ropke, Stefan & Pisinger, David, 2006. "A unified heuristic for a large class of Vehicle Routing Problems with Backhauls," European Journal of Operational Research, Elsevier, vol. 171(3), pages 750-775, June.
    10. Tahami, Hesamoddin & Rabadi, Ghaith & Haouari, Mohamed, 2020. "Exact approaches for routing capacitated electric vehicles," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 144(C).
    11. 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).
    12. 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.
    13. 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.
    14. 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).
    15. Guy Desaulniers & Fausto Errico & Stefan Irnich & Michael Schneider, 2016. "Exact Algorithms for Electric Vehicle-Routing Problems with Time Windows," Operations Research, INFORMS, vol. 64(6), pages 1388-1405, December.
    16. 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.
    17. Sai Shao & Wei Guan & Bin Ran & Zhengbing He & Jun Bi, 2017. "Electric Vehicle Routing Problem with Charging Time and Variable Travel Time," Mathematical Problems in Engineering, Hindawi, vol. 2017, pages 1-13, January.
    18. Juho Andelmin & Enrico Bartolini, 2017. "An Exact Algorithm for the Green Vehicle Routing Problem," Transportation Science, INFORMS, vol. 51(4), pages 1288-1303, November.
    19. Marius M. Solomon, 1987. "Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints," Operations Research, INFORMS, vol. 35(2), pages 254-265, April.
    20. 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.
    21. 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.
    22. 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.
    23. Maximilian Schiffer & Grit Walther, 2018. "An Adaptive Large Neighborhood Search for the Location-routing Problem with Intra-route Facilities," Transportation Science, INFORMS, vol. 52(2), pages 331-352, March.
    24. 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.
    25. 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.
    26. Hiermann, Gerhard & Hartl, Richard F. & Puchinger, Jakob & Vidal, Thibaut, 2019. "Routing a mix of conventional, plug-in hybrid, and electric vehicles," European Journal of Operational Research, Elsevier, vol. 272(1), pages 235-248.
    27. Pelletier, Samuel & Jabali, Ola & Laporte, Gilbert & Veneroni, Marco, 2017. "Battery degradation and behaviour for electric vehicles: Review and numerical analyses of several models," Transportation Research Part B: Methodological, Elsevier, vol. 103(C), pages 158-187.
    28. Guo, Fang & Zhang, Jingjing & Huang, Zhihong & Huang, Weilai, 2022. "Simultaneous charging station location-routing problem for electric vehicles: Effect of nonlinear partial charging and battery degradation," Energy, Elsevier, vol. 250(C).
    29. Turkeš, Renata & Sörensen, Kenneth & Hvattum, Lars Magnus, 2021. "Meta-analysis of metaheuristics: Quantifying the effect of adaptiveness in adaptive large neighborhood search," European Journal of Operational Research, Elsevier, vol. 292(2), pages 423-442.
    30. 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.
    31. Macrina, Giusy & Laporte, Gilbert & Guerriero, Francesca & Di Puglia Pugliese, Luigi, 2019. "An energy-efficient green-vehicle routing problem with mixed vehicle fleet, partial battery recharging and time windows," European Journal of Operational Research, Elsevier, vol. 276(3), pages 971-982.
    32. 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.
    33. 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).
    34. Okan Arslan & Oya Ekin Karaşan & Ridha Mahjoub & Hande Yaman, 2019. "A Branch-and-Cut Algorithm for the Alternative Fuel Refueling Station Location Problem with Routing," Transportation Science, INFORMS, vol. 53(4), pages 1107-1125, July.
    35. Zhang, Jianghua & Zhao, Yingxue & Xue, Weili & Li, Jin, 2015. "Vehicle routing problem with fuel consumption and carbon emission," International Journal of Production Economics, Elsevier, vol. 170(PA), pages 234-242.
    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. Wu, Guoyuan & Peng, Dongbo & Boriboonsomsin, Kanok, 2024. "Developing an Efficient Dispatching Strategy to Support Commercial Fleet Electrification," Institute of Transportation Studies, Working Paper Series qt2qz0n2gv, Institute of Transportation Studies, UC Davis.

    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. Erfan Ghorbani & Mahdi Alinaghian & Gevork. B. Gharehpetian & Sajad Mohammadi & Guido Perboli, 2020. "A Survey on Environmentally Friendly Vehicle Routing Problem and a Proposal of Its Classification," Sustainability, MDPI, vol. 12(21), pages 1-71, October.
    3. Sadati, Mir Ehsan Hesam & Çatay, Bülent, 2021. "A hybrid variable neighborhood search approach for the multi-depot green vehicle routing problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 149(C).
    4. 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.
    5. 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.
    6. 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.
    7. Xiao, Yiyong & Zhang, Yue & Kaku, Ikou & Kang, Rui & Pan, Xing, 2021. "Electric vehicle routing problem: A systematic review and a new comprehensive model with nonlinear energy recharging and consumption," Renewable and Sustainable Energy Reviews, Elsevier, vol. 151(C).
    8. Wang, Weiquan & Zhao, Jingyi, 2023. "Partial linear recharging strategy for the electric fleet size and mix vehicle routing problem with time windows and recharging stations," European Journal of Operational Research, Elsevier, vol. 308(2), pages 929-948.
    9. Malladi, Satya S. & Christensen, Jonas M. & Ramírez, David & Larsen, Allan & Pacino, Dario, 2022. "Stochastic fleet mix optimization: Evaluating electromobility in urban logistics," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 158(C).
    10. Schiffer, Maximilian & Walther, Grit, 2018. "Strategic planning of electric logistics fleet networks: A robust location-routing approach," Omega, Elsevier, vol. 80(C), pages 31-42.
    11. Amine Masmoudi, M. & Coelho, Leandro C. & Demir, Emrah, 2022. "Plug-in hybrid electric refuse vehicle routing problem for waste collection," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 166(C).
    12. 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.
    13. 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.
    14. Tahami, Hesamoddin & Rabadi, Ghaith & Haouari, Mohamed, 2020. "Exact approaches for routing capacitated electric vehicles," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 144(C).
    15. Zhang, Shuai & Gajpal, Yuvraj & Appadoo, S.S. & Abdulkader, M.M.S., 2018. "Electric vehicle routing problem with recharging stations for minimizing energy consumption," International Journal of Production Economics, Elsevier, vol. 203(C), pages 404-413.
    16. Goeke, Dominik, 2019. "Granular tabu search for the pickup and delivery problem with time windows and electric vehicles," European Journal of Operational Research, Elsevier, vol. 278(3), pages 821-836.
    17. Schiffer, Maximilian & Schneider, Michael & Laporte, Gilbert, 2018. "Designing sustainable mid-haul logistics networks with intra-route multi-resource facilities," European Journal of Operational Research, Elsevier, vol. 265(2), pages 517-532.
    18. Seyfi, Majid & Alinaghian, Mahdi & Ghorbani, Erfan & Çatay, Bülent & Saeid Sabbagh, Mohammad, 2022. "Multi-mode hybrid electric vehicle routing problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 166(C).
    19. Macrina, Giusy & Laporte, Gilbert & Guerriero, Francesca & Di Puglia Pugliese, Luigi, 2019. "An energy-efficient green-vehicle routing problem with mixed vehicle fleet, partial battery recharging and time windows," European Journal of Operational Research, Elsevier, vol. 276(3), pages 971-982.
    20. Singh, Nitish & Dang, Quang-Vinh & Akcay, Alp & Adan, Ivo & Martagan, Tugce, 2022. "A matheuristic for AGV scheduling with battery constraints," European Journal of Operational Research, Elsevier, vol. 298(3), pages 855-873.

    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:transe:v:167:y:2022:i:c:s1366554522002940. 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/wps/find/journaldescription.cws_home/600244/description#description .

    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.