A compact arc-based ILP formulation for the pickup and delivery problem with divisible pickups and deliveries

Bolor Jargalsaikhan, Ward Romeijnders, K.J. Roodbergen

Research output: Contribution to journalArticleAcademicpeer-review

89 Downloads (Pure)

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 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 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 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.
Original languageEnglish
Pages (from-to)336-352
Number of pages17
JournalTransportation Science
Volume55
Issue number2
Early online date28-Jan-2021
DOIs
Publication statusPublished - Mar-2021

Keywords

  • Integer Linear Program, Pickup and Delivery Problem, Divisible Pickups and Deliveries

Cite this