Uma heurística baseada em colônia de formigas para o problema do carteiro chinês misto
Carregando...
Arquivos
Data
Autor(es)
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade Federal de Minas Gerais
Descrição
Tipo
Dissertação de mestrado
Título alternativo
Primeiro orientador
Membros da banca
Geraldo Robson Mateus
Thiago Ferreira de Noronha
Thiago Ferreira de Noronha
Resumo
O Problema do Carteiro Chinês (Chinese Postman Problem, em inglês) é um dos desafios clássicos em Ciência da Computação, especialmente na área de grafos. É um problema de otimização combinatória bem conhecido com uma infinidade de aplicações práticas. Grande parte dos problemas do mundo real onde seja preciso percorrer uma cidade, um trecho de mapa ou uma rede de recursos, tais como coleta de lixo urbano, inspeção em fios, retirada de gelo ou entrega de cartas, podem ser modelados atravésdo Chinese Postman problem (CPP) ou de suas variações. Basicamente, procura-se um caminho de custo mínimo em um grafo, de forma que o caminho contemple todas as arestas e arcos do grafo pelo menos uma vez. Este problema possui solução em tempo polinomial tanto para a versão orientada quanto para a versão não-orientada. O objeto de estudo deste trabalho é a variação do CPP conhecida como Problema do carteiro chinês misto, onde co-existem em um grafo arestas (não-direcionadas) e arcos. Esta variação do CPP é um problema NP-Completo [Papadimitriou, 1976]. É proposta uma heurística baseada em colônias de formigas para o MCPP (Problema do Carteiro Chinês Misto), assim como um procedimento de melhora contínua da solução.
Abstract
The Chinese Postman Problem (Chinese Postman Problem, in English) is one of the classic challenges in computer science, especially in the graphs. It is a combinatorial optimization problem well known with a multitude of practical applications. Much of the real-world problems where you need to go through a city, a map or excerpt from a network of resources, such as urban waste collection, inspection of wires, removal of ice or delivery of letters, can be modeled by the Chinese postman problem (CPP) or its variations. Basically, the aim is a minimum cost path in a graph, so that the path covering all edges and arcs of the graph at least once. This problem has a solution in polynomial time for both the oriented version to version as non-oriented. The object of this paper is the change in CPP known as Mixed Chinese Postman Problem, which co-exist in a graph edges (non-targeted) and arcs. This variation of the CPP is NP-complete [Papadimitriou, 1976]. It proposed a heuristic based on ant colonies for the MCPP (Mixed Chinese Postman Problem) as well as a procedure for continuous improvement of the solution.
Assunto
Otimização matemática, Otimização combinatória, Teoria dos grafos
Palavras-chave
Carteiro Chinês Misto, Colônia de Formigas, Otimização