Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

A branch-cut-and-price approach for the single-trip and multi-trip two-echelon vehicle routing problem with time windows

Guillaume Marques 1, 2 Ruslan Sadykov 2 Jean-Christophe Deschamps 1 Rémy Dupas 1
2 Realopt - Reformulations based algorithms for Combinatorial Optimization
LaBRI - Laboratoire Bordelais de Recherche en Informatique, IMB - Institut de Mathématiques de Bordeaux, Inria Bordeaux - Sud-Ouest
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. 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 which 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 post-processing procedure to check whether the solution can be transformed to avoid freight consolidation and storage without increasing its transportation cost. Our algorithm significantly outperforms another recent one for the single-trip variant of the problem. We also show 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.
Document type :
Preprints, Working Papers, ...
Complete list of metadata

https://hal.inria.fr/hal-03139799
Contributor : Ruslan Sadykov Connect in order to contact the contributor
Submitted on : Friday, February 12, 2021 - 12:20:58 PM
Last modification on : Friday, January 21, 2022 - 3:11:51 AM
Long-term archiving on: : Thursday, May 13, 2021 - 6:43:45 PM

File

main-clear.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-03139799, version 1

Citation

Guillaume Marques, Ruslan Sadykov, Jean-Christophe Deschamps, Rémy Dupas. A branch-cut-and-price approach for the single-trip and multi-trip two-echelon vehicle routing problem with time windows. 2020. ⟨hal-03139799⟩

Share

Metrics

Les métriques sont temporairement indisponibles