Text

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

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.

Ketersediaan

Informasi Detail

Judul Seri

TRANSPORTATION SCIENCE; Vol. 56 No.1 January-February 2022

No. Panggil

-

Penerbit

: .,

Deskripsi Fisik

p. 245-264

Bahasa

English

ISBN/ISSN

-

Klasifikasi

NONE

Tipe Isi

-

Tipe Media

-

Tipe Pembawa

-

Edisi

-

Subjek

COLUMN GENERATION
MULTI-ECHELON VEHICLE ROUTING PROBLEM
DUAL-OPTIMAL INEQUALITIES

Info Detail Spesifik

https://doi.org/10.1287/trsc.2021.1092

Pernyataan Tanggungjawab

Tayeb Mhamedi, Henrik Andersson, Marilene Cherkesly, Guy Desaulniers

Versi lain/terkait

Lampiran Berkas

Komentar