Pregled hevristik za problem trgovskega potnika

diplomsko delo

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

Povzetek

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.

Ključne besede

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;

Podatki

Jezik:	Slovenski jezik
Leto izida:	2020
Tipologija:	2.11 - Diplomsko delo
Organizacija:	UL FRI - Fakulteta za računalništvo in informatiko
Založnik:	[J. Gaberc Artenjak]
UDK:	004.023(043.2)
COBISS:	30748419
Št. ogledov:	934
Št. prenosov:	153
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Angleški jezik
Sekundarni naslov:	Overview of heuristics for the traveling salesman problem
Sekundarni povzetek:	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.
Sekundarne ključne besede:	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;
Vrsta dela (COBISS):	Diplomsko delo/naloga
Študijski program:	1000468
Konec prepovedi (OpenAIRE):	1970-01-01
Komentar na gradivo:	Univ. v Ljubljani, Fak. za računalništvo in informatiko
Strani:	80 str.
ID:	12031375