Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/320875
Type: TESE DIGITAL
Title: Algoritmos heurísticos e exatos para o problema do ciclo dominante
Title Alternative: Heuristic and exact algorithms for the dominating cycle problem
Author: Maziero, Lucas Porto, 1992-
Advisor: Usberti, Fábio Luiz, 1982-
Abstract: Resumo: Esta dissertação dedicou-se ao estudo de uma generalização do Problema do Caixeiro Viajante (TSP), denominada Problema do Ciclo Dominante (DCP). Essa generalização consiste na composição de dois problemas NP-difíceis: o TSP e o Problema do Conjunto k-Dominante em Grafos (k-DSP). O objetivo do DCP consiste em encontrar um ciclo de custo mínimo em um grafo não-direcionado, partindo de um vértice origem, tal que cada vértice do grafo ou pertence ao ciclo ou está a uma distância de até k de um vértice do ciclo. A motivação de estudo do DCP consiste em sua aplicação para um problema de roteamento, onde empresas que atuam como fornecedores de energia, gás ou água, possuem empregados responsáveis por registrar o consumo de clientes dispersos geograficamente. Considera-se que esses empregados, denominados leituristas, possuem aparelhos de medição remota, com raio de alcance pré-definido. Com esses aparelhos, os leituristas não precisam visitar cada cliente; basta que em suas rotas de leitura todos os clientes estejam no raio de alcance do aparelho. Esta dissertação apresentou um método heurístico e um método exato para solução do DCP. O método heurístico é baseado na metaheurística GRASP (Greedy Randomized Adaptive Search Procedure). Um algoritmo Branch-and-Cut é proposto como método exato para o DCP. Os métodos, heurístico e exato, são testados com um conjunto representativo de instâncias e os resultados obtidos são comparados, avaliando a eficiência de cada método no que diz respeito aos desvios de otimalidade

Abstract: This dissertation studies a generalization of the Travelling Salesman Problem (TSP), called the Dominating Cycle Problem (DCP). This generalization is a composition of two NP-hard problems: the TSP and the k-Dominating Set Problem in Graphs (k-DSP). The aim of the DCP is to find a minimum cost cycle in an undirected graph, from a source vertex, such that each vertex in the graph either belongs to the cycle, or is at a distance of up to k of some vertex in the cycle. The DCP is motivated by its application to a routing problem, where utilities that act as energy, gas or water suppliers, have employees responsible for recording the consumption of geographically dispersed customers. It is considered that these employees, called meter readers, have remote measurement devices, with pre-defined range. With these devices, meter readers do not need to visit each client; it suffices that all clients are within the device range from the reading routes. This dissertation presented a heuristic method and an exact method for the solution of the DCP. The heuristic method is based on GRASP (Greedy Randomized Adaptive Search Procedure). A Branch-and-Cut algorithm is proposed as the exact method for the DCP. The methods, heuristic and exact, are tested with a representative set of instances and the obtained results are compared, evaluating the efficiency of each method with respect to deviations from optimality
Subject: Teoria da computação
Otimização combinatória
Problema de roteamento de leituristas
Programação inteira
Meta-heurística
Editor: [s.n.]
Date Issue: 2016
Appears in Collections:IC - Tese e Dissertação

Files in This Item:
File SizeFormat 
Maziero_LucasPorto_M.pdf1.17 MBAdobe PDFView/Open


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