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 metadatas

Cited literature [10 references]  Display  Hide  Download

https://hal.laas.fr/hal-01880025
Contributor : Sandra Ulrich Ngueveu <>
Submitted on : Thursday, October 25, 2018 - 4:09:22 PM
Last modification on : Saturday, February 15, 2020 - 1:48:53 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, INFORMS, 2017, 51 (2), pp.592 - 606. ⟨10.1287/trsc.2016.0711⟩. ⟨hal-01880025⟩

Share

Metrics

Record views

385

Files downloads

447