Uma solução para o problema do caixeiro viajante com limite de calado
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 a...
| Autor principal: | Silva, Luana Villwock |
|---|---|
| Formato: | Trabalho de Conclusão de Curso (Graduação) |
| Idioma: | Português |
| Publicado em: |
Universidade Tecnológica Federal do Paraná
2020
|
| Assuntos: | |
| Acesso em linha: |
http://repositorio.utfpr.edu.br/jspui/handle/1/14589 |
| Tags: |
Adicionar Tag
Sem tags, seja o primeiro a adicionar uma tag!
|
| Resumo: |
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. |
|---|