20.500.12556/RUL-119680 Pregled hevristik za problem trgovskega potnika Overview of heuristics for the traveling salesman problem 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. 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. hevristika Problem trgovskega potnika simetrični Problem trgovskega potnika Lokalno iskanje k-opt Lin-Kerninghan Simulirano ohlajanje Kolonija mravelj Optimizacija z roji delcev Oponašanje volkov heuristic Traveling Salesman Problem symetric Traveling Salesman Problem Local search k-opt Lin-Kerninghan Simulated annealing Ant colony Particle swarm optimization Wolfpack true false false Slovenski jezik Angleški jezik Diplomsko delo/naloga 2020-09-10 15:05:13 2020-09-10 15:05:18 2024-02-02 13:52:57 0000-00-00 00:00:00 2020 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 26661 30748419 Gaberc_artenjak_Jakob_-_Pregled_hevristik_za_problem_trgovskega_potnika.pdf Gaberc_artenjak_Jakob_-_Pregled_hevristik_za_problem_trgovskega_potnika.pdf 1 564D62E9E6FCA4967E7E6F1FE8966791 f9ae66e607dabeb29f541999e92edbd417ebdc87498243f3a8163139cca1660a e4833a2e-a1b9-11eb-a523-00155dcfd717 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=134405 Fakulteta za računalništvo in informatiko 0 0 0