Abstract
This paper studies the multi-commodity two-echelon capacitated vehicle routing problem with time windows. Specifically, we take customer-specific origin to destination, non-substitutable demands into account. The main components are: (i) first echelon tours, (ii) second echelon tours and (iii) movement of commodities from first echelon to second echelon, considering route connection and synchronization. Exploiting the structure of the problem, we propose a decomposition scheme which decouples the first and second echelon routing problems, by deleting the third component, and re-couples them by using constraints ensuring movement of commodities between the two echelons. Based on this decomposition, we present (i) a number of model formulations for the MC-2E-VRPTW, and (ii) develop an exact solution approach for this real-life problem. A computational study on a comprehensive set of instances shows the effectiveness in terms of computational effort and solution quality.
| Original language | English |
|---|---|
| Article number | 105154 |
| Number of pages | 12 |
| Journal | Computers & Operations Research |
| Volume | 127 |
| DOIs | |
| Publication status | Published - Mar 2021 |
Funding
This research has been funded by the Dutch Institute for Advanced Logistics (DINALOG), under the grant titled ConCoord. Partial funding for this project has been provided by the Natural Sciences and Engineering Council of Canada (NSERC), through its Discovery Grant program. We also gratefully acknowledge the support of Fonds de recherche du Québec through their infrastructure grants. While working on this project, Teodor Gabriel Crainic was Adjunct Professor with the Department of Computer Science and Operations Research of the Université de Montréal. We also thank the anonymous referees for their constructive remarks.
Keywords
- Capacitated vehicle routing problem
- Distribution
- Exact solution algorithm
- Model formulations
- Multi-commodity
- Two-echelon