A new heuristic for the fleet size and mix vehicle routing problem

In this paper the authors address the problem of simultaneously selecting the composition and routing of a fleet of vehicles in order to service efficiently 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. The authors present a new savings heuristic based on successive route fusion. At each iteration, the best fusion is selected by solving a weighted matching problem. This provides a less myoptic criteria than the usual savings heuristics. This algorithm is also very easy to implement. Computational results are provided for a number of bench mark problems in order to compare its performance to that of various other methods.