Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/331772
Type: TESE DIGITAL
Title: Métodos de resolução e modelagem para o problema de rotas de cobertura multiveículo
Title Alternative: Solution methods and modeling for the multi-vehicle covering tour problem
Author: Ota, Cristina Teruko, 1987-
Advisor: Oliveira, Washington Alves de, 1977-
Abstract: Resumo: Os aspectos teóricos e computacionais foram apresentados para uma nova abordagem do problema de rotas de cobertura multiveículo (m-PRC). Nesta abordagem, o m-PRC determina um conjunto de rotas de veículos para toda frota disponível, tal que a distância total percorrida seja mínima. Na modelagem para resolver o m-PRC cada vértice representa uma localização de interesse e esses vértices são divididos em três conjuntos: vértices que podem ser visitados; vértices que devem ser visitados; e vértices que devem ser cobertos, no sentido de que cada um desses vértices deve estar próximo de um vértice visitado na rota. Além disso, foi considerado o balanceamento entre as rotas, ou seja, o número de vértices visitados nas diferentes rotas deve ser aproximadamente o mesmo. O m-PRC balanceado foi resolvido a partir de cinco métodos de resolução, sendo dois algoritmos genéticos e três métodos branch-and-cut, os quais foram implementados em um software de otimização. Os algoritmos genéticos e dois métodos branch-and-cut foram propostos neste trabalho. Na resolução dos métodos exatos foram incluídas desigualdades válidas para o m-PRC. Para os testes computacionais foram utilizados exemplares adaptados da biblioteca TSPLIB. Testes estatísticos realizados mostram a qualidade da abordagem proposta, com resultados promissores. Os resultados foram comparados usando perfis de desempenho

Abstract: The theoretical and computational aspects of a new approach of the multi-vehicle covering tour problem (m-CTP) were presented. In this approach, m-CTP determines a set of vehicle routes for all available fleet, such that the total distance traveled is minimal. In the model presented each vertex represents a location of interest and these vertices belong to three sets: vertices that can be visited; vertices that must be visited; and vertices that must be covered, in the sense that each vertex must be close to a visited vertex in a route. Furthermore, it was considered balanced routes, in other words, the number of visited vertices from different routes must be nearly the same. The balanced m-CTP was solved by using five solution methods, being two genetic algorithms and three branch-and-cut techniques. The methods were implemented in an optimization software. The genetic algorithms and two branch-and-cut methods were presented in this work. For exact methods resolution valid inequalities were added to m-CTP. Computational tests performed using adapted instances from TSPLIB library provided statistic results for a series of data that measured the quality of the proposed approach which were promissing. The obtained results were compared with performance profile
Subject: Algoritmos branch-and-cut
Algoritmos genéticos
Desigualdades (Matemática)
Language: Português
Editor: [s.n.]
Citation: OTA, Cristina Teruko. Métodos de resolução e modelagem para o problema de rotas de cobertura multiveículo. 2018. 1 recurso online (98 p.). Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Ciências Aplicadas, Limeira, SP. Disponível em: <http://www.repositorio.unicamp.br/handle/REPOSIP/331772>. Acesso em: 3 set. 2018.
Date Issue: 2018
Appears in Collections:FCA - Tese e Dissertação

Files in This Item:
File SizeFormat 
Ota_CristinaTeruko_M.pdf809.46 kBAdobe PDFView/Open


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