Branch and price for the vehicle routing problem with discrete split deliveries and time windows

Matteo Salani and Ilaria Vacca

European Journal of Operational Research, 2011, vol. 213, issue 3, 470-477

Abstract: 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. Each customer can be visited by more than one vehicle since each customer's demand, discretized in items, can be split in orders, i.e., feasible combinations of items. In this work, we model the DSDVRPTW assuming that all feasible orders are known in advance. Remarkably, service time at customer's location depends on the delivered combination of items, which is a modeling feature rarely found in literature. We present a flow-based mixed integer program for the DSDVRPTW, we reformulate it via Dantzig-Wolfe and we apply column generation. The proposed branch-and-price algorithm largely outperforms a commercial solver, as shown by computational experiments on Solomon-based instances. A comparison in terms of complexity between constant service time vs delivery-dependent service time is presented and potential savings are discussed.

Keywords: Vehicle; routing; Split; delivery; Column; generation; Dantzig-Wolfe; decomposition; Branch; and; price (search for similar items in EconPapers)
Date: 2011
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (42)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221711002347
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:213:y:2011:i:3:p:470-477

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().