Heuristic methods for the fleet size and mix vehicle routing problem with time windows and split deliveries

This paper proposes a scatter-search (SS) approach to solve the Fleet Size and Mixed Vehicle Routing Problem with Time Windows and Split Deliveries (FSMVRPTWSD). In the Vehicle Routing Problem with Split Deliveries (VRPSD), each customer can be served by more than one vehicle, as opposed to the classical VRP in which each customer is served only once. In the FSMVRPTW, the customers must be serviced within their time windows with minimal costs using a heterogeneous fleet. Experimental testing and benchmark examples are used to assess the merit of our proposed procedure. The results show that the proposed heuristics are competitive with the best results found in the literature.

► This paper studies the FSMVRPTWSD.
► The FSMVRPTW considers time windows and a heterogeneous fleet.
► In the VRPSD customers can be served by more than one vehicle.
► We propose a scatter search approach to solve the FSMVRPTWSD.
► Our algorithm is competitive with the best results found in the literature.