Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/304688
Type: TESE DIGITAL
Title: Aspectos teóricos e computacionais na resolução do problema de rotas e cobertura multiveículo = Theoretical and computational aspects of multivehicle covering tour problem's resolution
Title Alternative: Theoretical and computational aspects of multivehicle covering tour problem's resolution
Author: Cunha Oliveira, Rodolfo, 1991-
Advisor: Moretti, Antonio Carlos, 1958-
Abstract: Resumo: Nesta dissertação, estudamos os aspectos teóricos e computacionais para o Problema de Rotas de Cobertura Multiveículo ($m$-PRC). Neste problema, alguns vértices devem pertencer a uma rota, enquanto outros devem ficar suficientemente próximos das rotas ótimas. A adaptação do problema sugerida por W. Oliveira et al. (2014) é considerada neste trabalho. Nela, a quantidade de vértices pertencentes as diferentes rotas deve ser equilibrada, com o objetivo de estudar um importante aspecto do problema de planejamento urbano preventivo, onde viaturas policiais visitam alguns pontos geográficos obrigatórios e cobrem visualmente outros, de modo a proporcionar visibilidade de patrulhamento e aumento da sensação de segurança pela população. A formulação matemática para o $m$-PRC consiste em um programa linear inteiro cujo tamanho e complexidade torna desafiador a aplicação de algoritmos exatos e necessário o uso de métodos heurísticos para a sua resolução. Soluções sub-ótimas são obtidas aplicando-se as heurísticas propostas por M. Hachicha et al. (2000) e W. Oliveira et al. (2014). Com o objetivo de obter soluções exatas, propomos uma alteração na formulação de fluxo em redes para o $m$-PRC proposta por M. Hà et al. (2013). Assim, para o caso equilibrado, foi possível encontrar soluções exatas para exemplares dimensionalmente pequenos utilizando o Solver CPLEX 12.6. As heurísticas, implementadas em linguagem C, e a formulação proposta foram validadas através da resolução de exemplares gerados aleatoriamente. Nossa implementação obteve bons resultados e mostrou-se computacionalmente barata, sendo capaz de resolver problemas na ordem de 1000 vértices em poucos minutos. A análise das soluções obtidas será utilizada para aprimorar o modelo proposto. As principais contribuições deste trabalho são uma nova proposta de modelo de fluxo em redes para o $m$-PRC balanceado e as implementações de heurísticas que podem ser facilmente utilizadas em qualquer computador com sistema operacional Windows ou Linux sem grandes adaptações

Abstract: This dissertation studied the theoretical and computational aspects of the multi-vehicle Covering Tour Problem ($m$-CTP). In this problem, some vertices must belong to a route, while others must be sufficiently close to the optimal routes. The adaptation of the problem suggested by W. Oliveira et al. (2014) is considered in this work. W. Oliveira et al. (2014) aims to balance the amount of vertices belonging to the different routes in order to study an important aspect of preventive urban planning problem where police cars visit some mandatory geographical points and visually cover others, to provide a patrol and increase the sense of security for the population. The $m$-CTP formulation is an integer linear program whose size and complexity chalenges the application of exact algorithms and requires the use of heuristic methods for its resolution. Sub-optimal solutions are obtained by applying heuristics proposed by M. Hachicha et al. (2000) and W. Oliveira et al. (2014). In order to get exact solutions, we propose a change in the networkflows formulation for the $m$-CTP proposed by M. H\'{a} et al. (2013). Thus, for the balanced case, it was possible to find exact solutions for dimensionally small problems using the CPLEX 12.6 Solver. The heuristics, implemented in C language, and the proposed formulation were validated by solving randomly generated instances. Our implementation obtained good results and proved to be computationally inexpensive, being able to solve problems in the order of 1000 vertices in a few minutes. The obtained solutions' analysis will be used to improve the proposed model. The main contributions found in this work is a network flows model for the balanced $m$-CTP and the heuristics' implementations that can be easily used on any computer with Windows or Linux operating system without major adaptations
Subject: Programação inteira
Heurística
Otimização combinatória
Problema de roteamento de veículos
Pesquisa operacional
Editor: [s.n.]
Date Issue: 2015
Appears in Collections:FCA - Dissertação e Tese

Files in This Item:
File SizeFormat 
CunhaOliveira_Rodolfo_M.pdf1.37 MBAdobe PDFView/Open


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