A New Heuristic for the Fleet Size and Mix Vehicle Routing Problem

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.