A Subpath Ejection Method for the Vehicle Routing Problem

Generically, ejection chains are methods conceived to allow solution transformations to be efficiently carried out by modifying a variable number of their components at each step of a local search algorithm. We consider a subpath ejection chain method for the vehicle routing problem (VRP) under capacity and route length restrictions. The method undertakes the identification of a substructure named the flower reference structure which, besides coordinating moves during an ejection chain construction, allows the creation of neighborhood structures with interesting combinatorial characteristics. Specifically, we base the method on a fundamental property of creating alternating paths and cycles during an ejection chain construction. A new algorithm based on a Tabu search framework is proposed, and computational results on a set of academic and real-world problems indicate that the algorithm may be a good alternative to the best heuristic algorithms for the VRP.