Evaluating the importance of randomization in adaptive large neighborhood search

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.