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

Publication: Research - peer-reviewJournal article – Annual report year: 2018

DOI

View graph of relations

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.
Original languageEnglish
JournalJournal of Heuristics
Volume24
Issue number5
Pages (from-to)783-815
Number of pages33
ISSN1381-1231
DOIs
StatePublished - 2018
CitationsWeb of Science® Times Cited: 0

    Keywords

  • Adaptive large neighbourhood search, Capacitated minimum spanning tree, Quadratic assignment problem, Record-to-record travel, Simulated annealing, Threshold acceptance, Vehicle routing problem
Download as:
Download as PDF
Select render style:
APAAuthorCBE/CSEHarvardMLAStandardVancouverShortLong
PDF
Download as HTML
Select render style:
APAAuthorCBE/CSEHarvardMLAStandardVancouverShortLong
HTML
Download as Word
Select render style:
APAAuthorCBE/CSEHarvardMLAStandardVancouverShortLong
Word

ID: 153125177