A Compact Arc-Based ILP Formulation for the Pickup and Delivery Problem with Divisible Pickups and Deliveries

Bolor Jargalsaikhan (), Ward Romeijnders () and Kees Jan Roodbergen ()
Additional contact information
Bolor Jargalsaikhan: Department of Operations, Faculty of Economics and Business, University of Groningen, 9747 AE Groningen, Netherlands
Ward Romeijnders: Department of Operations, Faculty of Economics and Business, University of Groningen, 9747 AE Groningen, Netherlands
Kees Jan Roodbergen: Department of Operations, Faculty of Economics and Business, University of Groningen, 9747 AE Groningen, Netherlands

Transportation Science, 2021, vol. 55, issue 2, 336-352

Abstract: We consider the capacitated single vehicle one-to-one pickup and delivery problem with divisible pickups and deliveries (PDPDPD). In this problem, we do not make the standard assumption of one-to-one pickup and delivery problems (PDPs) that each location has only one transportation request. Instead we assume there are multiple requests per location that may be performed individually. This may result in multiple visits to a location. We provide a new compact arc-based integer linear programming (ILP) formulation for the PDPDPD by deriving time-consistency constraints that identify the order in which selected outgoing arcs from a node are actually traversed. The formulation can also easily be applied to the one-to-one PDP by restricting the number of times that a node can be visited. Numerical results on standard one-to-one PDP test instances from the literature show that our compact formulation is almost competitive with tailor-made solution methods for the one-to-one PDP. Moreover, we observe that significant cost savings of up to 15% on average may be obtained by allowing divisible pickups and deliveries in one-to-one PDPs. It turns out that divisible pickups and deliveries are not only beneficial when the vehicle capacity is small, but also when this capacity is unrestrictive.

Keywords: integer linear program; pickup and delivery problem; divisible pickups and deliveries (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1287/trsc.2020.1016 (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:ortrsc:v:55:y:2021:i:2:p:336-352

Access Statistics for this article

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