In this talk, we consider the two-echelon vehicle routing problem with time windows (2E-VRPTW). This problem arises in city logistics when high-capacity and low-capacity vehicles are used to transport merchandise from depots to satellites (first echelon), and from satellites to customers (second echelon), respectively. The aim is to determine a set of least-cost first- and second-echelon routes such that the load on the routes respect the capacity of the vehicles, each second-echelon route is supplied by exactly one first-echelon route, and each customer is visited by exactly one second-echelon route within its time window. We model this 2E-VRPTW with a route-based formulation involving first-echelon and second-echelon route variables. We propose to solve it using a branch-price-and-cut algorithm where only the second-echelon routes are generated by column generation. We discuss some specialized components of this algorithm, namely, the labeling algorithm for solving the pricing problems as well as deep dual optimal inequalities that are added to reduce degeneracy. We report computational results that show that our BPC algorithm outperforms a state-of-the-art algorithm. We also present sensitivity analysis results on the different components of our algorithm, and derive managerial insights related to the structure of the first-echelon routes.
Guy Desaulniers, Polytechnique Montreal and GERAD, Canada
Co-authors: Tayeb Mhamedi, Marilène Cherkesly, Henrik Andersson
Watch replay here