In this paper, we address the problem of routing a fleet of vehicles from a central depot to customers with known demands. We consider the classical vehicle routing problem (VRP), where the vehicles are identical. The objective is to find a set of routes with the least total travel costs. We present a new savings heuristic, based on the weighted matching problem. The maximum weight matching enable to choose the route fusion in a non-myopic way. Computational results are provided for a number of known problems in order to compare the performance of the different methods.
Paru en janvier 1989 , 19 pages
Ce cahier a été révisé en août 1989