Orientador: Fábio Luiz UsbertDissertação (mestrado) - Universidade Estadual de Campinas, Instituto de ComputaçãoResumo: Problemas de roteamento em arcos têm por objetivo determinar rotas de custo mínimo que visitam um subconjunto de arcos de um grafo, com uma ou mais restrições adicionais. A solução desses problemas remete à diminuição de custos logísticos, melhorando a competitividade das empresas. O Problema de Roteamento em Arcos Capacitado e Aberto (\textit{OCARP - Open Capacitated Arc Routing Problem}) é um problema de otimização combinatória NP-difícil com aplicações práticas, como o problema de roteamento de leituristas e o problema de determinação do caminho de corte. Esta dissertação de mestrado propõe novos métodos de solução para o OCARP. São propostas uma metaheurística de algoritmos genéticos e uma formulação relaxada de programação linear inteira. Experimentos computacionais comprovam o bom desempenho dos métodos desenvolvidos em comparação aos métodos da literatura. Os resultados demonstram a redução substancial do desvio de otimalidade para todos os grupos de instâncias e parâmetros considerados durante o experimento. Em particular, cinco do total de nove grupos de instâncias foram resolvidos até a otimalidadeAbstract: Arc routing problems aim at determining the lowest cost routes visiting a subset of edges from a graph, with one or more additional constraints. The solution of these problems leads to lower logistics costs, improving business competitiveness. The Open Capacitated Arc Routing Problem (OCARP) is an NP-hard combinatorial optimization problem with practical applications, such as the meter reading routing problem and the cutting path determination problem. This master thesis proposes new solution methods for OCARP. It is proposed a genetic algorithm metaheuristic and a relaxed integer linear programming formulation. Computational experiments prove the good performance of the developed methods compared to literature methods. The results show a substantial reduction in optimality deviation for all groups of instances and parameters considered during the experiment. In particular, five from the total of nine instance groups were solved to optimalityMestradoCiência da ComputaçãoMestre em Ciência da Computação162027/2014-1CNPQ