A Branch-Cut-and-Price Approach for the Single-Trip and Multi-Trip Two-Echelon Vehicle Routing Problem with Time Windows

Guillaume Marques (), Ruslan Sadykov (), Rémy Dupas () and Jean-Christophe Deschamps ()
Additional contact information
Guillaume Marques: Inria Centre at the University of Bordeaux, 33405 Talence cedex, France; Institut de Mathématiques de Bordeaux UMR 5251, CNRS (Unité Mixte de Recherche 5251 du Centre Nationale de la Recherche Scientifique), University of Bordeaux, 33405 Talence cedex, France
Ruslan Sadykov: Inria Centre at the University of Bordeaux, 33405 Talence cedex, France; Institut de Mathématiques de Bordeaux UMR 5251, CNRS (Unité Mixte de Recherche 5251 du Centre Nationale de la Recherche Scientifique), University of Bordeaux, 33405 Talence cedex, France
Rémy Dupas: Laboratoire de l’Intégration du Matériau au Système, UMR 5218, University of Bordeaux, 33405 Talence cedex, France
Jean-Christophe Deschamps: Laboratoire de l’Intégration du Matériau au Système, UMR 5218, University of Bordeaux, 33405 Talence cedex, France

Transportation Science, 2022, vol. 56, issue 6, 1598-1617

Abstract: The paper studies the two-echelon capacitated vehicle routing problem with time windows, in which delivery of freight from depots to customers is performed using intermediate facilities called satellites. We consider the variant of the problem with precedence constraints for unloading and loading freight at satellites. In this variant allows for storage and consolidation of freight at satellites. Thus, the total transportation cost may decrease in comparison with the alternative variant with exact freight synchronization at satellites. We suggest a mixed integer programming formulation for the problem with an exponential number of route variables and an exponential number of precedence constraints that link first-echelon and second-echelon routes. Routes at the second echelon connecting satellites and clients may consist of multiple trips and visit several satellites. A branch-cut-and-price algorithm is proposed to solve efficiently the problem. This is the first exact algorithm in the literature for the multi-trip variant of the problem. We also present a postprocessing procedure to check whether the solution can be transformed to avoid freight consolidation and storage without increasing its transportation cost. It is shown that all single-trip literature instances solved to optimality admit optimal solutions of the same cost for both variants of the problem either with precedence constraints or with exact synchronization constraints. Experimental results reveal that our algorithm can be used to solve these instances significantly faster than another recent approach proposed in the literature.

Keywords: two-echelon vehicle routing; vehicle routing with time windows; multi-trip vehicle routing; branch-cut-and-price (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.2022.1136 (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:6:p:1598-1617

Access Statistics for this article

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