Split Delivery VRP (SDVRP)

The SDVRP is a relaxation of the VRP in which the same customer may be served by different vehicles if doing so reduces the overall cost. This relaxation is especially valuable when the size of a customer order is comparable to the capacity of a vehicle: splitting large orders between routes can save vehicles and travel distance.

In [DLT94] it is concluded that obtaining the optimal solution of the SDVRP is more difficult than for the standard VRP: splitting deliveries enlarges the solution space and removes the "each customer visited exactly once" structure exploited by many search methods.

Formal description

• Objective: minimize the vehicle fleet and the sum of the travel time needed to supply all customers.
• Feasibility: a solution is feasible if all constraints of the 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 an SDVRP is to allow split deliveries by dividing each customer order into a number of smaller indivisible orders [Burrows 1988].

See also: VRP formulation · Capacitated VRP · SDVRP instances