IDEAS home Printed from https://ideas.repec.org/a/spr/joheur/v24y2018i5d10.1007_s10732-018-9377-x.html
   My bibliography  Save this article

A comparison of acceptance criteria for the adaptive large neighbourhood search metaheuristic

Author

Listed:
  • Alberto Santini

    (Pompeu Fabra University and Barcelona GSE)

  • Stefan Ropke

    (DTU Management Science)

  • Lars Magnus Hvattum

    (Molde University College)

Abstract

Adaptive large neighborhood search (ALNS) is a useful framework for solving difficult combinatorial optimisation problems. As a metaheuristic, it consists of some components that must be tailored to the specific optimisation problem that is being solved, while other components are problem independent. The literature is sparse with respect to studies that aim to evaluate the relative merit of different alternatives for specific problem independent components. This paper investigates one such component, the move acceptance criterion in ALNS, and compares a range of alternatives. Through extensive computational testing, the alternative move acceptance criteria are ranked in three groups, depending on the performance of the resulting ALNS implementations. Among the best variants, we find versions of criteria based on simulated annealing, threshold acceptance, and record-to-record travel, with a version of the latter being consistently undominated by the others. Additional analyses focus on the search behavior, and multiple linear regression is used to identify characteristics of search behavior that are associated with good search performance.

