Traveling Salesman Problem Optimization by Means of Graph-based Algorithm

Result code in 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>

Result on the web

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

Result language

angličtina

Original language name

Traveling Salesman Problem Optimization by Means of Graph-based Algorithm

Original language description

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.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

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

Project

<a href="/en/project/LO1401" target="_blank" >LO1401: Interdisciplinary Research of Wireless Technologies</a><br>

Continuities

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

Publication year

2016

Confidentiality

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

Article name in the collection

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

ISBN

978-1-5090-1287-9

ISSN

—

e-ISSN

—

Number of pages

4

Pages from-to

207-210

Publisher name

Neuveden

Place of publication

Vienna, Austria

Event location

Vídeň

Event date

Jun 27, 2016

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

000390164000043