Branch-Price-and-Cut Algorithms for the Pickup and Delivery Problem with Time Windows and Last-in-First-Out Loading

Marilène Cherkesly (), Guy Desaulniers () and Gilbert Laporte ()
Additional contact information
Marilène Cherkesly: École Polytechnique de Montréal, Montréal, Quebec H3T 1J4, Canada; and GERAD, Montréal, Quebec H3T 2A7, Canada
Guy Desaulniers: École Polytechnique de Montréal, Montréal, Quebec H3T 1J4, Canada; and GERAD, Montréal, Quebec H3T 2A7, Canada
Gilbert Laporte: HEC Montréal, Montréal, Quebec H3T 2A7, Canada; CIRRELT, Montréal, Quebec H3T 1J4, Canada; and GERAD, Montréal, Quebec H3T 2A7, Canada

Transportation Science, 2015, vol. 49, issue 4, 752-766

Abstract: This paper proposes models and algorithms for the pickup and delivery vehicle routing problem with time windows and last-in-first-out (LIFO) loading constraints (PDPTWL). The LIFO loading rule ensures that no handling is required prior to unloading an item from a vehicle: a linear stack loading structure is maintained and an item can only be delivered if it is the last one in the stack. Three exact branch-price-and-cut algorithms are proposed for this problem. The first incorporates the LIFO constraints in the master problem. The second one handles the LIFO constraints directly in the shortest path pricing problem. It applies a dynamic programming algorithm relying on an ad hoc dominance criterion. The third algorithm is a hybrid between the first two methods. Known valid inequalities are adapted to the PDPTWL and the impact of different path relaxations on the total computation time is investigated. Computational results obtained on instances derived from known instances of the pickup and delivery problem with time windows (PDPTW) are reported.

Keywords: vehicle routing with pickup and delivery; last-in-first-out loading; column generation; branch-price-and-cut; valid inequalities (search for similar items in EconPapers)
Date: 2015
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (17)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.2014.0535 (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:49:y:2015:i:4:p:752-766

Access Statistics for this article

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