Non-Elementary Formulations for Single Vehicle Routing Problems with Pickups and Deliveries

Bruno P. Bruck () and Manuel Iori ()
Additional contact information
Bruno P. Bruck: Department of Sciences and Methods for Engineering, University of Modena and Reggio Emilia, 42122 Reggio Emilia, Italy
Manuel Iori: Department of Sciences and Methods for Engineering, University of Modena and Reggio Emilia, 42122 Reggio Emilia, Italy

Operations Research, 2017, vol. 65, issue 6, 1597-1614

Abstract: We study the class of one-to-many-to-one single vehicle routing problems with pickups and deliveries, in which a single capacitated vehicle is used to serve a set of customers requiring a delivery, a pickup, or both. These problems have many real-world applications, including beverage distribution, courier service transportation, and reverse logistics. We first concentrate on a well-studied problem in this class, known as the single vehicle routing problem with deliveries and selective pickups (SVRPDSP), in which deliveries are mandatory but pickups are optional and generate a revenue if performed, and customers requiring both a delivery and a pickup (combined demand) can be visited either once or twice. Most exact algorithms in the literature solve SVRPDSP by looking for elementary tours on an extended network that is obtained by transforming each combined demand customer into two different customers, one requiring only the delivery and the other one only the pickup. Because this can result in a significant loss in performance, in this work we focus instead on the original problem network and present formulations that can yield non-elementary tours. Through the use of Benders decomposition, valid inequalities, and tailored optimization techniques based on branch-and-cut frameworks, we develop exact algorithms that outmatch previous results in the literature and obtain proven optimal solutions for all benchmark instances. We then generalize the algorithms to solve several other vehicle routing problems with pickups and deliveries, including the cases of split deliveries, intermediate drop-offs, mandatory pickups, and multiple vehicles.

Keywords: pickup and delivery; one-to-many-to-one; selective pickups; valid inequalities; branch-and-cut (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (13)

Downloads: (external link)
https://doi.org/10.1287/opre.2017.1639 (application/pdf)

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:inm:oropre:v:65:y:2017:i:6:p:1597-1614

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().