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

A combined approach for analysing heuristic algorithms

Author

Listed:
  • Jeroen Corstjens

    (UHasselt, Research Group Logistics)

  • Nguyen Dang

    (KU Leuven, CODeS, imec-ITEC)

  • Benoît Depaire

    (UHasselt, Research Group Logistics)

  • An Caris

    (UHasselt, Research Group Logistics)

  • Patrick Causmaecker

    (KU Leuven, CODeS, imec-ITEC)

Abstract

When developing optimisation algorithms, the focus often lies on obtaining an algorithm that is able to outperform other existing algorithms for some performance measure. It is not common practice to question the reasons for possible performance differences observed. These types of questions relate to evaluating the impact of the various heuristic parameters and often remain unanswered. In this paper, the focus is on gaining insight in the behaviour of a heuristic algorithm by investigating how the various elements operating within the algorithm correlate with performance, obtaining indications of which combinations work well and which do not, and how all these effects are influenced by the specific problem instance the algorithm is solving. We consider two approaches for analysing algorithm parameters and components—functional analysis of variance and multilevel regression analysis—and study the benefits of using both approaches jointly. We present the results of a combined methodology that is able to provide more insights than when the two approaches are used separately. The illustrative case studies in this paper analyse a large neighbourhood search algorithm applied to the vehicle routing problem with time windows and an iterated local search algorithm for the unrelated parallel machine scheduling problem with sequence-dependent setup times.

Suggested Citation

  • Jeroen Corstjens & Nguyen Dang & Benoît Depaire & An Caris & Patrick Causmaecker, 2019. "A combined approach for analysing heuristic algorithms," Journal of Heuristics, Springer, vol. 25(4), pages 591-628, October.
    • Handle: RePEc:spr:joheur:v:25:y:2019:i:4:d:10.1007_s10732-018-9388-7
    DOI: 10.1007/s10732-018-9388-7
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10732-018-9388-7
    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-9388-7?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. 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.
    2. Vallada, Eva & Ruiz, Rubén, 2011. "A genetic algorithm for the unrelated parallel machine scheduling problem with sequence dependent setup times," European Journal of Operational Research, Elsevier, vol. 211(3), pages 612-622, June.
    3. Dimitris J. Bertsimas & David Simchi-Levi, 1996. "A New Generation of Vehicle Routing Research: Robust Algorithms, Addressing Uncertainty," Operations Research, INFORMS, vol. 44(2), pages 286-304, April.
    4. Marius M. Solomon, 1987. "Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints," Operations Research, INFORMS, vol. 35(2), pages 254-265, April.
    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. Véronique François & Yasemin Arda & Yves Crama, 2019. "Adaptive Large Neighborhood Search for Multitrip Vehicle Routing with Time Windows," Transportation Science, INFORMS, vol. 53(6), pages 1706-1730, November.
    2. Justin C. Goodson & Barrett W. Thomas & Jeffrey W. Ohlmann, 2016. "Restocking-Based Rollout Policies for the Vehicle Routing Problem with Stochastic Demand and Duration Limits," Transportation Science, INFORMS, vol. 50(2), pages 591-607, May.
    3. Jian Yang & Patrick Jaillet & Hani Mahmassani, 2004. "Real-Time Multivehicle Truckload Pickup and Delivery Problems," Transportation Science, INFORMS, vol. 38(2), pages 135-148, May.
    4. Soriano, Adria & Vidal, Thibaut & Gansterer, Margaretha & Doerner, Karl, 2020. "The vehicle routing problem with arrival time diversification on a multigraph," European Journal of Operational Research, Elsevier, vol. 286(2), pages 564-575.
    5. de Castro Pena, Guilherme & Santos, Andréa Cynthia & Prins, Christian, 2023. "Solving the integrated multi-period scheduling routing problem for cleaning debris in the aftermath of disasters," European Journal of Operational Research, Elsevier, vol. 306(1), pages 156-172.
    6. Pillac, Victor & Gendreau, Michel & Guéret, Christelle & Medaglia, Andrés L., 2013. "A review of dynamic vehicle routing problems," European Journal of Operational Research, Elsevier, vol. 225(1), pages 1-11.
    7. 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.
    8. Said Dabia & Stefan Ropke & Tom van Woensel & Ton De Kok, 2013. "Branch and Price for the Time-Dependent Vehicle Routing Problem with Time Windows," Transportation Science, INFORMS, vol. 47(3), pages 380-396, August.
    9. Q Mu & Z Fu & J Lysgaard & R Eglese, 2011. "Disruption management of the vehicle routing problem with vehicle breakdown," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 62(4), pages 742-749, April.
    10. Zhi-Long Chen & Hang Xu, 2006. "Dynamic Column Generation for Dynamic Vehicle Routing with Time Windows," Transportation Science, INFORMS, vol. 40(1), pages 74-88, February.
    11. Li, Jing-Quan & Mirchandani, Pitu B. & Borenstein, Denis, 2009. "Real-time vehicle rerouting problems with time windows," European Journal of Operational Research, Elsevier, vol. 194(3), pages 711-727, May.
    12. Justin C. Goodson & Jeffrey W. Ohlmann & Barrett W. Thomas, 2013. "Rollout Policies for Dynamic Solutions to the Multivehicle Routing Problem with Stochastic Demand and Duration Limits," Operations Research, INFORMS, vol. 61(1), pages 138-154, February.
    13. Yi-Kuei Lin & Cheng-Fu Huang & Yi-Chieh Liao, 2019. "Reliability of a stochastic intermodal logistics network under spoilage and time considerations," Annals of Operations Research, Springer, vol. 277(1), pages 95-118, June.
    14. Filippo Focacci & Andrea Lodi & Michela Milano, 2002. "A Hybrid Exact Algorithm for the TSPTW," INFORMS Journal on Computing, INFORMS, vol. 14(4), pages 403-417, November.
    15. Asghari, Mohammad & Jaber, Mohamad Y. & Mirzapour Al-e-hashem, S.M.J., 2023. "Coordinating vessel recovery actions: Analysis of disruption management in a liner shipping service," European Journal of Operational Research, Elsevier, vol. 307(2), pages 627-644.
    16. Alex Gliesch & Marcus Ritt, 2022. "A new heuristic for finding verifiable k-vertex-critical subgraphs," Journal of Heuristics, Springer, vol. 28(1), pages 61-91, February.
    17. Zhang, Ying & Qi, Mingyao & Miao, Lixin & Liu, Erchao, 2014. "Hybrid metaheuristic solutions to inventory location routing problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 70(C), pages 305-323.
    18. Carolina G. Marcelino & João V. C. Avancini & Carla A. D. M. Delgado & Elizabeth F. Wanner & Silvia Jiménez-Fernández & Sancho Salcedo-Sanz, 2021. "Dynamic Electric Dispatch for Wind Power Plants: A New Automatic Controller System Using Evolutionary Algorithms," Sustainability, MDPI, vol. 13(21), pages 1-20, October.
    19. Dung-Ying Lin & Tzu-Yun Huang, 2021. "A Hybrid Metaheuristic for the Unrelated Parallel Machine Scheduling Problem," Mathematics, MDPI, vol. 9(7), pages 1-20, April.
    20. Nicolas Rincon-Garcia & Ben J. Waterson & Tom J. Cherrett, 2018. "Requirements from vehicle routing software: perspectives from literature, developers and the freight industry," Transport Reviews, Taylor & Francis Journals, vol. 38(1), pages 117-138, January.

    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:25:y:2019:i:4:d:10.1007_s10732-018-9388-7. 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.