Groupe d’études et de recherche en analyse des décisions

Sequential Search and its Application to Vehicle Routing Problems

Stefan Irnich RWTH Aachen University, Allemagne

Local Search is the most widely used heuristic technique for solving combinatorial optimization problems. It is also the basis for most modern metaheuristics, like, e.g., Tabu Search, Simulated Annealing, and Variable Neighborhood Search. Most of the effort spent within a local search algorithm is used for scanning the so-called neighborhood. It is, therefore, desirable to use efficient algorithms within local search to achieve this goal. Sequential Search is a technique that allows neighborhoods within local search algorithms to be investigated in a highly efficient way. It was discovered independently in the 1970's by Christofides and Eilon and by Lin and Kernighan in algorithms for the Traveling Salesman Problem (TSP) and the Graph Partitioning Problem. Although the Lin-Kernighan algorithm and its extensions still belong to the best heuristics for solving TSPs, little attention has been paid to applying Sequential Search to other problems. This might be attributed to the fact that the definition of a Sequential Search algorithm for a given neighborhood is not a straightforward task and that the principle requires some assumptions that are not met for all kinds of problems and neighborhoods.

In this talk we give a generic description of Sequential Search and show when and how it can be applied within local search algorithms. As an example we use classical neighborhoods of the capacitated vehicle routing problem (CVRP). The CVRP is a good candidate to study, since it is more constrained than the TSP and much more difficult to solve in practice. Sequential Search is applicable to the swap neighborhood, 2-Opt, 2-Opt*, as well as the string exchange neighborhood of the CVRP. The talk also presents another technique, called Indirect Search. It allows to identify the best improving neighbor solution in the 1-1-exchange neighborhood, which is of size \(\cal{O}(n^4)\), with quadratic effort.

The superiority of Sequential and Indirect Search over straightforward approaches is not only of theoretical interest, but is essential for solving large-scale CVRP. In computational test, we observed speedups by factors between 10 and 200 compared to straightforward implementations.