Premium
Evaluating the importance of randomization in adaptive large neighborhood search
Author(s) -
Hemmati Ahmad,
Hvattum Lars Magnus
Publication year - 2017
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/itor.12273
Subject(s) - randomization , computer science , variance (accounting) , mathematical optimization , implementation , metaheuristic , randomized algorithm , component (thermodynamics) , randomized experiment , randomized controlled trial , mathematics , algorithm , statistics , medicine , physics , surgery , accounting , programming language , business , thermodynamics
Randomization is common in many implementations of metaheuristics, and is typically a main ingredient while considering adaptive large neighborhood search (ALNS). This paper considers a standard implementation of ALNS for maritime pickup and delivery problems, identifies seven randomized components in that implementation, and proposes and analyzes simple nonrandomized alternatives to those components. The results reveal that the randomized alternatives perform slightly better for one of seven components, the deterministic alternatives perform better for one component, while the randomized and deterministic alternatives have similar performance for the remaining five components. When analyzing runs with different initial solutions, there seems to be a larger variance in the results obtained with only randomized components, compared to the results with only deterministic components, even when the average results are similar.