Paper Info
Title
A Branch-Price-and-Cut Algorithm for the Two-Echelon Vehicle Routing Problem with Time Windows
Abstract
In this paper, we propose an exact branch-price-and-cut (BPC) algorithm for the two-echelon vehicle routing problem with time windows. This problem arises in city logistics when high-capacity and low-capacity vehicles are used to transport items 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 the problem with a route-based formulation where first-echelon routes are enumerated a priori, and second-echelon routes are generated using column generation. The problem is solved using BPC. To generate second-echelon routes, one pricing problem per satellite is solved using a labeling algorithm which keeps track of the first-echelon route associated with each (partial) second-echelon route considered. Furthermore, to speed up the solution process, we introduce effective deep dual-optimal inequalities and apply known valid inequalities. We perform extensive computational experiments on benchmark instances and show that our method outperforms a state-of-the-art algorithm. We also conduct sensitivity analyses on the different components of our algorithm and derive managerial insights related to the structure of the first-echelon routes.
Year
DOI
Venue
2022
10.1287/trsc.2021.1092
TRANSPORTATION SCIENCE
Keywords
DocType
Volume
column generation, multi-echelon vehicle routing problem, dual-optimal inequalities
Journal
56
Issue
ISSN
Citations 
1
0041-1655
0
PageRank 
References 
Authors
0.34
0
4
Name
Order
Citations
PageRank
Tayeb Mhamedi100.34
Henrik Andersson271.23
Marilene Cherkesly300.34
Guy Desaulniers487462.90