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

Meta-analysis of metaheuristics: Quantifying the effect of adaptiveness in adaptive large neighborhood search

Author

Listed:
  • Turkeš, Renata
  • Sörensen, Kenneth
  • Hvattum, Lars Magnus

Abstract

Research on metaheuristics has focused on (novel) algorithmic development and on competitive testing, both of which have been frequently argued to yield little generalizable knowledge. The main goal of this paper is to promote meta-analysis — a systematic statistical examination that combines the results of several independent studies — as a more suitable way to obtain problem- and implementation-independent insights on metaheuristics. Meta-analysis is widely used in several scientific domains, most notably the medical sciences (e.g., to establish the efficacy of a certain treatment). To the best of our knowledge, this is the first meta-analysis in the field of metaheuristics.

Suggested Citation

  • 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.
    • Handle: RePEc:eee:ejores:v:292:y:2021:i:2:p:423-442
    DOI: 10.1016/j.ejor.2020.10.045
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S037722172030936X
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2020.10.045?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. David Pisinger & Stefan Ropke, 2010. "Large Neighborhood Search," International Series in Operations Research & Management Science, in: Michel Gendreau & Jean-Yves Potvin (ed.), Handbook of Metaheuristics, chapter 0, pages 399-419, Springer.
    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. Žulj, Ivan & Kramer, Sergej & Schneider, Michael, 2018. "A hybrid of adaptive large neighborhood search and tabu search for the order-batching problem," European Journal of Operational Research, Elsevier, vol. 264(2), pages 653-664.
    4. 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.
    5. 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.
    6. Alexander Kiefer & Richard F. Hartl & Alexander Schnell, 2017. "Adaptive large neighborhood search for the curriculum-based course timetabling problem," Annals of Operations Research, Springer, vol. 252(2), pages 255-282, May.
    7. Majid Salavati-Khoshghalb & Michel Gendreau & Ola Jabali & Walter Rei, 2019. "A Rule-Based Recourse for the Vehicle Routing Problem with Stochastic Demands," Transportation Science, INFORMS, vol. 53(5), pages 1334-1353, September.
    8. 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.
    9. Li, Yuan & Chen, Haoxun & Prins, Christian, 2016. "Adaptive large neighborhood search for the pickup and delivery problem with time windows, profits, and reserved requests," European Journal of Operational Research, Elsevier, vol. 252(1), pages 27-38.
    10. François, Véronique & Arda, Yasemin & Crama, Yves & Laporte, Gilbert, 2016. "Large neighborhood search for multi-trip vehicle routing," European Journal of Operational Research, Elsevier, vol. 255(2), pages 422-441.
    11. 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.
    12. 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.
    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. Lusby, Richard Martin & Schwierz, Martin & Range, Troels Martin & Larsen, Jesper, 2016. "An Adaptive Large Neighbourhood Search Procedure Applied to the Dynamic Patient Admission Scheduling Problem," Discussion Papers on Economics 1/2016, University of Southern Denmark, Department of Economics.
    15. Iris, Çağatay & Lam, Jasmine Siu Lee, 2019. "Recoverable robustness in weekly berth and quay crane planning," Transportation Research Part B: Methodological, Elsevier, vol. 122(C), pages 365-389.
    16. Aksen, Deniz & Kaya, Onur & Sibel Salman, F. & Tüncel, Özge, 2014. "An adaptive large neighborhood search algorithm for a selective and periodic inventory routing problem," European Journal of Operational Research, Elsevier, vol. 239(2), pages 413-426.
    17. López-Ibáñez, Manuel & Dubois-Lacoste, Jérémie & Pérez Cáceres, Leslie & Birattari, Mauro & Stützle, Thomas, 2016. "The irace package: Iterated racing for automatic algorithm configuration," Operations Research Perspectives, Elsevier, vol. 3(C), pages 43-58.
    18. Bach, Lukas & Hasle, Geir & Schulz, Christian, 2019. "Adaptive Large Neighborhood Search on the Graphics Processing Unit," European Journal of Operational Research, Elsevier, vol. 275(1), pages 53-66.
    19. 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.
    20. Barrena, Eva & Canca, David & Coelho, Leandro C. & Laporte, Gilbert, 2014. "Single-line rail rapid transit timetabling under dynamic passenger demand," Transportation Research Part B: Methodological, Elsevier, vol. 70(C), pages 134-150.
    21. Fabien Lehuédé & Renaud Masson & Sophie N Parragh & Olivier Péton & Fabien Tricoire, 2014. "A multi-criteria large neighbourhood search for the transportation of disabled people," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 65(7), pages 983-1000, July.
    22. Iris, Çağatay & Pacino, Dario & Ropke, Stefan, 2017. "Improved formulations and an Adaptive Large Neighborhood Search heuristic for the integrated berth allocation and quay crane assignment problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 105(C), pages 123-147.
    23. 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.
    24. Luo, Zhixing & Qin, Hu & Zhang, Dezhi & Lim, Andrew, 2016. "Adaptive large neighborhood search heuristics for the vehicle routing problem with stochastic demands and weight-related cost," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 85(C), pages 69-89.
    25. Gilbert Laporte & Roberto Musmanno & Francesca Vocaturo, 2010. "An Adaptive Large Neighbourhood Search Heuristic for the Capacitated Arc-Routing Problem with Stochastic Demands," Transportation Science, INFORMS, vol. 44(1), pages 125-135, February.
    26. Timo Gschwind & Michael Drexl, 2019. "Adaptive Large Neighborhood Search with a Constant-Time Feasibility Test for the Dial-a-Ride Problem," Transportation Science, INFORMS, vol. 53(2), pages 480-491, March.
    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. 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. Arda, Yasemin & Cattaruzza, Diego & François, Véronique & Ogier, Maxime, 2024. "Home chemotherapy delivery: An integrated production scheduling and multi-trip vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 317(2), pages 468-486.
    3. Mancini, Simona & Gansterer, Margaretha & Triki, Chefi, 2023. "Locker box location planning under uncertainty in demand and capacity availability," Omega, Elsevier, vol. 120(C).
    4. 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.
    5. 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.
    6. Karimi-Mamaghan, Maryam & Mohammadi, Mehrdad & Pasdeloup, Bastien & Meyer, Patrick, 2023. "Learning to select operators in meta-heuristics: An integration of Q-learning into the iterated greedy algorithm for the permutation flowshop scheduling problem," European Journal of Operational Research, Elsevier, vol. 304(3), pages 1296-1330.
    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. Hrabec, Dušan & Hvattum, Lars Magnus & Hoff, Arild, 2022. "The value of integrated planning for production, inventory, and routing decisions: A systematic review and meta-analysis," International Journal of Production Economics, Elsevier, vol. 248(C).
    9. Nolz, Pamela C. & Absi, Nabil & Feillet, Dominique & Seragiotto, Clóvis, 2022. "The consistent electric-Vehicle routing problem with backhauls and charging management," European Journal of Operational Research, Elsevier, vol. 302(2), pages 700-716.

    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 & 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.
    2. 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.
    3. Yin, Jiateng & D’Ariano, Andrea & Wang, Yihui & Yang, Lixing & Tang, Tao, 2021. "Timetable coordination in a rail transit network with time-dependent passenger demand," European Journal of Operational Research, Elsevier, vol. 295(1), pages 183-202.
    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. 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. Santos, Maria João & Curcio, Eduardo & Mulati, Mauro Henrique & Amorim, Pedro & Miyazawa, Flávio Keidi, 2020. "A robust optimization approach for the vehicle routing problem with selective backhauls," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 136(C).
    8. 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).
    9. 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.
    10. Pan, Binbin & Zhang, Zhenzhen & Lim, Andrew, 2021. "Multi-trip time-dependent vehicle routing problem with time windows," European Journal of Operational Research, Elsevier, vol. 291(1), pages 218-231.
    11. Hatzenbühler, Jonas & Jenelius, Erik & Gidófalvi, Gyözö & Cats, Oded, 2023. "Modular vehicle routing for combined passenger and freight transport," Transportation Research Part A: Policy and Practice, Elsevier, vol. 173(C).
    12. 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.
    13. 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.
    14. Seokgi Lee & Mona Issabakhsh & Hyun Woo Jeon & Seong Wook Hwang & Byung Chung, 2020. "Idle time and capacity control for a single machine scheduling problem with dynamic electricity pricing," Operations Management Research, Springer, vol. 13(3), pages 197-217, December.
    15. Michael Drexl, 2018. "On the One-to-One Pickup-and-Delivery Problem with Time Windows and Trailers," Working Papers 1816, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.
    16. Hammami, Farouk & Rekik, Monia & Coelho, Leandro C., 2019. "Exact and heuristic solution approaches for the bid construction problem in transportation procurement auctions with a heterogeneous fleet," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 127(C), pages 150-177.
    17. 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.
    18. Worapot Sirirak & Rapeepan Pitakaso, 2018. "Marketplace Location Decision Making and Tourism Route Planning," Administrative Sciences, MDPI, vol. 8(4), pages 1-25, November.
    19. Mohri, Seyed Sina & Asgari, Nasrin & Zanjirani Farahani, Reza & Bourlakis, Michael & Laker, Benjamin, 2020. "Fairness in hazmat routing-scheduling: A bi-objective Stackelberg game," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 140(C).
    20. Mo, Pengli & Yao, Yu & D’Ariano, Andrea & Liu, Zhiyuan, 2023. "The vehicle routing problem with underground logistics: Formulation and algorithm," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 179(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:ejores:v:292:y:2021:i:2:p:423-442. 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.