A combined approach for analysing heuristic algorithms

Jeroen Corstjens (), Nguyen Dang (), Benoît Depaire, An Caris and Patrick Causmaecker
Additional contact information
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

Journal of Heuristics, 2019, vol. 25, issue 4, No 5, 628 pages

Abstract: 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.

Keywords: Functional analysis of variance; fANOVA; Multilevel regression; Algorithm performance; Vehicle routing problem with time windows; Large neighbourhood search; Iterated local search; Unrelated parallel machine scheduling problem (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10732-018-9388-7 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joheur:v:25:y:2019:i:4:d:10.1007_s10732-018-9388-7

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10732

DOI: 10.1007/s10732-018-9388-7

Access Statistics for this article

Journal of Heuristics is currently edited by Manuel Laguna

More articles in Journal of Heuristics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().