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

Tayeb Mhamedi (), Henrik Andersson (), Marilène Cherkesly () and Guy Desaulniers ()
Additional contact information
Tayeb Mhamedi: Department of Mathematics and Industrial Engineering, Polytechnique Montréal, Montréal, Québec H3T 1J4, Canada; Group for Research in Decision Analysis (GERAD), HEC Montréal, Montréal, Québec H3T 2A7, Canada
Henrik Andersson: Department of Industrial Economics and Technology Management, Norwegian University of Science and Technology, 7491 Trondheim, Norway
Marilène Cherkesly: Group for Research in Decision Analysis (GERAD), HEC Montréal, Montréal, Québec H3T 2A7, Canada; Department of Management and Technology, Université du Québec à Montréal, Montréal, Québec H2X 3X2, Canada
Guy Desaulniers: Department of Mathematics and Industrial Engineering, Polytechnique Montréal, Montréal, Québec H3T 1J4, Canada; Group for Research in Decision Analysis (GERAD), HEC Montréal, Montréal, Québec H3T 2A7, Canada

Transportation Science, 2022, vol. 56, issue 1, 245-264

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.

Keywords: column generation; multi-echelon vehicle routing problem; dual-optimal inequalities (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.2021.1092 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:56:y:2022:i:1:p:245-264

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().