Please use this identifier to cite or link to this item:
http://hdl.handle.net/1843/SLSS-87JHC4| Type: | Dissertação de Mestrado |
| Title: | Uma heurística baseada em colônia de formigas para o problema do carteiro chinês misto |
| Authors: | Jairo Viana Junior |
| First Advisor: | Sebastián Alberto Urrutia |
| First Referee: | Geraldo Robson Mateus |
| Second Referee: | Thiago Ferreira de Noronha |
| Abstract: | 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. |
| Subject: | Otimização matemática Otimização combinatória Teoria dos grafos |
| language: | Português |
| Publisher: | Universidade Federal de Minas Gerais |
| Publisher Initials: | UFMG |
| Rights: | Acesso Aberto |
| URI: | http://hdl.handle.net/1843/SLSS-87JHC4 |
| Issue Date: | 9-Jul-2010 |
| Appears in Collections: | Dissertações de Mestrado |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| jairovianajunior.pdf | 1.23 MB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.