Robust branch-and-cut-and-price for the capacitated vehicle routing problem

• 成果类型: Article
• 署名作者: Fukasawa, R; Longo, H; Lysgaard, J; de Aragao, MP; Reis, M; Uchoa, E; Werneck, RF
• 署名单位: Universidade Federal Fluminense; Universidade Federal de Goias; Aarhus University; Pontificia Universidade Catolica do Rio de Janeiro; Princeton University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-005-0644-x
• 发表日期: 2006
• 页码: 491-511
• 关键词: algorithm; relaxations; delivery; TREE

摘要

The best exact algorithms for the Capacitated Vehicle Routing Problem (CVRP) have been based on either branch-and-cut or Lagrangean relaxation/column generation. This paper presents an algorithm that combines both approaches: it works over the intersection of two polytopes, one associated with a traditional Lagrangean relaxation over q-routes, the other defined by bound, degree and capacity constraints. This is equivalent to a linear program with exponentially many variables and constraints that can lead to lower bounds that are superior to those given by previous methods. The resulting branch-and-cut-and-price algorithm can solve to optimality all instances from the literature with up to 135 vertices. This more than doubles the size of the instances that can be consistently solved.