Back to activities
“Meet a GERAD researcher!” seminar

A branch-price-and-cut algorithm for multi-compartment pickup and delivery problems


Sep 27, 2023   11:00 AM — 12:00 PM

Marilène Cherkesly Associate Professor, Department of Analytics, Operations and Information Technology, Université du Québec à Montréal, Canada

Marilène Cherkesly

To have access to the presentation, please contact Marilène Cherkesly to obtain the link.

The pickup and delivery with multiple compartments (PDPMC) generalizes multi-compartment vehicle routing problems in the context of pickup and delivery (PDP). In that problem, items must be transported from a pickup location to a delivery location using a set of vehicles with limited capacity and with compartment loading spaces (compartments). Three compartment-related attributes are studied: 1) compartment capacity flexibility which allows the capacities of the compartments to be fixed or flexible, 2) item-to-compartment flexibility which allows some items to be compatible (or not) with some compartments, and 3) as item-to-item incompatibility which allows items to be incompatible, and incompatible items cannot be loaded simultaneously in the same compartment. These attributes generalize three important compartment-related attributes studied in the vehicle-routing setting to the PDP, i.e., 1) the flexibility of compartment sizes, 2) the assignment of product types to compartments, and 3) the shareability of compartments. To solve the PDPMC and its variants, i.e., additional time windows and different combinations of the three-compartment related attributes, an exact branch-price-and-cut algorithm (BPC) is proposed. The pricing problem in our BPC is solved through a unified bidirectional labeling algorithm with several acceleration techniques which reduce the symmetry. Our BPC is tested on a set of benchmark instances inspired from the PDP literature. We show the limits of our algorithm and derive relevant managerial insights.

Olivier Bahn organizer


Hybrid activity at GERAD
Zoom et salle 4488
Pavillon André-Aisenstadt
Campus de l'Université de Montréal
2920, chemin de la Tour

Montréal Québec H3T 1J4

Research Axis

Research application