An Exact Algorithm for the Pickup and Delivery Problem with Time Windows and Last-in-First-out Loading

Ali Mehsin Alyasiry (), Michael Forbes () and Michael Bulmer ()
Additional contact information
Ali Mehsin Alyasiry: School of Mathematics and Physics, Faculty of Science, University of Queensland, St. Lucia, Brisbane, Australia
Michael Forbes: School of Mathematics and Physics, Faculty of Science, University of Queensland, St. Lucia, Brisbane, Australia
Michael Bulmer: School of Mathematics and Physics, Faculty of Science, University of Queensland, St. Lucia, Brisbane, Australia

Transportation Science, 2019, vol. 53, issue 6, 1695-1705

Abstract: Applications of the pickup and delivery problem with time windows and last-in-first-out (LIFO) loading (PDPTWL) constraints can be found in the transportation of animals, heavyweight goods, and hazardous materials, where unloading vehicles requires more time and special handling. Examples include carrying livestock, cars, and chemical containers. Research on exact methods to solve the pickup and delivery problem with time windows (PDPTW) and its variants has mainly focused on branch-and-price-and-cut algorithms. In this paper, we propose a novel exact approach based on fragments— a series of pickup and delivery requests starting and ending with an empty vehicle. We use fragments to formulate a relaxed network flow model with side constraints. Lazy constraints are used to cut off any illegal solution that may occur while solving the integer program. Extensive computational experiments show that the proposed approach is superior to the current state-of-the-art method.

Keywords: vehicle routing; pickup and delivery; LIFO loading constraints; exact; lazy constraints (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (11)

Downloads: (external link)
https://doi.org/10.1287/trsc.2019.0905 (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:53:y:2019:i:6:p:1695-1705

Access Statistics for this article

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