A Unified Branch-Price-and-Cut Algorithm for Multicompartment Pickup and Delivery Problems

Marjolein Aerts-Veenstra (), Marilène Cherkesly () and Timo Gschwind ()
Additional contact information
Marjolein Aerts-Veenstra: Department of Operations, Faculty of Economics and Business, University of Groningen, 9747 AJ Groningen, Netherlands
Marilène Cherkesly: Département d’analytique, opérations et technologies de l’information, Université du Québec à Montréal and GERAD, Montréal, Québec H3C 3P8, Canada
Timo Gschwind: School of Business and Economics, RPTU Kaiserslautern-Landau, 67663 Kaiserslautern, Germany

Transportation Science, 2024, vol. 58, issue 5, 1121-1142

Abstract: In this paper, we study the pickup and delivery problem with time windows and multiple compartments (PDPTWMC). The PDPTWMC generalizes the pickup and delivery problem with time windows to vehicles with multiple compartments. In particular, we consider three compartment-related attributes: (1) compartment capacity flexibility that allows the capacities of the compartments to be fixed or flexible, (2) item-to-compartment flexibility that specifies which items are compatible with which compartments, and (3) item-to-item compatibility that considers that incompatible items cannot be simultaneously in the same compartment. To solve the PDPTWMC, we propose an exact branch-price-and-cut algorithm in which the pricing problem is solved by means of a unified bidirectional labeling algorithm. The labeling algorithm can tackle all possible combinations of the studied compartment-related attributes of the PDPTWMC. Furthermore, we implement several acceleration techniques that allow to, among others, reduce the symmetry in the label extensions with empty compartments, the symmetry in the dominance between compartments with similar attributes, and the complexity of the algorithm with fixed compartment capacity. Finally, we introduce benchmark instances for the PDPTWMC and conduct an extensive computational campaign to test the limits of our algorithm and to derive relevant managerial insights in order to highlight the applicability of considering the studied compartment-related attributes.

Keywords: vehicle routing with pickup and delivery; multiple compartments; flexible capacity; item incompatibility; column generation; branch-price-and-cut (search for similar items in EconPapers)
Date: 2024
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.2023.0252 (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:58:y:2024:i:5:p:1121-1142

Access Statistics for this article

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