Branch and Price for the Vehicle Routing Problem with Discrete Split Deliveries and Time Windows

The Discrete Split Delivery Vehicle Routing Problem with Time Windows (DSDVRPTW) consists of designing the optimal set of routes to serve, at least cost, a given set of customers while respecting constraints on vehicles capacity and customer time windows. The delivery request of a customer is discrete since it consists of several items that cannot be split further. The problem belongs to the class of split delivery problems since each customers demand can be split in orders, i.e. feasible combinations of items, and each customer can be visited by more than one vehicle. In this work, we model the DSDVRPTW assuming that all feasible orders are known in advance and that each vehicle can serve at most one order per customer. Remarkably, service time at customers location depends on the serviced combination of items, which is a modeling feature rarely found in literature. We present a mixed integer program for the DSDVRPTW based on arc-flow formulation, we reformulate it via Dantzig-Wolfe and we apply column generation. We propose a branch-and-price algorithm, implemented using state-of-the-art techniques for the pricing and the master problem. Computational results on instances based on Solomons data set are presented and discussed