Séminaire en format hybride au local 4488 du GERAD ou Zoom.

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
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
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.