Use este identificador para citar ou linkar para este item:
http://repositorio.utfpr.edu.br/jspui/handle/1/39111| Título: | O problema do carteiro chines em grafos mistos: otimização através da metaheurística colônia de formigas |
| Título(s) alternativo(s): | The chinese postman problem in mixed graphs: optimization using the metaheuristics ant colony algorithm |
| Autor(es): | Mascarenhas, Felipe Ritter |
| Orientador(es): | Barbosa, Marco Antonio de Castro |
| Palavras-chave: | Teoria dos grafos Formigas Programação heurística Graph theory Ants Heuristic programming |
| Data do documento: | 2-Dez-2025 |
| Editor: | Universidade Tecnológica Federal do Paraná |
| Câmpus: | Pato Branco |
| Citação: | MASCARENHAS, Felipe Ritter. O problema do carteiro chines em grafos mistos: otimização através da metaheurística colônia de formigas. 2025. Trabalho de Conclusão de Curso (Bacharelado em Engenharia de Computação) - Universidade Tecnológica Federal do Paraná, Pato Branco, 2025. |
| Resumo: | O Problema do Carteiro Chinês em grafos mistos modela tarefas de roteamento em que todas as arestas de uma rede devem ser percorridas com o menor custo possível, sendo relevante em cenários como limpeza urbana e inspeção de infraestrutura. Por se tratar de uma variante NPcompleta, métodos exatos tornam-se limitados para instâncias maiores, o que justifica o uso de heurísticas e meta-heurísticas. Este trabalho implementa e avalia duas variantes de Colônia de Formigas (Ant System e Elitist Ant System) e uma heurística gulosa para o Problema do Carteiro Chinês em Grafos Mistos, utilizando instâncias de referência da literatura. Comparam-se custo da solução, gap em relação ao ótimo conhecido e tempo de execução. Os resultados mostram que, nas configurações testadas, a heurística gulosa superou as versões de Colônia de Formigas em qualidade de solução e tempo computacional, indicando a necessidade de adaptações mais específicas dos modelos de formigas para torná-los competitivos nesse problema. |
| Abstract: | The Mixed Chinese Postman Problem (MCPP) models routing tasks in which all edges of a network must be traversed at minimum cost, with applications in street cleaning and infrastructure inspection. Since this mixed variant is NP-complete, exact methods are restricted to small and medium-sized instances, motivating the use of heuristics and metaheuristics. This work implements and evaluates two Ant Colony variants (Ant System and Elitist Ant System) and a greedy heuristic for the MCPP, using benchmark instances from the literature. Solution cost, gap with respect to the known optimum and running time are compared. The computational results show that, under the tested configurations, the greedy heuristic outperformed the Ant Colony variants in both solution quality and CPU time, suggesting that more problem-oriented adaptations are required for Ant-based models to become competitive on mixed-edge routing problems. |
| URI: | http://repositorio.utfpr.edu.br/jspui/handle/1/39111 |
| Aparece nas coleções: | PB - Engenharia de Computação |
Arquivos associados a este item:
| Arquivo | Descrição | Tamanho | Formato | |
|---|---|---|---|---|
| formigascarteirochinesproduto.pdf | 278,75 kB | Adobe PDF |  Visualizar/Abrir |
Este item está licenciada sob uma Licença Creative Commons
