The Vehicle Routing Problem with Transhipment Facilities

Roberto Baldacci (), Sandra Ulrich Ngueveu () and Roberto Wolfler Calvo ()
Additional contact information
Roberto Baldacci: Department of Electrical, Electronic, and Information Engineering, University of Bologna, 47521 Cesena, Italy
Sandra Ulrich Ngueveu: LAAS–CNRS, Université de Toulouse, CNRS, INP, F-31400 Toulouse, France
Roberto Wolfler Calvo: Laboratoire d’Informatique de Paris Nord, Université de Paris 13, 93430 Villetaneuse, France; and Sorbonne Paris Cité, CNRS (UMR 7030), 93430 Villetaneuse, France

Transportation Science, 2017, vol. 51, issue 2, 592-606

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.

Keywords: transhipment facilities; dual ascent heuristic; column-and-cut generation (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
https://doi.org/10.1287/trsc.2016.0711 (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:51:y:2017:i:2:p:592-606

Access Statistics for this article

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