Solving capacitated arc routing problems using a transformation to the CVRP

作     者：Longo, H de Aragao, MP Uchoa, E 

作者机构：Pontificia Univ Catolica Rio de Janeiro Dept Informat BR-22453900 Rio De Janeiro Brazil Univ Fed Goias Inst Informat BR-74001970 Goiania Go Brazil Univ Fed Fluminense Dept Engn Prod BR-24210 Niteroi RJ Brazil 

出 版 物：《COMPUTERS & OPERATIONS RESEARCH》 (计算机与运筹学研究)

年 卷 期：2006年第33卷第6期

页      面：1823-1837页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：PICDT Coordenação de Aperfeiçoamento de Pessoal de Nível Superior, CAPES Conselho Nacional de Desenvolvimento Científico e Tecnológico, CNPq, (302086/2003-0, 304533/2002-5) 

主　　题：arc routing mixed-integer programming 

摘      要：A well-known transformation by Pearn, Assad and Golden reduces a capacitated arc routing problem (CARP) into an equivalent capacitated vehicle routing problem (CVRP). However, that transformation is regarded as unpractical, since an original instance with r required edges is turned into a CVRP over a complete graph with 3r + 1 vertices. We propose a similar transformation that reduces this graph to 2r + 1 vertices, with the additional restriction that a previously known set of r pairwise disconnected edges must belong to every solution. Using a recent branch-and-cut-and-price algorithm for the CVRP, we observed that it yields an effective way of attacking the CARP, being significantly better than the exact methods created specifically for that problem. Computational experiments obtained improved lower bounds for almost all open instances from the literature. Several such instances could be solved to optimality. Scope and purpose The scope of this paper is transforming arc routing problems into node routing problems. The paper shows that this approach can be effective and, in particular, that the original instances may generate node routing instances that behave as if the size is not increased. This result is obtained by slightly modifying the well-known transformation by Pearn, Assad and Golden from capacitated arc routing problem (CARP) to the capacitated vehicle routing problem (CVRP), that is regarded as unpractical. The paper provides a computational experience using a recent branch-and-cut-and-price algorithm for the CVRP. The results are significantly better than the exact methods created specifically for that problem, improving lower bounds for almost all open instances from the literature. Several such instances could be solved to optimality. (c) 2004 Elsevier Ltd. All rights reserved.