A Branch-Price-and-Cut Algorithm for the Multicommodity Two-Echelon Vehicle Routing Problem with Time Windows

In the multicommodity two-echelon vehicle routing problem with time windows (MC-2E-VRPTW), first-echelon vehicles transport goods from depots to satellites, whereas second-echelon vehicles ensure that goods are shipped from satellites to customers within their time windows. Given a set of customers, each with demand available at one depot, the MC-2E-VRPTW aims at determining least-cost and capacity-feasible first- and second-echelon routes such that each customer is serviced during its time window by a second-echelon route and has a single first-echelon route supplying its whole demand. For this problem, we propose a route-based formulation that contains an exponential number of variables associated with second-echelon routes and develop a tailored branch-price-and-cut algorithm. This algorithm considers one subproblem per satellite, which is solved by a labeling algorithm to generate second-echelon routes and determine the first-echelon route supplying the load of each visited customer. We devise a recovery procedure to enforce integer solution feasibility in the presence of dual inequalities and propose a branching rule adapted to the multicommodity context. Through extensive computational experiments on benchmark instances, we show that our algorithm outperforms a state-of-the-art algorithm.

History: Accepted by Andrea Lodi, Area Editor for Design and Analysis of Algorithms–Discrete.

Funding: This work was supported by Natural Sciences and Engineering Research Council of Canada [Discovery Grants 2017-06106 and 2023-03791].

Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2024.1010) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2024.1010). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/.