Fast Local Search in Vehicle Routing

We consider several strategies for the efficient implementation of Static Move Descriptors (SMDs), a recently developed technique that significantly speeds up Local Search-based algorithms. SMDs exploit the fact that each local search step affects only a small part of the solution and allow for efficient tracking of changes at each iteration, such that unnecessary reevaluations can be avoided. Despite its significant advantages, the design proposed in the literature suffers from high overhead and considerable implementation difficulty. We developed a simpler implementation that offers better extendibility and significant further speedups of local search algorithms. We also explore the hybridization of SMD with the granular sparsification concept to achieve a possibly better computational efficiency. We experimentally evaluate our findings by applying them to the Capacitated Vehicle Routing Problem (CVRP).