Suggested Citation

  • 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.
    • Handle: RePEc:spr:joheur:v:24:y:2018:i:5:d:10.1007_s10732-018-9377-x
    DOI: 10.1007/s10732-018-9377-x
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10732-018-9377-x
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10732-018-9377-x?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

    for a different version of it.

    References listed on IDEAS

    as
    1. 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.
    2. 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.
    3. Edmund K Burke & Michel Gendreau & Matthew Hyde & Graham Kendall & Gabriela Ochoa & Ender Özcan & Rong Qu, 2013. "Hyper-heuristics: a survey of the state of the art," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 64(12), pages 1695-1724, December.
    4. Muller, Laurent Flindt & Spoorendonk, Simon & Pisinger, David, 2012. "A hybrid adaptive large neighborhood search heuristic for lot-sizing with setup times," European Journal of Operational Research, Elsevier, vol. 218(3), pages 614-623.
    5. 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.
    6. Eugene L. Lawler, 1963. "The Quadratic Assignment Problem," Management Science, INFORMS, vol. 9(4), pages 586-599, July.
    7. Hansen, Pierre & Mladenovic, Nenad, 2001. "Variable neighborhood search: Principles and applications," European Journal of Operational Research, Elsevier, vol. 130(3), pages 449-467, May.
    8. Schmid, Verena, 2014. "Hybrid large neighborhood search for the bus rapid transit route design problem," European Journal of Operational Research, Elsevier, vol. 238(2), pages 427-437.
    9. Ruiz, Ruben & Stutzle, Thomas, 2007. "A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem," European Journal of Operational Research, Elsevier, vol. 177(3), pages 2033-2049, March.
    10. Potvin, Jean-Yves & Rousseau, Jean-Marc, 1993. "A parallel route building algorithm for the vehicle routing and scheduling problem with time windows," European Journal of Operational Research, Elsevier, vol. 66(3), pages 331-340, May.
    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. Sistig, Hubert Maximilian & Sauer, Dirk Uwe, 2023. "Metaheuristic for the integrated electric vehicle and crew scheduling problem," Applied Energy, Elsevier, vol. 339(C).
    2. Reza Eslamipoor, 2024. "Direct and indirect emissions: a bi-objective model for hybrid vehicle routing problem," Journal of Business Economics, Springer, vol. 94(3), pages 413-436, April.
    3. Amira Saker & Amr Eltawil & Islam Ali, 2023. "Adaptive Large Neighborhood Search Metaheuristic for the Capacitated Vehicle Routing Problem with Parcel Lockers," Logistics, MDPI, vol. 7(4), pages 1-27, October.
    4. Wang, Yu & Ropke, Stefan & Wen, Min & Bergh, Simon, 2023. "The mobile production vehicle routing problem: Using 3D printing in last mile distribution," European Journal of Operational Research, Elsevier, vol. 305(3), pages 1407-1423.
    5. Alberto Santini & Michael Schneider & Thibaut Vidal & Daniele Vigo, 2023. "Decomposition Strategies for Vehicle Routing Heuristics," INFORMS Journal on Computing, INFORMS, vol. 35(3), pages 543-559, May.
    6. Dalmau, Ramon & Gawinowski, Gilles & Anoraud, Camille, 2022. "Comparison of various temporal air traffic flow management models in critical scenarios," Journal of Air Transport Management, Elsevier, vol. 105(C).
    7. Eilertsen, Ulrik & Falck-Pedersen, Olav M. & Henriksen, Jone V. & Fagerholt, Kjetil & Pantuso, Giovanni, 2024. "Joint relocation and pricing in electric car-sharing systems," European Journal of Operational Research, Elsevier, vol. 315(2), pages 553-566.
    8. 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.
    9. 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.
    10. 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.
    11. 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.
    12. Konrad Steiner, 2019. "Schedule-Based Integrated Inter-City Bus Line Planning for Multiple Timetabled Services via Large Multiple Neighborhood Search," Working Papers 1902, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    13. Jann Michael Weinand & Kenneth Sorensen & Pablo San Segundo & Max Kleinebrahm & Russell McKenna, 2020. "Research trends in combinatorial optimisation," Papers 2012.01294, arXiv.org.
    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. Lena Hörsting & Catherine Cleophas, 2023. "Integrating Micro-Depot Freight Transport in Existing Public Transport Services," SN Operations Research Forum, Springer, vol. 4(3), pages 1-35, September.
    16. Nielsen, Clara Chini & Pisinger, David, 2023. "Tactical planning for dynamic technician routing and scheduling problems," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 177(C).

    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. 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.
    3. 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.
    4. 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.
    5. Blum, Christian & Ochoa, Gabriela, 2021. "A comparative analysis of two matheuristics by means of merged local optima networks," European Journal of Operational Research, Elsevier, vol. 290(1), pages 36-56.
    6. 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.
    7. Yu, Vincent F. & Jodiawan, Panca & Hou, Ming-Lu & Gunawan, Aldy, 2021. "Design of a two-echelon freight distribution system in last-mile logistics considering covering locations and occasional drivers," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 154(C).
    8. Worapot Sirirak & Rapeepan Pitakaso, 2018. "Marketplace Location Decision Making and Tourism Route Planning," Administrative Sciences, MDPI, vol. 8(4), pages 1-25, November.
    9. Fowler, John W. & Mönch, Lars, 2022. "A survey of scheduling with parallel batch (p-batch) processing," European Journal of Operational Research, Elsevier, vol. 298(1), pages 1-24.
    10. Vadlamani, Satish & Hosseini, Seyedmohsen, 2014. "A novel heuristic approach for solving aircraft landing problem with single runway," Journal of Air Transport Management, Elsevier, vol. 40(C), pages 144-148.
    11. Groß, Patrick-Oliver & Ehmke, Jan Fabian & Mattfeld, Dirk Christian, 2020. "Interval travel times for robust synchronization in city logistics vehicle routing," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 143(C).
    12. Li, Hongqi & Wang, Haotian & Chen, Jun & Bai, Ming, 2021. "Two-echelon vehicle routing problem with satellite bi-synchronization," European Journal of Operational Research, Elsevier, vol. 288(3), pages 775-793.
    13. Ruf, Moritz & Cordeau, Jean-François, 2021. "Adaptive large neighborhood search for integrated planning in railroad classification yards," Transportation Research Part B: Methodological, Elsevier, vol. 150(C), pages 26-51.
    14. Punnen, Abraham P. & Wang, Yang, 2016. "The bipartite quadratic assignment problem and extensions," European Journal of Operational Research, Elsevier, vol. 250(3), pages 715-725.
    15. Pan, Quan-Ke & Gao, Liang & Li, Xin-Yu & Gao, Kai-Zhou, 2017. "Effective metaheuristics for scheduling a hybrid flowshop with sequence-dependent setup times," Applied Mathematics and Computation, Elsevier, vol. 303(C), pages 89-112.
    16. Chun-Lung Chen, 2023. "An Iterated Population-Based Metaheuristic for Order Acceptance and Scheduling in Unrelated Parallel Machines with Several Practical Constraints," Mathematics, MDPI, vol. 11(6), pages 1-14, March.
    17. Mejía, Gonzalo & Yuraszeck, Francisco, 2020. "A self-tuning variable neighborhood search algorithm and an effective decoding scheme for open shop scheduling problems with travel/setup times," European Journal of Operational Research, Elsevier, vol. 285(2), pages 484-496.
    18. 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).
    19. 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.
    20. Beezão, Andreza Cristina & Cordeau, Jean-François & Laporte, Gilbert & Yanasse, Horacio Hideki, 2017. "Scheduling identical parallel machines with tooling constraints," European Journal of Operational Research, Elsevier, vol. 257(3), pages 834-844.

    More about this item

    Keywords

    ;
    ;
    ;
    ;
    ;
    ;
    ;

    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:spr:joheur:v:24:y:2018:i:5:d:10.1007_s10732-018-9377-x. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.