Fast Ejection Chain Algorithms for Vehicle Routing with Time Windows

This paper introduces new ejection chain strategies to effectively target vehicle routing problems with time window constraints (VRPTW). Ejection chain procedures are based on the idea of compound moves that allow a variable number of solution components to be modified within any single iteration of a local search algorithm. The yardstick behind such procedures is the underlying reference structure, which is the structure that is used to coordinate the moves that are available for the local search algorithm. The main contribution of the paper is a new reference structure that is particularly suited in order to handle the asymmetric aspects in a VRPTW. The new reference structure is a generalization of the doubly rooted reference structure introduced by Glover, resulting in a new, powerful neighborhood for the VRPTW. We use tabu search for the generation of the ejection chains. On a higher algorithmic level, we study the effect of different meta heuristics to steer the tabu chain ejection process. Computational results confirm that our approach leads to very fast algorithms that can compete with the current state of the art algorithms for the VRPTW.