Traveling Salesman Problem Optimization by Means of Graph-based Algorithm

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26210%2F16%3APU120392" target="_blank" >RIV/00216305:26210/16:PU120392 - isvavai.cz</a>

Výsledek na webu

<a href="https://ieeexplore.ieee.org/document/7760861" target="_blank" >https://ieeexplore.ieee.org/document/7760861</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1109/TSP.2016.7760861" target="_blank" >10.1109/TSP.2016.7760861</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Traveling Salesman Problem Optimization by Means of Graph-based Algorithm

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Traveling Salesman Problem Optimization by Means of Graph-based Algorithm

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/LO1401" target="_blank" >LO1401: Interdisciplinární výzkum bezdrátových technologií</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2016

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Proceedings of the 39th International Conference on Telecommunications and Signal Processing (TSP)

ISBN

978-1-5090-1287-9

ISSN

—

e-ISSN

—

Počet stran výsledku

4

Strana od-do

207-210

Název nakladatele

Neuveden

Místo vydání

Vienna, Austria

Místo konání akce

Vídeň

Datum konání akce

27. 6. 2016

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

000390164000043