Designing granular solution methods for routing problems with time windows

The use of granular neighborhoods is one way to improve the run-time of local-search-based metaheuristics for combinatorial optimization problems without compromising solution quality. So-called sparsification methods are applied to restrict the neighborhoods to include only elements which are likely to be part of high-quality solutions. The goal of this work is to provide insights about the design of effective and efficient granular solution methods for routing problems with time windows. In extensive numerical experiments with a granular tabu search (GTS) for the vehicle-routing problem with time windows (VRPTW), we find that sparsification methods using reduced-cost values based on the solution of a linear relaxation of the original problem outperform standard sparsification methods. Furthermore, including additional depot arcs into the restricted arc set (beyond those selected by the sparsification method) improves solution quality. The same is true for dynamically inserting into the restricted arc set (i) the arcs involved in the best move selected in each iteration, and (ii) the arcs of the current best-known solution. Moreover, for small restricted arc sets, guaranteeing a minimum number of incoming and outgoing arcs per vertex is beneficial. Finally, dynamically altering the size of the restricted arc set can be used to successfully diversify and intensify the search, which has a significant positive effect on solution quality. The usefulness of the gained insights about the design of granular solution methods is demonstrated by the performance of the final configuration of our GTS for VRPTW, which obtains state-of-the-art results and reaches an outstanding computational efficiency.