The Vehicle Routing Problem with Discrete Split Delivery 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 consists of several discrete items which 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 as a mixed integer linear program, 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 branch-and-price algorithm, analyzing the implications of the classical Dantzig-Wolfe reformulation. Preliminary computational results on instances based on Solomons data set are discussed.
VaccSala09_STRC.pdf
openaccess
221.86 KB
Adobe PDF
e724317cd39d7033640c0661831d4896