Back

G-2024-79

A branch-price-and-cut algorithm for the multi-commodity two-echelon vehicle routing problem with time windows

, , and

BibTeX reference

In the multi-commodity two-echelon vehicle routing problem with time windows (MC-2E-VRPTW), first-echelon vehicles transport goods from depots to satellites while 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 multi-commodity context. Through extensive computational experiments on benchmark instances, we show that our algorithm outperforms a state-of-the-art algorithm.

, 27 pages

Research Axis

Research application

Document

G2479.pdf (500 KB)