prikaz prve stranice dokumenta Primjena Lin-Kernighan-Helsgaun TSP solvera na probleme usmjeravanja vozila
Rad nije dostupan
završni rad
Primjena Lin-Kernighan-Helsgaun TSP solvera na probleme usmjeravanja vozila
Zagreb: Sveučilište u Zagrebu, Fakultet elektrotehnike i računarstva, 2019. urn:nbn:hr:168:500098
Ivanković, Marko
Sveučilište u Zagrebu
Fakultet elektrotehnike i računarstva

Institucijski repozitorij: Repozitorij FER-a

Citirajte ovaj rad

Ivanković, M. (2019). Primjena Lin-Kernighan-Helsgaun TSP solvera na probleme usmjeravanja vozila (Završni rad). Zagreb: Sveučilište u Zagrebu, Fakultet elektrotehnike i računarstva. Preuzeto s https://urn.nsk.hr/urn:nbn:hr:168:500098

Ivanković, Marko. "Primjena Lin-Kernighan-Helsgaun TSP solvera na probleme usmjeravanja vozila." Završni rad, Sveučilište u Zagrebu, Fakultet elektrotehnike i računarstva, 2019. https://urn.nsk.hr/urn:nbn:hr:168:500098

Ivanković, Marko. "Primjena Lin-Kernighan-Helsgaun TSP solvera na probleme usmjeravanja vozila." Završni rad, Sveučilište u Zagrebu, Fakultet elektrotehnike i računarstva, 2019. https://urn.nsk.hr/urn:nbn:hr:168:500098

Ivanković, M. (2019). 'Primjena Lin-Kernighan-Helsgaun TSP solvera na probleme usmjeravanja vozila', Završni rad, Sveučilište u Zagrebu, Fakultet elektrotehnike i računarstva, citirano: 27.12.2024., https://urn.nsk.hr/urn:nbn:hr:168:500098

Ivanković M. Primjena Lin-Kernighan-Helsgaun TSP solvera na probleme usmjeravanja vozila [Završni rad]. Zagreb: Sveučilište u Zagrebu, Fakultet elektrotehnike i računarstva; 2019 [pristupljeno 27.12.2024.] Dostupno na: https://urn.nsk.hr/urn:nbn:hr:168:500098

M. Ivanković, "Primjena Lin-Kernighan-Helsgaun TSP solvera na probleme usmjeravanja vozila", Završni rad, Sveučilište u Zagrebu, Fakultet elektrotehnike i računarstva, Zagreb, 2019. Dostupno na: https://urn.nsk.hr/urn:nbn:hr:168:500098

Za citiranje koristite ovu mrežnu adresu: https://urn.nsk.hr/urn:nbn:hr:168:500098
Podaci o radu
NaslovPrimjena Lin-Kernighan-Helsgaun TSP solvera na probleme usmjeravanja vozila
Naslov (engleski)An Application of the Lin-Kernighan-Helsgaun TSP Solver for Vehicle Routing Problems
AutorMarko Ivanković
MentorJosipa Pina Milišić (mentor)
Član povjerenstvaJosipa Pina Milišić (predsjednik povjerenstva)
Član povjerenstvaAndrea Aglić Aljinović (član povjerenstva)
Član povjerenstvaTomislav Burić (član povjerenstva)
Ustanova koja je dodijelila
akademski / stručni stupanj		Sveučilište u Zagrebu
Fakultet elektrotehnike i računarstva
Zagreb
Datum i država obrane2019-09-06, Hrvatska
Znanstveno / umjetničko
područje, polje i grana		TEHNIČKE ZNANOSTI
Računarstvo
Sažetak
Poznati kombinatorni problem trgovačkog putnika klasificira se kao NP-potpun problem. Različitim heuristikama i algoritmima, pa čak i za velik broj gradova, moguće je dobiti rješenje u razumnom vremenu. Trenutno najbolja tura za TSP problem koji uključuje sve gradove svijeta iznosi 7,515,772,107, a pronašao ju je Keld Helsgaun. Završni rad se zasniva na detaljnoj implementaciji i analizi Lin-Kernighan-Helsgaun algoritma, Lin-Kernighan algoritma i pripadajućih heuristika te metode grananja i razgranavanja. Svaki algoritam opisan je svojim Python i pseudokodom, a na kraju i vizualno reprezentiran alatima iz matplotlib-a. Također, razmatra se proširena verzija Lin-Kernighan-Helsgaun algoritma namjenjena za rješavanje problema za navigaciju vozila (VRP).
Sažetak (engleski)
A well-known traveling salesman problem is a combinatorial problem classified as a NP-complete problem. By applying different heuristics and algorithms, even for a large number of cities, it is possible to get a solution in a reasonable time. Currently, length of the best TSP tour that includes all cities in the world is 7,515,772,107, and has been found by Keld Helsgaun. This bachelor thesis is based on the detailed implementation and analysis of Lin-Kernighan-Helsgaun algorithm, Lin-Kernighan algorithm and related heuristics, and branch and bound method. Each algorithm is described by its Python code and pseudocode, and ultimately is visually represented by matplotlib tools. Also, an extended version of the Lin-Kernighan-Helsgaun algorithm designed to solve vehicle navigation problems (VRP) is considered.
Ključne riječi
Ključne riječi (engleski)
Jezikhrvatski
URN:NBNurn:nbn:hr:168:500098
Studijski programNaziv: Računarstvo
Vrsta studija: sveučilišni
Stupanj studija: preddiplomski
Akademski / stručni naziv: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (univ.bacc.ing.comp.)
Vrsta resursaTekst
Način izrade datotekeIzvorno digitalna
Prava pristupaZatvoreni pristup
Uvjeti korištenjaIkona licence Zaštićeno autorskim pravom.
Javna napomena
Datum i vrijeme pohrane2020-01-07 18:32:47