Publication detail

Traveling Salesman Problem Optimization by Means of Graph-based Algorithm

ŠŤASTNÝ, J. ŠKORPIL, V. ČÍŽEK, L.

Original Title

Traveling Salesman Problem Optimization by Means of Graph-based Algorithm

English Title

Traveling Salesman Problem Optimization by Means of Graph-based Algorithm

Type

conference paper

Language

en

Original Abstract

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.

English abstract

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.

Keywords

Genetic algorithm; Graph-based algorithm; Traveling Salesman Problem; GLPA*; NP-Hard problem; logistics optimization; task scheduling

Released

27.06.2016

Location

Vienna, Austria

ISBN

978-1-5090-1287-9

Book

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

Pages from

207

Pages to

210

Pages count

4

BibTex


@inproceedings{BUT128496,
  author="Jiří {Šťastný} and Vladislav {Škorpil} and Lubomír {Čížek}",
  title="Traveling Salesman Problem Optimization by Means of Graph-based Algorithm",
  annote="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.",
  booktitle="Proceedings of the 39th International Conference on Telecommunications and Signal Processing (TSP)",
  chapter="128496",
  doi="10.1109/TSP.2016.7760878",
  howpublished="electronic, physical medium",
  year="2016",
  month="june",
  pages="207--210",
  type="conference paper"
}