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

A review and ranking of operators in adaptive large neighborhood search for vehicle routing problems

Author

Listed:
  • Voigt, Stefan

Abstract

This article systematically reviews the literature on adaptive large neighborhood search (ALNS) to gain insights into the operators used for vehicle routing problems (VRPs) and their effectiveness. The ALNS has been successfully applied to a variety of optimization problems, particularly variants of the VRP. The ALNS gradually improves an initial solution by modifying it using removal and insertion operators. However, relying solely on adaptive operator selection is not advisable. Instead, authors often conduct experiments to identify operators that improve the solution quality or remove detrimental ones. This process is mostly cumbersome due to the wide variety of operators, further complicated by inconsistent nomenclature. The objectives of this review are threefold: First, to classify ALNS operators using a unified terminology; second, to analyze their performance; and third, to present guidelines for the development and analysis of ALNS algorithms in the future based on the outcomes of the performance evaluation. In this review, we conduct a network meta-analysis of 211 articles published between 2006 and 2023 that have applied ALNS algorithms in the context of VRPs. We employ incomplete pairwise comparison matrices, similar to rankings used in sports, to rank the operators. We identify 57 distinct removal and 42 insertion operators, and the analysis ranks them based on their effectiveness. Sequence-based removal operators, which remove sequences of customers in the current solution, are found to be the most effective. The best-performing insertion operators are those that exhibit foresight, such as regret insertion operators. Finally, guidelines and possible future research directions are discussed.

