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

• 成果类型: Article
• 署名作者: Baldacci, Roberto; Mingozzi, Aristide; Roberti, Roberto; Clavo, Roberto Wolfler
• 署名单位: University of Bologna; University of Bologna; Universite Paris 13; Centre National de la Recherche Scientifique (CNRS); CNRS - Institute of Physics (INP)
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.1120.1153
• 发表日期: 2013
• 页码: 298-314
• 关键词: location; search

摘要

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.