IDEAS home Printed from https://ideas.repec.org/p/hal/journl/hal-02511086.html
   My bibliography  Save this paper

Enhanced multi-directional local search for the bi-objective heterogeneous vehicle routing problem with multiple driving ranges

Author

Listed:
  • Majid Eskandarpour

    (IRCCyN - Institut de Recherche en Communications et en Cybernétique de Nantes - Mines Nantes - Mines Nantes - ECN - École Centrale de Nantes - EPUN - Ecole Polytechnique de l'Université de Nantes - UN - Université de Nantes - UNAM - PRES Université Nantes Angers Le Mans - CNRS - Centre National de la Recherche Scientifique, LEM - Lille économie management - UMR 9221 - UA - Université d'Artois - UCL - Université catholique de Lille - Université de Lille - CNRS - Centre National de la Recherche Scientifique)

  • Djamila Ouelhadj

    (School of Computer Science - UON - University of Nottingham, UK)

  • Sara Hatami
  • Angel Juan

    (Open University of Catalonia [Barcelona])

  • Banafsheh Khosravi

Abstract

The transportation sector accounts for a significant amount of greenhouse gas emissions. To mitigate this problem, electric vehicles have been widely recommended as green vehicles with lower emissions. However, the driving range of electric vehicles is limited due to their battery capacity. In this paper, a bi-objective mixed-integer linear programming model is proposed to minimise total costs (fixed plus variable) as well as CO2 emissions caused by the vehicles used in the fleet for a Heterogeneous Vehicle Routing Problem with Multiple Loading Capacities and Driving Ranges (HeVRPMD). To solve the proposed model, an enhanced variant of Multi-Directional Local Search (EMDLS) is developed to approximate the Pareto frontier. The proposed method employs a Large Neighbourhood Search (LNS) framework to find efficient solutions and update the approximated Pareto frontier at each iteration. The LNS algorithm makes use of three routing-oriented destroy operators and a construction heuristic based on a multi-round approach. The performance of EMDLS is compared to MDLS, an Improved MDLS (IMDLS), non-dominated sorting genetic algorithm II (NSGAII), non-dominated sorting genetic algorithm III (NSGAIII), and the weighting and epsilon-constraint methods. Extensive experiments have been conducted using a set of instances generated from the Capacitated Vehicle Routing Problem benchmark tests in the literature. In addition, real data is utilised to estimate fixed and variable costs, CO2 emissions, capacity, and the driving range of each type of vehicle. The results show the effectiveness of the proposed method to find high-quality non-dominated solutions.

