Back to search

Institutional Repository of Vilnius University

Euristinių algoritmų palyginimas keliaujančio pirklio uždaviniui /

Abstract

dc:description

The 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.*

Chain of custody

source
Harvested from
Vilnius University
Base URL
epublications.vu.lt/oai
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Rudys, Petras Liubartas,. Euristinių algoritmų palyginimas keliaujančio pirklio uždaviniui /. Institutional Repository of Vilnius University, 2025. https://repository.vu.lt/VU:ELABAETD229555651&prefLang=en_US