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

Duplicating nodes or arcs in green vehicle routing: A computational comparison of two formulations

Author

Listed:
  • Koyuncu, Işıl
  • Yavuz, Mesut

Abstract

This study addresses a family of green vehicle routing problems. A unified framework incorporating several key modeling aspects such as mixed fleets, refueling at customer and non-customer locations, and refueling policies into two competing formulations, namely node- and arc-duplicating is provided. Additionally, both formulations are strengthened via (i) two label setting algorithms to tighten the bounds of common variables, and (ii) improved lower bound on the number of routes. Through computational experiments based on two testbeds from the literature, the study concludes that the less common arc-duplicating formulation outperforms the more common node-duplicating formulation.

Suggested Citation

  • Koyuncu, Işıl & Yavuz, Mesut, 2019. "Duplicating nodes or arcs in green vehicle routing: A computational comparison of two formulations," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 122(C), pages 605-623.
    • Handle: RePEc:eee:transe:v:122:y:2019:i:c:p:605-623
    DOI: 10.1016/j.tre.2018.11.003
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S1366554518305544
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.tre.2018.11.003?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. Bektas, Tolga & Laporte, Gilbert, 2011. "The Pollution-Routing Problem," Transportation Research Part B: Methodological, Elsevier, vol. 45(8), pages 1232-1250, September.
    2. Mesut Yavuz & Ismail Çapar, 2017. "Alternative-Fuel Vehicle Adoption in Service Fleets: Impact Evaluation Through Optimization Modeling," Transportation Science, INFORMS, vol. 51(2), pages 480-493, May.
    3. Koç, Çağrı & Bektaş, Tolga & Jabali, Ola & Laporte, Gilbert, 2014. "The fleet size and mix pollution-routing problem," Transportation Research Part B: Methodological, Elsevier, vol. 70(C), pages 239-254.
    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. Franceschetti, Anna & Honhon, Dorothée & Van Woensel, Tom & Bektaş, Tolga & Laporte, Gilbert, 2013. "The time-dependent pollution-routing problem," Transportation Research Part B: Methodological, Elsevier, vol. 56(C), pages 265-293.
    6. Stefan Frank & Henning Preis & Karl Nachtigall, 2014. "On the Modeling of Recharging Stops in Context of Vehicle Routing Problems," Operations Research Proceedings, in: Dennis Huisman & Ilse Louwerse & Albert P.M. Wagelmans (ed.), Operations Research Proceedings 2013, edition 127, pages 129-135, Springer.
    7. 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.
    8. 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.
    9. Juho Andelmin & Enrico Bartolini, 2017. "An Exact Algorithm for the Green Vehicle Routing Problem," Transportation Science, INFORMS, vol. 51(4), pages 1288-1303, November.
    10. Schneider, M. & Stenger, A. & Hof, J., 2015. "An Adaptive VNS Algorithm for Vehicle Routing Problems with Intermediate Stops," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 63500, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    11. 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.
    12. Demir, Emrah & Bektaş, Tolga & Laporte, Gilbert, 2014. "The bi-objective Pollution-Routing Problem," European Journal of Operational Research, Elsevier, vol. 232(3), pages 464-478.
    13. 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.
    14. Woodward, Christel A. & Abelson, Julia & Tedford, Sara & Hutchison, Brian, 2004. "What is important to continuity in home care?: Perspectives of key stakeholders," Social Science & Medicine, Elsevier, vol. 58(1), pages 177-192, January.
    15. 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.
    16. Nesbitt, Kevin & Sperling, Daniel, 2001. "Fleet Purchase Behavior: Decision Processes and Implications for New Vehicle Technologies and Fuels," Institute of Transportation Studies, Working Paper Series qt15k63162, Institute of Transportation Studies, UC Davis.
    17. Gilbert Laporte & Yves Nobert & Martin Desrochers, 1985. "Optimal Routing under Capacity and Distance Restrictions," Operations Research, INFORMS, vol. 33(5), pages 1050-1073, October.
    18. Chung-Lun Li & David Simchi-Levi & Martin Desrochers, 1992. "On the Distance Constrained Vehicle Routing Problem," Operations Research, INFORMS, vol. 40(4), pages 790-799, August.
    19. 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.
    20. Hiermann, Gerhard & Puchinger, Jakob & Ropke, Stefan & Hartl, Richard F., 2016. "The Electric Fleet Size and Mix Vehicle Routing Problem with Time Windows and Recharging Stations," European Journal of Operational Research, Elsevier, vol. 252(3), pages 995-1018.
    21. 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.
    22. 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. 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.
    2. 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).
    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. Wei Xu & Chenghao Zhang & Ming Cheng & Yucheng Huang, 2022. "Electric Vehicle Routing Problem with Simultaneous Pickup and Delivery: Mathematical Modeling and Adaptive Large Neighborhood Search Heuristic Method," Energies, MDPI, vol. 15(23), pages 1-25, December.
    5. Racha El-Hajj & Rym Nesrine Guibadj & Aziz Moukrim & Mehdi Serairi, 2020. "A PSO based algorithm with an efficient optimal split procedure for the multiperiod vehicle routing problem with profit," Annals of Operations Research, Springer, vol. 291(1), pages 281-316, August.
    6. 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.
    7. 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.

    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. Bektaş, Tolga & Ehmke, Jan Fabian & Psaraftis, Harilaos N. & Puchinger, Jakob, 2019. "The role of operational research in green freight transportation," European Journal of Operational Research, Elsevier, vol. 274(3), pages 807-823.
    4. 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.
    5. 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).
    6. 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.
    7. 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.
    8. 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.
    9. 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).
    10. 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.
    11. 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.
    12. 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.
    13. 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.
    14. Alvo, Matías & Angulo, Gustavo & Klapp, Mathias A., 2021. "An exact solution approach for an electric bus dispatch problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 156(C).
    15. 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.
    16. Li, Lu & Lo, Hong K. & Huang, Wei & Xiao, Feng, 2021. "Mixed bus fleet location-routing-scheduling under range uncertainty," Transportation Research Part B: Methodological, Elsevier, vol. 146(C), pages 155-179.
    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. 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).
    19. 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.
    20. 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).

    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:122:y:2019:i:c:p:605-623. 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.