Um Enfoque Analógico para a Solução do Problema do Caixeiro Viajante Através do Método Elástico
Autores
3276 |
163,200,252
|
|
3277 |
163,200,252
|
|
3278 |
163,200,252
|
Informações:
Publicações do PESC
É apresentada neste trabalho, uma versão modificada do Algoritmo Elástico denominada por Filtro, aplicada sobre um problema de otimização combinatória muito famoso, o problema do Caixeiro Viajante. Com o objetivo de reduzir o tempo de processamento do Algoritmo Elástico, desenvolveu-se uma modificação do mesmo, no sentido de minimizar o número de cálculos de distâncias necessários em cada iteração do algoritmo. A aplicação do método em vários conjuntos de cidades gerou resultados que foram comparados com aqueles gerados por outro algoritmo, implementado também neste trabalho, o algoritmo LK. Foi observado que tanto o Elástico quanto o Filtro geraram resultados piores que o LK, em termos de custo de tour, porém num tempo de processamento substancialmente melhor. Os testes foram desenvolvidos nas estações de trabalho SUN, utilizando a linguagem C como linguagem de programação.
It is presented in this work, a modified version of Elastic Net denoted by the Filter. The method is applied to a classical problem in the field of combinatorial optimization, the Travelling Salesman Problem. The main computacional cost is in calculating the distances at each iteration. Concerned with the redution of the computational time required, it was proposed in this work, a minirnization of this calculation. The application of the method on random sets of cities, gives worse quality solutions, but much better computational times than another algorithm developed here, the LK. The tests have been performed on a workstation (SUN), utilizing the C language as programming tool.