Pregled hevristik za problem trgovskega potnika

diplomsko delo

Jakob Gaberc Artenjak (Author), Borut Robič (Mentor)

Abstract

Problem trgovskega potnika je iskanje najkrajše poti med vsemi mesti, kjer obiščemo vsako mesto natanko enkrat in se vrnemo nazaj na začetno mesto. Na problem lahko gledamo kot na iskanje najcenejšega cikla v grafu, ki obišče vse točke natanko enkrat. Pridobivanje optimalne rešitve problema trgovskega potnika je praktično neuporabno zaradi časovne zahtevnosti problema. Hevristični algoritmi so dobra alternativa optimalnemu reševanju problema, saj pridobijo rešitev v praktično izvedljivem času, a izgubijo jamstvo optimalne rešitve. Uvod diplomske naloge vsebuje osnovni opis problema trgovskega potnika. Temu sledijo primeri praktične uporabe problema, natančnejši opis problema, opredelitev hevristik in opis testnega okolja. Glavni del naloge vsebuje šest hevrističnih algoritmov, ki smo jih implementirali in jih testirali. Izbrali smo algoritem Lokalnega iskanja z operacijo k-opt, Lin-Kernighanov algoritem, algoritem Simuliranega ohlajanja, algoritem Kolonije mravelj, algoritem Optimizacije z roji delcev in algoritem Oponašanja volkov. Končni del naloge vsebuje primerjavo eksperimentalnih rezultatov in komentar nad uporabljeno metodologijo za primerjavo algoritmov.

Keywords

hevristika;problem trgovskega potnika;simetrični problem trgovskega potnika;lokalno iskanje;k-opt;Lin-Kerninghan;simulirano ohlajanje;optimizacija z roji delcev;oponašanje volkov;računalništvo in informatika;univerzitetni študij;diplomske naloge;

Data

Language:	Slovenian
Year of publishing:	2020
Typology:	2.11 - Undergraduate Thesis
Organization:	UL FRI - Faculty of Computer and Information Science
Publisher:	[J. Gaberc Artenjak]
UDC:	004.023(043.2)
COBISS:	30748419
Views:	934
Downloads:	153
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary title:	Overview of heuristics for the traveling salesman problem
Secondary abstract:	The Traveling Salesman Problem is finding the shortest path through all the cities, where each city is visited precisely once, while the first and the last city are the same. This can be formulated as searching for the shortest cycle in a graph which visits each vertex exactly once. Finding the optimal solution is practically fruitless due to the time complexity of the problem. Heuristic algorithms are good alternatives to algorithms, which search for the optimal solution, because a solution can be found in a practically achievable time frame; however, the guarantee of the solution being optimal is lost. The introduction of this work includes a basic description of The Traveling Salesman Problem, which is followed by a list of practical applications, a detailed description of the problem, the classification of heuristic algorithms and the details of the experimental environment. The main part of this work includes six algorithms, which were implemented and tested. The selected algorithms are Local Search with the k-opt operation; Lin-Kernighan algorithm; Simulated Annealing; Ant Colony Algorithm; Particle Swarm Optimization and Wolfpack algorithm. The final part of this work is a comparison of the results from each algorithm and a commentary on the methodology that was used for the comparison of the algorithms.
Secondary keywords:	heuristic;traveling salesman problem;symetric traveling salesman problem;local search;k-opt;Lin-Kerninghan;simulated annealing;ant colony;particle swarm optimization;wolfpack;computer and information science;diploma thesis;
Type (COBISS):	Bachelor thesis/paper
Study programme:	1000468
Embargo end date (OpenAIRE):	1970-01-01
Thesis comment:	Univ. v Ljubljani, Fak. za računalništvo in informatiko
Pages:	80 str.
ID:	12031375