SDVRP is a relaxation of the VRP wherein it is allowed that the same customer can be served by different vehicles if it reduces overall costs. This relaxation is very important if the sizes of the customer orders are as big as the capacity of a vehicle.

In [DLT94] it is concluded that it is more difficult to obtain the optimal solution in the SDVRP that in the VRP.

Objective

The objective is to minimize the vehicle fleet and the sum of travel time needed to supply all customers.

Feasibility

A solution is feasible if all constraints of VRP are satisfied except that a customer may be supplied by more than one vehicle.

Formulation

Minimize the sum of the cost of all routes. An easy way to transform a VRP into a SDVRP consists on allowing split deliveries by splitting each customer order into a number of smaller indivisible orders [Burrows 1988].