Institutional Repository of Vilnius University
Euristinių algoritmų palyginimas keliaujančio pirklio uždaviniui /
Abstract
dc:descriptionThe travelling salesman problem (abbreviated as TSP) is a classical optimisation problem in mathematics and computer science, mainly in graph theory. The objective of this problem is to construct the shortest route between a given number of cities, visiting each city once, and returning to the city in which the journey began. In this paper, the following heuristic algorithms for TSP are implemented and compared: a convexhull cheapest insertion algorithm, an innovative all convexhull cheapest insertion algorithm, a conventional genetic algorithm and a modified version of it that uses a convexhull for the generation of the initial population. The innovative algorithm is designed and studied in order to reduce the running time of the conventional convexhull cheapest insertion algorithm, and the modified version of the genetic algorithm is implemented and studied to reduce the length of the estimated route compared with the conventional convexhull cheapest insertion algorithm. The implemented algorithms were tested using data sets from the TSPLIB library and randomly generated point lists. The results show that, at least as implemented in this work, a modified version of the genetic algorithm, that uses a convex hull to generate the initial population, computes an even longer route. It has also been shown that the running time of the innovative all convexhull cheapest insertion algorithm is significantly lower than of the conventional convexhull cheapest insertion algorithm, however the caclulated path is longer.
Degree
thesis:*- Grantor dc:publisher
- Institutional Repository of Vilnius University
- Year dc:date
- 2025
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Rudys, Petras Liubartas,
Rights
dc:rights- Statement dc:rights
-
- info:eu-repo/semantics/openAccess
- Language dc:language
- lit
Identifiers
dc:identifier.*- Repository record dc:identifier
- https://repository.vu.lt/VU:ELABAETD229555651&prefLang=en_US