Registro fonte: Uma solução para o problema do caixeiro viajante com limite de calado

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...

ver descrição completa

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:	Caixeiros-viajantes Transporte de mercadorias Análise de redes (Planejamento) Traveling sales personnel Shipment of goods Network analysis (Planning) CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
Acesso em linha:	http://repositorio.utfpr.edu.br/jspui/handle/1/14589
Tags:	Adicionar Tag Sem tags, seja o primeiro a adicionar uma tag!

id	riut-1-14589
recordtype	dspace
spelling	riut-1-145892020-11-18T14:01:19Z Uma solução para o problema do caixeiro viajante com limite de calado A solution for the traveling salesman problem with draft limits Silva, Luana Villwock Barbosa, Marco Antonio de Castro Barbosa, Marco Antonio de Castro Casanova, Dalcimar Marin, Luciene de Oliveira Borsoi, Beatriz Terezinha Caixeiros-viajantes Transporte de mercadorias Análise de redes (Planejamento) Traveling sales personnel Shipment of goods Network analysis (Planning) CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO 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. 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. 2020-11-18T14:01:19Z 2020-11-18T14:01:19Z 2017-11-24 bachelorThesis 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. http://repositorio.utfpr.edu.br/jspui/handle/1/14589 por openAccess application/pdf Universidade Tecnológica Federal do Paraná Pato Branco Brasil Departamento Acadêmico de Informática Engenharia de Computação UTFPR
institution	Universidade Tecnológica Federal do Paraná
collection	RIUT
language	Português
topic	Caixeiros-viajantes Transporte de mercadorias Análise de redes (Planejamento) Traveling sales personnel Shipment of goods Network analysis (Planning) CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
spellingShingle	Caixeiros-viajantes Transporte de mercadorias Análise de redes (Planejamento) Traveling sales personnel Shipment of goods Network analysis (Planning) CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO Silva, Luana Villwock Uma solução para o problema do caixeiro viajante com limite de calado
description	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.
format	Trabalho de Conclusão de Curso (Graduação)
author	Silva, Luana Villwock
author_sort	Silva, Luana Villwock
title	Uma solução para o problema do caixeiro viajante com limite de calado
title_short	Uma solução para o problema do caixeiro viajante com limite de calado
title_full	Uma solução para o problema do caixeiro viajante com limite de calado
title_fullStr	Uma solução para o problema do caixeiro viajante com limite de calado
title_full_unstemmed	Uma solução para o problema do caixeiro viajante com limite de calado
title_sort	uma solução para o problema do caixeiro viajante com limite de calado
publisher	Universidade Tecnológica Federal do Paraná
publishDate	2020
citation	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.
url	http://repositorio.utfpr.edu.br/jspui/handle/1/14589
_version_	1805303911535345664
score	10,814766

Uma solução para o problema do caixeiro viajante com limite de calado

Registros relacionados