prikaz prve stranice dokumenta Primjena Lin-Kernighan-Helsgaun TSP solvera na probleme usmjeravanja vozila
No public access
undergraduate thesis
Primjena Lin-Kernighan-Helsgaun TSP solvera na probleme usmjeravanja vozila
Zagreb: University of Zagreb, Faculty of Electrical Engineering and Computing, 2019. urn:nbn:hr:168:500098
Ivanković, Marko
University of Zagreb
Faculty of Electrical Engineering and Computing

Institutional repository: FER Repository

Cite this document

Ivanković, M. (2019). Primjena Lin-Kernighan-Helsgaun TSP solvera na probleme usmjeravanja vozila (Undergraduate thesis). Zagreb: University of Zagreb, Faculty of Electrical Engineering and Computing. Retrieved from https://urn.nsk.hr/urn:nbn:hr:168:500098

Ivanković, Marko. "Primjena Lin-Kernighan-Helsgaun TSP solvera na probleme usmjeravanja vozila." Undergraduate thesis, University of Zagreb, Faculty of Electrical Engineering and Computing, 2019. https://urn.nsk.hr/urn:nbn:hr:168:500098

Ivanković, Marko. "Primjena Lin-Kernighan-Helsgaun TSP solvera na probleme usmjeravanja vozila." Undergraduate thesis, University of Zagreb, Faculty of Electrical Engineering and Computing, 2019. https://urn.nsk.hr/urn:nbn:hr:168:500098

Ivanković, M. (2019). 'Primjena Lin-Kernighan-Helsgaun TSP solvera na probleme usmjeravanja vozila', Undergraduate thesis, University of Zagreb, Faculty of Electrical Engineering and Computing, accessed 28 June 2024, https://urn.nsk.hr/urn:nbn:hr:168:500098

Ivanković M. Primjena Lin-Kernighan-Helsgaun TSP solvera na probleme usmjeravanja vozila [Undergraduate thesis]. Zagreb: University of Zagreb, Faculty of Electrical Engineering and Computing; 2019 [cited 2024 June 28] Available at: https://urn.nsk.hr/urn:nbn:hr:168:500098

M. Ivanković, "Primjena Lin-Kernighan-Helsgaun TSP solvera na probleme usmjeravanja vozila", Undergraduate thesis, University of Zagreb, Faculty of Electrical Engineering and Computing, Zagreb, 2019. Available at: https://urn.nsk.hr/urn:nbn:hr:168:500098

Metadata
TitlePrimjena Lin-Kernighan-Helsgaun TSP solvera na probleme usmjeravanja vozila
Title (english)An Application of the Lin-Kernighan-Helsgaun TSP Solver for Vehicle Routing Problems
AuthorMarko Ivanković
MentorJosipa Pina Milišić (mentor)
Committee memberJosipa Pina Milišić (predsjednik povjerenstva)
Committee memberAndrea Aglić Aljinović (član povjerenstva)
Committee memberTomislav Burić (član povjerenstva)
GranterUniversity of Zagreb
Faculty of Electrical Engineering and Computing
Zagreb
Defense date and country2019-09-06, Croatia
Scientific / art field,
discipline and subdiscipline		TECHNICAL SCIENCES
Computing
Abstract
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).
Abstract (english)
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.
Keywords
Keywords (english)
Languagecroatian
URN:NBNurn:nbn:hr:168:500098
Study programmeTitle: Computing
Study programme type: university
Study level: undergraduate
Academic / professional title: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva)
Type of resourceText
File originBorn digital
Access conditionsClosed access
Terms of useLicence In copyright icon
Public note
Created on2020-01-07 18:32:47