Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/305624
Type: DISSERTAÇÃO DIGITAL
Degree Level: Mestrado
Title: Estudos computacionais para o problema de roteamento em arcos capacitado e aberto
Title Alternative: Computational studies for the open capacitated arc routing problem
Author: Arakaki, Rafael Kendy, 1993-
Advisor: Usberti, Fábio Luiz, 1982-
Abstract: Resumo: 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 otimalidade

Abstract: 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 optimality
Subject: Problema de roteamento em arcos
Problema de roteamento de leituristas
Algoritmos genéticos
Programação inteira
Otimização combinatória
Editor: [s.n.]
Citation: ARAKAKI, Rafael Kendy. Estudos computacionais para o problema de roteamento em arcos capacitado e aberto. 2016. 1 recurso online (61 p.). Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação, Campinas, SP. Disponível em: <http://www.repositorio.unicamp.br/handle/REPOSIP/305624>. Acesso em: 30 ago. 2018.
Date Issue: 2016
Appears in Collections:IC - Tese e Dissertação

Files in This Item:
File SizeFormat 
Arakaki_RafaelKendy_M.pdf1.06 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.