2016/12/17 by Roberto Baldacci, Sandra Ulrich Ngueveu, Roberto Wolfler Calvo · 1 citation
Engineering · #Transportation and Mobility Innovations #Urban and Freight Transport Logistics #Vehicle Routing Optimization Methods
paper · doi:10.1287/trsc.2016.0711
openalex publication_date 2016/12/17 · crossref created 2016/12/17 · crossref issued 2017/05/01 · crossref published 2017/05/01 · crossref published-print 2017/05/01 · crossref deposited 2023/04/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/03 · crossref indexed 2026/08/03
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.