Suggested Citation

  • Majid Eskandarpour & Djamila Ouelhadj & Sara Hatami & Angel Juan & Banafsheh Khosravi, 2019. "Enhanced multi-directional local search for the bi-objective heterogeneous vehicle routing problem with multiple driving ranges," Post-Print hal-02511086, HAL.
    • Handle: RePEc:hal:journl:hal-02511086
    DOI: 10.1016/j.ejor.2019.02.048
    Note: View the original document on HAL open archive server: https://hal.science/hal-02511086
    as

    Download full text from publisher

    File URL: https://hal.science/hal-02511086/document
    Download Restriction: no
    File URL: https://libkey.io/10.1016/j.ejor.2019.02.048?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
    ---><---

    Other versions of this item:

    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. 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.
    3. Koç, Çağrı & Bektaş, Tolga & Jabali, Ola & Laporte, Gilbert, 2016. "Thirty years of heterogeneous vehicle routing," European Journal of Operational Research, Elsevier, vol. 249(1), pages 1-21.
    4. Caballero, Rafael & Gonzalez, Mercedes & Guerrero, Flor M & Molina, Julian & Paralera, Concepcion, 2007. "Solving a multiobjective location routing problem with a metaheuristic based on tabu search. Application to a real case in Andalusia," European Journal of Operational Research, Elsevier, vol. 177(3), pages 1751-1763, March.
    5. Dekker, Rommert & Bloemhof, Jacqueline & Mallidis, Ioannis, 2012. "Operations Research for green logistics – An overview of aspects, issues, contributions and challenges," European Journal of Operational Research, Elsevier, vol. 219(3), pages 671-679.
    6. 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.
    7. Tight, M.R. & Bristow, A.L. & Pridmore, A. & May, A.D., 2005. "What is a sustainable level of CO2 emissions from transport activity in the UK in 2050?," Transport Policy, Elsevier, vol. 12(3), pages 235-244, May.
    8. Kunlei Lian & Ashlea Bennett Milburn & Ronald L. Rardin, 2016. "An improved multi-directional local search algorithm for the multi-objective consistent vehicle routing problem," IISE Transactions, Taylor & Francis Journals, vol. 48(10), pages 975-992, October.
    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. A A Juan & J Faulin & J Jorba & D Riera & D Masip & B Barrios, 2011. "On the use of Monte Carlo simulation, cache and splitting techniques to improve the Clarke and Wright savings heuristics," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 62(6), pages 1085-1097, June.
    11. Tolga Bektaş & Emrah Demir & Gilbert Laporte, 2016. "Green Vehicle Routing," International Series in Operations Research & Management Science, in: Harilaos N. Psaraftis (ed.), Green Transportation Logistics, edition 127, chapter 0, pages 243-265, Springer.
    12. 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).
    13. G. Clarke & J. W. Wright, 1964. "Scheduling of Vehicles from a Central Depot to a Number of Delivery Points," Operations Research, INFORMS, vol. 12(4), pages 568-581, August.
    14. 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.
    15. Angel Juan & Javier Faulin & Albert Ferrer & Helena Lourenço & Barry Barrios, 2013. "MIRHA: multi-start biased randomization of heuristics with adaptive local search for solving non-smooth routing problems," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 21(1), pages 109-132, April.
    16. 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.
    17. Angel Alejandro Juan & Carlos Alberto Mendez & Javier Faulin & Jesica De Armas & Scott Erwin Grasman, 2016. "Electric Vehicles in Logistics and Transportation: A Survey on Emerging Environmental, Strategic, and Operational Challenges," Energies, MDPI, vol. 9(2), pages 1-21, January.
    18. Franceschetti, Anna & Demir, Emrah & Honhon, Dorothée & Van Woensel, Tom & Laporte, Gilbert & Stobbe, Mark, 2017. "A metaheuristic for the time-dependent pollution-routing problem," European Journal of Operational Research, Elsevier, vol. 259(3), pages 972-991.
    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. Zajac, Sandra & Huber, Sandra, 2021. "Objectives and methods in multi-objective routing problems: a survey and classification scheme," European Journal of Operational Research, Elsevier, vol. 290(1), pages 1-25.
    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. Anderluh, Alexandra & Nolz, Pamela C. & Hemmelmayr, Vera C. & Crainic, Teodor Gabriel, 2021. "Multi-objective optimization of a two-echelon vehicle routing problem with vehicle synchronization and ‘grey zone’ customers arising in urban logistics," European Journal of Operational Research, Elsevier, vol. 289(3), pages 940-958.
    4. 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).
    5. José-Fernando Camacho-Vallejo & Lilian López-Vera & Alice E. Smith & José-Luis González-Velarde, 2022. "A tabu search algorithm to solve a green logistics bi-objective bi-level problem," Annals of Operations Research, Springer, vol. 316(2), pages 927-953, September.
    6. Nasreddine Ouertani & Hajer Ben-Romdhane & Saoussen Krichen & Issam Nouaouri, 2022. "A vector evaluated evolutionary algorithm with exploitation reinforcement for the dynamic pollution routing problem," Journal of Combinatorial Optimization, Springer, vol. 44(2), pages 1011-1038, September.
    7. Miriam Enzi & Sophie N. Parragh & Jakob Puchinger, 2022. "The bi-objective multimodal car-sharing problem," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 44(2), pages 307-348, June.
    8. Bochra Rabbouch & Foued Saâdaoui & Rafaa Mraihi, 2021. "Efficient implementation of the genetic algorithm to solve rich vehicle routing problems," Operational Research, Springer, vol. 21(3), pages 1763-1791, September.
    9. Yong Wang & Jiayi Zhe & Xiuwen Wang & Yaoyao Sun & Haizhong Wang, 2022. "Collaborative Multidepot Vehicle Routing Problem with Dynamic Customer Demands and Time Windows," Sustainability, MDPI, vol. 14(11), pages 1-37, May.
    10. Leandro do C. Martins & Rafael D. Tordecilla & Juliana Castaneda & Angel A. Juan & Javier Faulin, 2021. "Electric Vehicle Routing, Arc Routing, and Team Orienteering Problems in Sustainable Transportation," Energies, MDPI, vol. 14(16), pages 1-30, August.
    11. Majid Eskandarpour & Pierre Dejax & Olivier Péton, 2019. "Multi-Directional Local Search for Sustainable Supply Chain Network Design," Post-Print hal-02407741, HAL.
    12. Yanfei Zhu & Chunhui Li & Kwang Y. Lee, 2022. "The NR-EGA for the EVRP Problem with the Electric Energy Consumption Model," Energies, MDPI, vol. 15(10), pages 1-12, May.
    13. 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).
    14. 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.
    15. Yuda Li & Mohammad Peyman & Javier Panadero & Angel A. Juan & Fatos Xhafa, 2022. "IoT Analytics and Agile Optimization for Solving Dynamic Team Orienteering Problems with Mandatory Visits," Mathematics, MDPI, vol. 10(6), pages 1-21, March.

    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. 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.
    4. 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.
    5. 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.
    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. 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.
    8. 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.
    9. 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.
    10. 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).
    11. 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).
    12. 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.
    13. 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.
    14. 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.
    15. 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.
    16. 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.
    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. 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.
    19. 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).
    20. 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.

    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:hal:journl:hal-02511086. 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: CCSD (email available below). General contact details of provider: https://hal.archives-ouvertes.fr/ .

    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.