An Exact Algorithm for the Two-Echelon Capacitated Vehicle Routing Problem

Roberto Baldacci (), Aristide Mingozzi (), Roberto Roberti () and Roberto Wolfler Calvo ()
Additional contact information
Roberto Baldacci: Department of Electronics, Computer Science, and Systems, University of Bologna, 40126 Bologna, Italy
Aristide Mingozzi: Department of Mathematics, University of Bologna, 40126 Bologna, Italy
Roberto Roberti: Department of Electronics, Computer Science, and Systems, University of Bologna, 40126 Bologna, Italy
Roberto Wolfler Calvo: Laboratoire d'Informatique de Paris Nord, Université de Paris 13; and Sorbonne Paris Cité, CNRS (UMR 7538), 93430 Villetaneuse, France

Operations Research, 2013, vol. 61, issue 2, 298-314

Abstract: In the two-echelon capacitated vehicle routing problem (2E-CVRP), the delivery to customers from a depot uses intermediate depots, called satellites . The 2E-CVRP involves two levels of routing problems. The first level requires a design of the routes for a vehicle fleet located at the depot to transport the customer demands to a subset of the satellites. The second level concerns the routing of a vehicle fleet located at the satellites to serve all customers from the satellites supplied from the depot. The objective is to minimize the sum of routing and handling costs. This paper describes a new mathematical formulation of the 2E-CVRP used to derive valid lower bounds and an exact method that decomposes the 2E-CVRP into a limited set of multidepot capacitated vehicle routing problems with side constraints. Computational results on benchmark instances show that the new exact algorithm outperforms the state-of-the-art exact methods.

Keywords: two-echelon vehicle routing; dual ascent; dynamic programming (search for similar items in EconPapers)
Date: 2013
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (38)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1120.1153 (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:oropre:v:61:y:2013:i:2:p:298-314

Access Statistics for this article

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