The Split Delivery Vehicle Routing Problem

Consider a set of customers that need to be served by means of an unlimited fleet of identical capacitated vehicles that start and end their routes at a depot. Each customer may be visited by several vehicles if beneficial, that is, split deliveries are allowed. The Split Delivery Vehicle Routing Problem (SDVRP) is the problem of finding a set of routes that minimizes the total traveling cost. In the SDVRP, the traditional assumption made in the Vehicle Routing Problem (VRP) that each customer is visited only once is relaxed.

The SDVRP was formally introduced by Dror and Trudeau (1989, 1990) and has received increasing attention over time. Some properties of the problem and complexity results have been proved. Moreover, the maximum saving that can be achieved by split deliveries has been studied. Heuristic and exact solution algorithms have been proposed. The SDVRP is a very challenging problem that at present can be solved to optimality in a systematic way only on instances with less than 30 customers.