Suggested Citation

  • Voigt, Stefan, 2025. "A review and ranking of operators in adaptive large neighborhood search for vehicle routing problems," European Journal of Operational Research, Elsevier, vol. 322(2), pages 357-375.
  • Handle: RePEc:eee:ejores:v:322:y:2025:i:2:p:357-375
    DOI: 10.1016/j.ejor.2024.05.033
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221724003928
    Download Restriction: Full text for ScienceDirect subscribers only

    File URL: https://libkey.io/10.1016/j.ejor.2024.05.033?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. 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).
    2. Grangier, Philippe & Gendreau, Michel & Lehuédé, Fabien & Rousseau, Louis-Martin, 2016. "An adaptive large neighborhood search for the two-echelon multiple-trip vehicle routing problem with satellite synchronization," European Journal of Operational Research, Elsevier, vol. 254(1), pages 80-91.
    3. Rahma Lahyani & Anne-Lise Gouguenheim & Leandro C. Coelho, 2019. "A hybrid adaptive large neighbourhood search for multi-depot open vehicle routing problems," International Journal of Production Research, Taylor & Francis Journals, vol. 57(22), pages 6963-6976, November.
    4. Thibaut Vidal & Teodor Gabriel Crainic & Michel Gendreau & Nadia Lahrichi & Walter Rei, 2012. "A Hybrid Genetic Algorithm for Multidepot and Periodic Vehicle Routing Problems," Operations Research, INFORMS, vol. 60(3), pages 611-624, June.
    5. 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.
    6. Ghiami, Yousef & Demir, Emrah & Van Woensel, Tom & Christiansen, Marielle & Laporte, Gilbert, 2019. "A deteriorating inventory routing problem for an inland liquefied natural gas distribution network," Transportation Research Part B: Methodological, Elsevier, vol. 126(C), pages 45-67.
    7. David Sacramento & Christine Solnon & David Pisinger, 2020. "Constraint Programming and Local Search Heuristic: a Matheuristic Approach for Routing and Scheduling Feeder Vessels in Multi-terminal Ports," SN Operations Research Forum, Springer, vol. 1(4), pages 1-33, December.
    8. Bozóki, Sándor & Csató, László & Temesi, József, 2016. "An application of incomplete pairwise comparison matrices for ranking top tennis players," European Journal of Operational Research, Elsevier, vol. 248(1), pages 211-218.
    9. 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.
    10. Adria Soriano & Margaretha Gansterer & Richard F. Hartl, 2018. "The two-region multi-depot pickup and delivery problem," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 40(4), pages 1077-1108, October.
    11. Yossiri Adulyasak & Jean-François Cordeau & Raf Jans, 2014. "Optimization-Based Adaptive Large Neighborhood Search for the Production Routing Problem," Transportation Science, INFORMS, vol. 48(1), pages 20-45, February.
    12. Alarcon Ortega, Emilio J. & Schilde, Michael & Doerner, Karl F., 2020. "Matheuristic search techniques for the consistent inventory routing problem with time windows and split deliveries," Operations Research Perspectives, Elsevier, vol. 7(C).
    13. David Moher & Alessandro Liberati & Jennifer Tetzlaff & Douglas G Altman & The PRISMA Group, 2009. "Preferred Reporting Items for Systematic Reviews and Meta-Analyses: The PRISMA Statement," PLOS Medicine, Public Library of Science, vol. 6(7), pages 1-6, July.
    14. 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.
    15. Özarık, Sami Serkan & Veelenturf, Lucas P. & Woensel, Tom Van & Laporte, Gilbert, 2021. "Optimizing e-commerce last-mile vehicle routing and scheduling under uncertain customer presence," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 148(C).
    16. Real, Luiza Bernardes & Contreras, Ivan & Cordeau, Jean-François & de Camargo, Ricardo Saraiva & de Miranda, Gilberto, 2021. "Multimodal hub network design with flexible routes," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 146(C).
    17. Jan Christiaens & Greet Vanden Berghe, 2020. "Slack Induction by String Removals for Vehicle Routing Problems," Transportation Science, INFORMS, vol. 54(2), pages 417-433, March.
    18. 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.
    19. Fontaine, Pirmin, 2022. "The vehicle routing problem with load-dependent travel times for cargo bicycles," European Journal of Operational Research, Elsevier, vol. 300(3), pages 1005-1016.
    20. Alinaghian, Mahdi & Shokouhi, Nadia, 2018. "Multi-depot multi-compartment vehicle routing problem, solved by a hybrid adaptive large neighborhood search," Omega, Elsevier, vol. 76(C), pages 85-99.
    21. 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).
    22. Alberto Santini & Stefan Ropke & Lars Magnus Hvattum, 2018. "A comparison of acceptance criteria for the adaptive large neighbourhood search metaheuristic," Journal of Heuristics, Springer, vol. 24(5), pages 783-815, October.
    23. Gullhav, Anders N. & Cordeau, Jean-François & Hvattum, Lars Magnus & Nygreen, Bjørn, 2017. "Adaptive large neighborhood search heuristics for multi-tier service deployment problems in clouds," European Journal of Operational Research, Elsevier, vol. 259(3), pages 829-846.
    24. Demir, Emrah & Bektaş, Tolga & Laporte, Gilbert, 2012. "An adaptive large neighborhood search heuristic for the Pollution-Routing Problem," European Journal of Operational Research, Elsevier, vol. 223(2), pages 346-359.
    25. 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.
    26. Dayarian, Iman & Crainic, Teodor Gabriel & Gendreau, Michel & Rei, Walter, 2016. "An adaptive large-neighborhood search heuristic for a multi-period vehicle routing problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 95(C), pages 95-123.
    27. Paolo Toth & Daniele Vigo, 2003. "The Granular Tabu Search and Its Application to the Vehicle-Routing Problem," INFORMS Journal on Computing, INFORMS, vol. 15(4), pages 333-346, November.
    28. 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.
    29. Hellsten, Erik Orm & Sacramento, David & Pisinger, David, 2020. "An adaptive large neighbourhood search heuristic for routing and scheduling feeder vessels in multi-terminal ports," European Journal of Operational Research, Elsevier, vol. 287(2), pages 682-698.
    30. Renaud Masson & Fabien Lehuédé & Olivier Péton, 2013. "An Adaptive Large Neighborhood Search for the Pickup and Delivery Problem with Transfers," Transportation Science, INFORMS, vol. 47(3), pages 344-355, August.
    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. 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.
    2. TURKEŠ, Renata & SÖRENSEN, Kenneth & HVATTUM, Lars Magnus & BARRENA, Eva & CHENTLI, Hayet & COELHO, Leandro & DAYARIAN, Iman & GRIMAULT, Axel & GULLHAVE, Anders & IRIS, Çagatay & KESKIN, Merve & KIEFE, 2019. "Meta-analysis of metaheuristics: Quantifying the effect of adaptiveness in adaptive large neighborhood search," Working Papers 2019002, University of Antwerp, Faculty of Business and Economics.
    3. 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.
    4. 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).
    5. Liu, Yiming & Roberto, Baldacci & Zhou, Jianwen & Yu, Yang & Zhang, Yu & Sun, Wei, 2023. "Efficient feasibility checks and an adaptive large neighborhood search algorithm for the time-dependent green vehicle routing problem with time windows," European Journal of Operational Research, Elsevier, vol. 310(1), pages 133-155.
    6. Yu, Vincent F. & Anh, Pham Tuan & Baldacci, Roberto, 2023. "A robust optimization approach for the vehicle routing problem with cross-docking under demand uncertainty," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 173(C).
    7. Bao, Dan-Wen & Zhou, Jia-Yi & Zhang, Zi-Qian & Chen, Zhuo & Kang, Di, 2023. "Mixed fleet scheduling method for airport ground service vehicles under the trend of electrification," Journal of Air Transport Management, Elsevier, vol. 108(C).
    8. Kallestad, Jakob & Hasibi, Ramin & Hemmati, Ahmad & Sörensen, Kenneth, 2023. "A general deep reinforcement learning hyperheuristic framework for solving combinatorial optimization problems," European Journal of Operational Research, Elsevier, vol. 309(1), pages 446-468.
    9. Gläser, Sina, 2022. "A waste collection problem with service type option," European Journal of Operational Research, Elsevier, vol. 303(3), pages 1216-1230.
    10. Dumez, Dorian & Lehuédé, Fabien & Péton, Olivier, 2021. "A large neighborhood search approach to the vehicle routing problem with delivery options," Transportation Research Part B: Methodological, Elsevier, vol. 144(C), pages 103-132.
    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. Dumez, Dorian & Tilk, Christian & Irnich, Stefan & Lehuédé, Fabien & Olkis, Katharina & Péton, Olivier, 2023. "A matheuristic for a 2-echelon vehicle routing problem with capacitated satellites and reverse flows," European Journal of Operational Research, Elsevier, vol. 305(1), pages 64-84.
    13. Masmoudi, Mohamed Amine & Hosny, Manar & Braekers, Kris & Dammak, Abdelaziz, 2016. "Three effective metaheuristics to solve the multi-depot multi-trip heterogeneous dial-a-ride problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 96(C), pages 60-80.
    14. 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.
    15. Zhang, Yimeng & Li, Xinlei & van Hassel, Edwin & Negenborn, Rudy R. & Atasoy, Bilge, 2022. "Synchromodal transport planning considering heterogeneous and vague preferences of shippers," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 164(C).
    16. Liu, Dan & Yan, Pengyu & Pu, Ziyuan & Wang, Yinhai & Kaisar, Evangelos I., 2021. "Hybrid artificial immune algorithm for optimizing a Van-Robot E-grocery delivery system," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 154(C).
    17. Li, Hongqi & Wang, Haotian & Chen, Jun & Bai, Ming, 2020. "Two-echelon vehicle routing problem with time windows and mobile satellites," Transportation Research Part B: Methodological, Elsevier, vol. 138(C), pages 179-201.
    18. 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).
    19. Frey, Christian M.M. & Jungwirth, Alexander & Frey, Markus & Kolisch, Rainer, 2023. "The vehicle routing problem with time windows and flexible delivery locations," European Journal of Operational Research, Elsevier, vol. 308(3), pages 1142-1159.
    20. Brunner, Carlos & Giesen, Ricardo & Klapp, Mathias A. & Flórez-Calderón, Luz, 2021. "Vehicle routing problem with steep roads," Transportation Research Part A: Policy and Practice, Elsevier, vol. 151(C), pages 1-17.

    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:322:y:2025:i:2:p:357-375. 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.