期刊名称：Relatórios de Pesquisa em Engenharia de Produção
电子版ISSN：1678-2399
出版年度：2004
卷号：4
出版社：Universidade Federal Fluminense (UFF)
摘要：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 regardedas unpractical, since an original instance with r required edges is turned into a CVRP over a complete graphwith 3r + 1 vertices. We propose a similar transformation that reduces this graph to 2r + 1 vertices, with theadditional restriction that r edges are already fixed to 1. Using a recent branch-and-cut-and-price algorithm forthe CVRP, we observed that it yields an e.ective way of attacking the CARP, being significantly better thanthe exact methods created specifically for that problem. Computational experiments obtained improved lowerbounds for almost all open instances from the literature. Several such instances could be solved to optimality
其他摘要：O problema de roteamento de ve′.culos em um grafo com demandas nas arestas (CARP - Capacitated ArcRouting Problem) pode ser transformado em um problema equivalente de roteamento com as demandas nosv′ertices (CVRP - Capacitated Vehicle Routing Problem), usando-se a transforma.c.ao proposta por Pearn, Assade Golden. Contudo, a utiliza.c.ao dessa transforma.c.ao ′e praticamente invi′avel, uma vez que uma inst.ancia doCARP com r arestas com demandas ′e transformada em um CVRP com 3r + 1 v′ertices. N′os propomosuma transforma.c.ao similar que reduz esse grafo a 2r + 1 v′ertices, com a restri.c.ao adicional de que r arestass.ao previamente fixadas em 1. Usando-se um algoritmo recente de branch-and-cut-and-price para o CVRP,essa nova transforma.c.ao mostrou-se eficaz na resolu.c.ao do CARP, sendo significativamente melhor do que osm′etodos exatos criados especificamente para esse problema. As experi.encias computacionais melhoraram oslimites inferiores no valor da solu.c.ao ′otima para quase to das as inst.ancias testadas. Muitas dessas inst.anciasda literatura puderam, pela primeira vez, ser resolvidas at′e a otimalidade
