The pickup and delivery problem with time windows and handling operations. (January 2017)

• Record Type: Journal Article
• Authors: Veenstra, Marjolein; Cherkesly, Marilène; Desaulniers, Guy; Laporte, Gilbert
• Is Part Of: Computers & operations research. Volume 77(2017)
• Page Start: 127
• Page End: 140
• Publication Date: 2017-01
• Subjects: Vehicle routing with pickups and deliveries -- Handling operations -- Column generation -- Branch-price-and-cut -- Valid inequalities; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2016.07.014
• Languages: English
• ISSNs: 0305-0548

Abstract

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. Abstract : Highlights: We study the pickup and delivery problem with time windows and handling operations. We define two handling policies with compulsory and preventive handling. Branch-price-and-cut algorithms with ad hoc dominance criteria are presented. Computational results are reported on pickup and delivery benchmark instances.