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

Roberto Baldacci, Aristide Mingozzi, Roberto Roberti, Roberto Wolfler Clavo

Research output: Contribution to journalJournal articleResearchpeer-review

999 Downloads (Pure)

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.
Original languageEnglish
Journal4 O R
Volume61
Issue number2
Pages (from-to)298-314
Number of pages17
ISSN1619-4500
DOIs
Publication statusPublished - 2013
Externally publishedYes

Keywords

  • OPERATIONS
  • MANAGEMENT
  • LOCATION
  • SEARCH
  • Algorithms
  • Dynamic programming
  • Network routing
  • Routing algorithms
  • Sales
  • Transportation routes
  • Satellites
  • Capacitated vehicle routing problem
  • Computational results
  • Customer demands
  • Dual ascent
  • Exact algorithms
  • Mathematical formulation
  • Routing problems
  • Side constraints
  • Two-echelon vehicle routing
  • ALGORITHMS
  • Research

Fingerprint

Dive into the research topics of 'An Exact Algorithm for the Two-Echelon Capacitated Vehicle Routing Problem'. Together they form a unique fingerprint.

Cite this