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

master's thesis

• Title (english): Heuristic Methods for the Traveling-Salesman Problem
• Author: Dorian Šulc
• Mentor: Ante Đerek (mentor)
• Committee member: Ante Đerek (predsjednik povjerenstva)
• Committee member: Domagoj Jakobović (član povjerenstva)
• Committee member: Alan Jović (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2017-07-10, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

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.

Abstract (english)

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.

• Keywords: trgovački; putnik; Lin-Kernighan; heuristika
• Keywords (english): traveling; salesman; Lin-Kernighan; heuristic
• Language: croatian
• URN:NBN: urn:nbn:hr:168:226211
• Study programme: Title: Computing; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra inženjer/inženjerka računarstva (magistar/magistra inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2019-03-14 01:28:28