Traveling Salesman Problem optimization by means of graph-based algorithm
| Autor: | Vladislav Skorpil, Lubomir Cizek, Jiri Stastny |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
Mathematical optimization
Meta-optimization Population-based incremental learning 2-opt 01 natural sciences 010104 statistics & probability Christofides algorithm Combinatorial optimization Suurballe's algorithm 0101 mathematics Greedy algorithm Bottleneck traveling salesman problem Algorithm Mathematics |
| Zdroj: | TSP |
| Popis: | There are many different algorithms for optimization of logistic and scheduling problems and one of the most known is Genetic algorithm. In this paper we take a deeper look at a draft of new graph-based algorithm for optimization of scheduling problems based on Generalized Lifelong Planning A* algorithm which is usually used for path planning of mobile robots. And then we test it on Traveling Salesman Problem (TSP) against classic implementation of genetic algorithm. The results of these tests are then compared according to the time of finding the best path, its travel distance, an average distance of travel paths found and average time of finding these paths. A comparison of the results shows that the proposed algorithm has very fast convergence rate towards an optimal solution. Thanks to this it reaches not only better solutions than genetic algorithm, but in many instances it also reaches them faster. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|