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

36 Citations (SciVal)

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

Funding

This project was funded by the Dutch Institute for Advanced Logistics (Dinalog) and by the Canadian Natural Sciences and Engineering Research Council under grants 157935-2012 and 2015-06189 . This support is gratefully acknowledged. The authors are thankful to François Lessard for his valuable advice. Thanks are due to the referees for their valuable comments.

Keywords

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

ASJC Scopus subject areas

  • General Computer Science
  • 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