Use este identificador para citar ou linkar para este item:
http://repositorio.utfpr.edu.br/jspui/handle/1/14589| Título: | Uma solução para o problema do caixeiro viajante com limite de calado |
| Título(s) alternativo(s): | A solution for the traveling salesman problem with draft limits |
| Autor(es): | Silva, Luana Villwock |
| Orientador(es): | Barbosa, Marco Antonio de Castro |
| Palavras-chave: | Caixeiros-viajantes Transporte de mercadorias Análise de redes (Planejamento) Traveling sales personnel Shipment of goods Network analysis (Planning) |
| Data do documento: | 24-Nov-2017 |
| Editor: | Universidade Tecnológica Federal do Paraná |
| Câmpus: | Pato Branco |
| Citação: | SILVA, Luana Villwock. Uma solução para o problema do caixeiro viajante com limite de calado. 2017. 60 f. Trabalho de Conclusão de Curso (Graduação) - Universidade Tecnológica Federal do Paraná, Pato Branco, 2017. |
| Resumo: | Problemas de otimização cada vez mais complexos têm surgido nos últimos anos nas mais diversas áreas do conhecimento e isso exige que profissionais da área de computação procurem soluções para os mesmos. Entretanto, determinados problemas são tão complexos que não existem algoritmos que possam resolvê-los otimamente em tempo polinomial. Assim, o estudo nessa área tem crescido e se tornado bastante relevante. Um problema clássico em programação matemática é o problema do caixeiro viajante. Esse problema e suas variações possuem várias aplicações práticas. Uma das suas variações é o problema abordado nesse trabalho, que é o problema do caixeiro viajante com limite de calado. Existem várias classes de métodos para a resolução desses problemas, um delas são as meta-heurísticas, que nem sempre encontram uma solução ótima, mas permitem encontrar soluções satisfatórias em tempo polinomial, ao contrário dos outros métodos. Com o objetivo de encontrar melhores resultados surgiram várias meta-heurísticas, neste trabalho foi abordado a meta-heurística colônia de formigas para resolver o problema citado anteriormente. Esse algoritmo consiste do uso de formigas artificiais que percorrem um grafo deixando feromônio, uma substância química que evapora com o tempo nas arestas. O objetivo dessas ações é que essas formigas convirjam para o mesmo caminho e esse caminho ser o melhor possível. Com isso obteve-se resultados bons, apesar de nem todos terem chegado na solução ótima. |
| Abstract: | In the past few year complex optimization problems have arisen in diverse areas of knowledge requiring that computer professionals search for a solution to them. However, certain problems are so complex that are no algorithms tha can solve them optimally in polynomial time. Thus, the study in this area has grown and become quite relevant. A classic problem in mathematical programming is the traveling salesman problem. This problem and its variations have several applications. One of its varionts is the problem addressed in this work, which is the problem of the traveling salesman with draft limits. There are several types of methods to solve these problems, one of them are meta-heuristics, which do not always find an optimal solution, but allow finding satisfactory solutions in polynomial time, unlike other methods. In this paper, Ant Colony was approached to solve the previously mentioned problem. This algoritm consists of the use of artificial ants that walk through a graph leaving pheromone, a chemical substance that evaporates with time on the edges of the graph. The purpose of these actions is for these ants to converge on the same path and this path be the best possible. This has led to good results, although not always to the best solution. |
| URI: | http://repositorio.utfpr.edu.br/jspui/handle/1/14589 |
| Aparece nas coleções: | PB - Engenharia de Computação |
Arquivos associados a este item:
| Arquivo | Descrição | Tamanho | Formato | |
|---|---|---|---|---|
| PB_COENC_2017_1_05.pdf | 2 MB | Adobe PDF |  Visualizar/Abrir |
Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.