EconPapers    
Economics at your fingertips  
 

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

Alberto Santini (alberto.santini@upf.edu), Stefan Ropke (ropke@dtu.dk) and Lars Magnus Hvattum (hvattum@himolde.no)
Additional contact information
Alberto Santini: Pompeu Fabra University and Barcelona GSE
Stefan Ropke: DTU Management Science
Lars Magnus Hvattum: Molde University College

Journal of Heuristics, 2018, vol. 24, issue 5, No 4, 783-815

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

Keywords: Adaptive large neighbourhood search; Simulated annealing; Threshold acceptance; Record-to-record travel; Vehicle routing problem; Capacitated minimum spanning tree; Quadratic assignment problem (search for similar items in EconPapers)
Date: 2018
References: Add references at CitEc
Citations: View citations in EconPapers (14)

Downloads: (external link)
http://link.springer.com/10.1007/s10732-018-9377-x 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:24:y:2018:i:5:d:10.1007_s10732-018-9377-x

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

DOI: 10.1007/s10732-018-9377-x

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 (sonal.shukla@springer.com) and Springer Nature Abstracting and Indexing (indexing@springernature.com).

 
Page updated 2024-12-29
Handle: RePEc:spr:joheur:v:24:y:2018:i:5:d:10.1007_s10732-018-9377-x