Column Generation for the Split Delivery VRP

In this paper we tackle a variation of the Vehicle Routing Problem (VRP) in which each customer can be served by more than one vehicle, each serving a fraction of its demand. This problem is known as the Split Delivery VRP (SDVRP). Due to the potential savings that can be achieved in this way, the SDVRP recently received great attention in the combinatorial optimization community. We propose a new extended formulation for the problem. We exploit its properties to derive an effective column generation scheme. Our method is compared to the previous ones in the literature from both a theoretical and a computational point of view. In particular, our formulation involves a polynomial number of constraints and flow variables, can be optimized by solving well understood resource constrained shortest path problems and yields a bound which is not dominated by any previous one in the literature.

Presented at:
Column Generation 2008, Aussois, France, June 19, 2008

 Record created 2009-06-15, last modified 2018-03-17

Download fulltextPDF
External link:
Download fulltextURL
Rate this document:

Rate this document:
(Not yet reviewed)