Inter-depot moves and dynamic-radius search for multi-depot vehicle routing problems

Abstract

Dynamic-radius search, formerly known as sequential search, is an effective neighborhood exploration technique for standard edge-exchange neighborhoods such as 2-opt, 2-opt*, swap, relocation, Or-opt, string exchange, etc. Up to now, it has only been used for vehicle routing problems with a homogeneous fleet and in the single-depot context. In this work, we extend dynamic-radius search to the multi-depot vehicle routing problem, in which 2-opt and 2-opt* moves may involve routes from different depots. To this end, we equip dynamic-radius search with a modified pruning criterion that still guarantees to identify a best-improving move, either intra-depot or inter-depot, with little additional computational effort. We experimentally confirm that substantial speedups of factors of 100 and more are achieved compared to an also optimized implementation of lexicographic search, another effective neighborhood exploration technique using a feasibility-based pruning criterion. As one would expect, better local optima are found on average when allowing inter-depot moves in radius search (positive result). Against intuition, we do however not end up with a better ILS metaheuristic regarding best found solutions, i.e., better average results do not translate into better overall results. We can at least partly explain the latter negative result, which might be useful for other researchers and their attempt to algorithmically optimize their neighborhood exploration procedures.