The Shrinking and Expanding Heuristic for the Fleet Size and Mix Vehicle Routing Problem

Abstract

The FSMVRP (Fleet Size and Mix Vehicle Routing Problem) is a variant of the classical Capacitated Vehicle Routing Problem, CVRP. We suggest a new methodology, called the Shrinking and Expanding Heuristic (SEH) which is incorporated in a standard tabu search. To determine an appropriate fleet mix is a major challenge in this type of problem and the SEH technique is especially developed to find a good combination of vehicles by introducing a mechanism for changing the existing fleet mix during the search, thus also changing the underlying route structure. The SEH utilizes the concept of depletion and expansion of routes depending upon the filling degree of a vehicle. This strategy is tested on standard problem instances and good quality solutions are obtained.