Webinar link via Teams

In this talk, 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. It consists in determining 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, and solve it using BPC. To generate second-echelon routes, one pricing problem per satellite is considered and 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.

*Webinar organized by Stefan Irnich's Chair of Logistics Management.

Stefan Irnich seminar, Exact solution of soft-clustered capacitated vehicle-routing and arc-routing problems, December 15, 2020