G-89-05
A New Heuristic for the Fleet Size and Mix Vehicle Routing Problem
Martin Desrochers et TW Verhoog
In this paper we address the problem of simultaneously selecting the composition and routing of a fleet of vehicles in order to efficiently service customers with known demands from a central depot. This problem is called the fleet size and mix vehicle routing problem (FSMVRP). The vehicle fleet may be heterogeneous. The objective is to find the fleet composition and a set of routes with minimum total cost, which includes routing cost and vehicle cost. We present a new savings heuristic based on successive route fusion. At each iteration, the bestfusion is selected by solving a weighted matching problem. This provides a less myopic criteria than the usual savings heuristics. This algorithm is also very easy to implement. Computational results are provided for a number of benchmark problems in order to compare its performance to that of various other methods.
Paru en janvier 1989 , 22 pages
Ce cahier a été révisé en mai 1990