A tabu search algorithm for the split delivery vehicle routing problem

We consider the Split Delivery Vehicle Routing Problem (SDVRP) where a fleet of homogeneous vehicles has to serve a set of customers. Each customer can be visited more than once, contrary to what is usually assumed in the classical Vehicle Routing Problem (VRP) and the demand of each customer can be greater than the capacity of the vehicles. No constraint on the number of available vehicles is considered. There is a single depot for the vehicles and each vehicle has to start and end its tour at the depot. The objective is to find a set of vehicle routes that serve all the customers such that the sum of the quantity delivered in each tour does not exceed the capacity of the vehicles and the total distance travelled is minimized. The SDVRP has been introduced in the literature only few years ago by Dror and Trudeau (see [4] and [5]) who have considered the case where the demand of each customer is lower than the capacity of the vehicles. They have analyzed the savings generated by allowing split deliveries in a vehicle routing problem and they have presented a heuristic algorithm for the problem. They have also shown that when the distances satisfy the triangle inequality there exists an optimal solution for the SDVRP where no pair of tours have more than one customer in common. We study here the case where the capacity of the vehicles, as well as the demand of eac