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.