Skip to Main content Skip to Navigation
New interface
Journal articles

The Vehicle Routing Problem with Transhipment Facilities

Abstract : This paper proposes an exact method for solving an optimization problem arising in several distribution networks where customers can be served directly, using vehicle routes from a central depot, or through transhipment facilities. The problem consists of optimizing the following inter-dependent decisions: selecting transhipment facilities, allocating customers to these facilities, and designing vehicle routes emanating from a central depot to minimize the total distribution cost. This problem is called the Vehicle Routing Problem with Transhipment Facilities (vrptf). The paper describes two integer-programming formulations for the vrptf, i.e., an edge-flow based formulation and a Set Partitioning (SP) based formulation. The LP-relaxation of the two formulations are further strengthened by the addition of different valid inequalities. We also describe two new route relaxations used by dual ascent heuristics to find near-optimal dual solutions of LP-relaxation of the SP model. The valid inequalities and the route relaxations are used in a branch-and-cut-and-price approach to solve the problem to optimality. The proposed method is tested on a large family of instances, including real-world examples. The computational results obtained indicate the effectiveness of the proposed method.
Complete list of metadata

Cited literature [10 references]  Display  Hide  Download

https://hal.laas.fr/hal-01880025
Contributor : Sandra Ulrich Ngueveu Connect in order to contact the contributor
Submitted on : Thursday, October 25, 2018 - 4:09:22 PM
Last modification on : Tuesday, October 25, 2022 - 11:58:11 AM
Long-term archiving on: : Saturday, January 26, 2019 - 3:11:18 PM

File

vrptfforHAL.pdf
Files produced by the author(s)

Identifiers

Citation

Roberto Baldacci, Sandra Ulrich Ngueveu, Roberto Wolfler Calvo. The Vehicle Routing Problem with Transhipment Facilities. Transportation Science, 2017, 51 (2), pp.592 - 606. ⟨10.1287/trsc.2016.0711⟩. ⟨hal-01880025⟩

Share

Metrics

Record views

57

Files downloads

0