The work proposed in this dissertation is the field of combinatorial optimization, which aims to find a solution to these types of problems at a low computational time and effectively. The combinatorial optimization studies a set of discrete solutions, which have a finite number of elements, to find the best viable solution to the problems of this magnitude. One of the main approaches that area is the Traveling Salesman Problem (TSP), mainly due to the size of possible solutions to the problem, so that is intractable computation by exhaustive search methods. Given all these features, this work is to study and develop evolutionary strategies for the resolution of the Problem of Traveling Salesman with Heterogeneous Demands (TSPHD), a variation of the classic TSP. The evolutionary strategies belong to the class of evolutionary computation, and methods of search based on the theory of the evolution of species, where the best individuals compete for survival. The evolutionary strategies differ from other optimization techniques, as the search is conducted in a population of solutions, not a single point. To solve the problem are proposed four evolutionary algorithms, using heuristics techniques and metaheurísticas for its implementation. The results were obtained from tests using instances of low density (low connection), and compared with the exact solution (optimal solution) and other progressive methods in the literature. These results are evaluated on the basis of their quality and time for its implementation. / O trabalho proposto nessa dissertação pertence à área de otimização combinatória, a qual visa encontrar uma solução para esses tipos de problema em um tempo computacional baixo e de forma eficaz. A otimização combinatória estuda um conjunto discreto de soluções, os quais possuem um número finito de elementos, para se poder encontrar a melhor solução viável para os problemas dessa grandeza. Uma das principais abordagens dessa área é o Problema do Caixeiro Viajante (PCV), principalmente devido à dimensão de possíveis soluções para o problema, fazendo com que seja intratável computacionalmente por métodos de buscas exaustivas. Face a todas essas características, este trabalho tem por objetivo estudar e desenvolver estratégias evolutivas para a resolução do Problema do Caixeiro Viajante com Demandas Heterogêneas (PCVDH), uma variação do PCV clássico. As estratégias evolutivas pertencem à classe da computação evolutiva, sendo métodos de busca inspirados na teoria da evolução das espécies, onde os melhores indivíduos competem pela sobrevivência. As estratégias evolutivas diferem das demais técnicas de otimização, pois a busca é realizada em uma população de soluções, não em um único ponto. Para a resolução do problema são propostos quatro algoritmos evolutivos, utilizando técnicas heurísticas e metaheurísticas para sua aplicação. Os resultados foram obtidos com testes utilizando instâncias de baixa densidade (baixa conexão), e comparados com a sua solução exata (solução ótima) e com outros métodos evolutivos encontrados na literatura. Esses resultados são avaliados com base na sua qualidade e tempo decorrido para sua execução.
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.ufsm.br:1/8041 |
| Date | 23 November 2006 |
| Creators | Vieira, Luis Eduardo |
| Contributors | Müller, Felipe Martins, Oliveira, Joao Helvio Righi de, Santos, José Vicente Canto dos |
| Publisher | Universidade Federal de Santa Maria, Programa de Pós-Graduação em Engenharia de Produção, UFSM, BR, Engenharia de Produção |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | application/pdf |
| Source | reponame:Repositório Institucional da UFSM, instname:Universidade Federal de Santa Maria, instacron:UFSM |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | 300800000005, 400, 500, 300, 300, 500, 71f97871-5101-4fa8-b821-aa730e3775c4, d6899f71-b319-4024-8058-4a01c2c7f80e, 63f94315-1157-4d1c-a162-d58cf9ef0489, 52bfd79c-590b-439b-bf1a-a6efda2c34aa |
Page generated in 0.0023 seconds