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, Gilbert Laporte

Research output: Contribution to journalArticlepeer-review

28 Citations (Scopus)

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.

Original languageEnglish
Pages (from-to)752-766
Number of pages15
JournalTransportation Science
Volume49
Issue number4
DOIs
Publication statusPublished - Nov 2015

Keywords

  • Branch-price-and-cut
  • Column generation
  • Last-in-first-out loading
  • Valid inequalities
  • Vehicle routing with pickup and delivery

ASJC Scopus subject areas

  • Civil and Structural Engineering
  • Transportation

Fingerprint Dive into the research topics of 'Branch-price-and-cut algorithms for the pickup and delivery problem with time windows and last-in-first-out loading'. Together they form a unique fingerprint.

Cite this