|
A composite very large-scale neighborhood search algorithm for the vehicle routing problem R. Agarwal, R.K. Ahuja, G. Laporte, and Z.J. Shen, Handbook of Scheduling: Algorithms, Models and Performance Analysis. Edited by J. Y-T. Leung, Chapman & Hall/CRC, pp. 49-01 to 49-23. 2003 This chapter 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. |