期刊名称：Relatórios de Pesquisa em Engenharia de Produção
电子版ISSN：1678-2399
出版年度：2003
卷号：3
出版社：Universidade Federal Fluminense (UFF)
摘要：During the eigthies and early nineties, the best exact algorithms for the Capacitated Vehicle Routing Problem (CVRP) utilized lower bounds obtained by Lagrangean relaxation or column generation. Next, the advances in the polyhedral description of the CVRP yielded branch-and- cut algorithms giving better results. However, several instances in the range of 50{80 vertices, some proposed more than 30 years ago, can not be solved with current known techniques. This paper presents an algorithm utilizing a lower bound obtained by minimizing over the intersec- tion of the polytopes associated to a traditional Lagrangean relaxation over q-routes and the one de¯ned by bounds, degree and the capacity constraints. This is equivalent to a linear program with an exponential number of both variables and constraints. Computational experiments show the new lower bound to be superior to the previous ones, specially when the number of vehicles is large. The resulting branch-and-cut-and-price could solve to optimality almost all instances from the literature up to 100 vertices, nearly doubling the size of the instances that can be consistently solved. Further progress in this algorithm may be soon obtained by also using other known families of inequalities.
