The pickup and delivery problem with time windows and handling operations

Marjolein Veenstra, Marilène Cherkesly, Guy Desaulniers, Gilbert Laporte

Research output: Contribution to journalArticlepeer-review

19 Citations (Scopus)

Abstract

This paper introduces the pickup and delivery problem with time windows and handling operations. In this problem, the loading compartment of a vehicle is modeled as a linear LIFO stack. When an item is picked up, it is positioned on top of the stack. When it is on top of the stack, it can be delivered without additional handling. Otherwise, items on top must be unloaded before the delivery and reloaded afterwards, which requires time. We define two rehandling policies. For both policies, rehandling is only allowed at delivery locations and there is no specific reloading order for the rehandled items. Under the first policy, only compulsory rehandling is allowed. Under the second policy, in addition to compulsory rehandling, preventive rehandling is allowed. For each policy, we propose a branch-price-and-cut algorithm with an ad hoc dominance criterion for the labeling algorithm used to generate routes. Computational results are reported on benchmark instances for the pickup and delivery problem with time windows.

Original languageEnglish
Pages (from-to)127-140
Number of pages14
JournalComputers and Operations Research
Volume77
DOIs
Publication statusPublished - 1 Jan 2017

Keywords

  • Branch-price-and-cut
  • Column generation
  • Handling operations
  • Valid inequalities
  • Vehicle routing with pickups and deliveries

ASJC Scopus subject areas

  • Computer Science(all)
  • Modelling and Simulation
  • Management Science and Operations Research

Fingerprint Dive into the research topics of 'The pickup and delivery problem with time windows and handling operations'. Together they form a unique fingerprint.

Cite this