A Composite Very Large-Scale Neighborhood Search Algorithm for the Vehicle Routing Problem

This article proposes a new heuristic, called Very Large Scale Neighborhood Search (VLSN Search) for the classical vehicle routing problem. The heuristic is a descent mechanism that explores the solution space by performing a search based on very large neighborhoods. The search mechanism allows moves in which several customers and several routes are involved. The best neighbor is determined through the solution of a network flow problem on an auxiliary graph. Computational tests indicate that the proposed heuristic is competitive with the best local search methods.