A review and ranking of operators in adaptive large neighborhood search for vehicle routing problems

Kurzfassung/Abstract

This article systematically reviews the literature on adaptive large neighborhood search (ALNS) to gain insights into the operators used for vehicle routing problems (VRPs) and their effectiveness. The ALNS has been successfully applied to a variety of optimization problems, particularly variants of the VRP. The ALNS gradually improves an initial solution by modifying it using removal and insertion operators. However, relying solely on adaptive operator selection is not advisable. Instead, authors often conduct experiments to identify operators that improve the solution quality or remove detrimental ones. This process is mostly cumbersome due to the wide variety of operators, further complicated by inconsistent nomenclature. The objectives of this review are threefold: First, to classify ALNS operators using a unified terminology; second, to analyze their performance; and third, to present guidelines for the development and analysis of ALNS algorithms in the future based on the outcomes of the performance evaluation. In this review, we conduct a network meta-analysis of 211 articles published between 2006 and 2023 that have applied ALNS algorithms in the context of VRPs. We employ incomplete pairwise comparison matrices, similar to rankings used in sports, to rank the operators. We identify 57 distinct removal and 42 insertion operators, and the analysis ranks them based on their effectiveness. Sequence-based removal operators, which remove sequences of customers in the current solution, are found to be the most effective. The best-performing insertion operators are those that exhibit foresight, such as regret insertion operators. Finally, guidelines and possible future research directions are discussed.