Heurističke metode rješavanja problema trgovačkog putnika

diplomski rad

• Naslov (engleski): Heuristic Methods for the Traveling-Salesman Problem
• Autor: Dorian Šulc
• Mentor: Ante Đerek (mentor)
• Član povjerenstva: Ante Đerek (predsjednik povjerenstva)
• Član povjerenstva: Domagoj Jakobović (član povjerenstva)
• Član povjerenstva: Alan Jović (č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 obrane: 2017-07-10, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

Problem trgovačkog putnika je NP-težak problem, ali ga se može dovoljno dobro riješiti u razumnom vremenu koristeći heuristike. U radu opisujemo jednu takvu po imenu Lin-Kernighan heuristika. Implementiramo i testiramo istu. Na temelju rezultata nudimo mišljenja i ideje kako ubrzati i efikasno implementirati novu inačicu. Provodimo temeljite testove i uspoređujemo se s drugim rješenjima. Dodatno, iskušavamo metodu koja ponovnim rješavanjem istog problema i prijenosom informacija između pokušaja unaprjeđuje konačna rješenja.
Konačni algoritam radi u izmjerenoj vremenskoj složenosti O(n1.9). Jedan pokušaj rješavanja potpuno povezanog grafa od 1000 čvorova traje svega nekoliko milisekundi dok je za 15 tisuća čvorova potrebno oko 300 milisekundi.

Sažetak (engleski)

Traveling salesman problem belongs to the class of NP-hard problems but, using heuristics, it can be solved well enough within reasonable time. In this paper we describe one such heuristic called Lin-Kernighan heuristic. We implement and test it. Based on results we offer ideas on how to speed up and efficiently implement a new version the algorithm. We perform extensive tests and compare ourselves with other solutions. Additionally, we try out a method which repeatedly solves the problem and uses the gained information through the process to yield better results.
The final algorithm has measured time complexity of O(n1.9). One trial for solving a 1000 node graph takes but a few milliseconds, while 15 thousand node problems take about 300 milliseconds.

• Ključne riječi: trgovački; putnik; Lin-Kernighan; heuristika
• Ključne riječi (engleski): traveling; salesman; Lin-Kernighan; heuristic
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:226211
• Studijski program: Naziv: Računarstvo; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra inženjer/inženjerka računarstva (mag.ing.comp.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2019-03-14 01:28:28