Primjena metaheuristike tabu pretraživanja kod rješavanja problema trgovačkog putnika

undergraduate thesis

• Title (english): Applicability of the Tabu Search Metaheuristic in Solving the Traveling Salesman Problem
• Author: Sven Srebot
• Mentor: Lea Skorin-Kapov (mentor)
• Committee member: Lea Skorin-Kapov (predsjednik povjerenstva)
• Committee member: Tomislav Grgić (član povjerenstva)
• Committee member: Ivan Slivar (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2016-09-05, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

Cilj ovog rada je primijeniti algoritam tabu pretraživanja na problem trgovačkog putnika i analizirati utjecaj pojedinih parametara pretraživanja na kvalitetu rješenja i trajanje izvođenja algoritma. Problem trgovačkog putnika spada u skupinu NP-teških problema. Rješenje problema trgovačkog putnika egzaktnim algoritmom nije moguće naći u polinomnom vremenu, zbog čega se za rješavanje problema trgovačkog putnika često koriste metaheuristike. Metaheuristike se koriste za pronalazak dovoljno dobrog rješenja u razumnom vremenu. Tabu pretraživanje je iterativna metaheuristika zasnovana na pojedinačnom rješenju, koja prilikom pretraživanja koristi pamćenje. Tabu pretraživanje je čest pristup rješavanju problema trgovačkog putnika.

Abstract (english)

The goal of this thesis is to apply the tabu search algorithm in solving the travelling salesman problem, and to analyse the influence of the search parameters on the quality of solution and algorithm execution time. The travelling salesman problem belongs to the class of NP-hard optimization problems. Solutions to the travelling salesman problem cannot be found by exact methods in polynomial time, and because of that metaheuristics are often used to solve this class of problem. Metaheuristics are used to find acceptable solutions in reasonable time. Tabu search is a single solution-based iterative metaheuristic, which uses memory during the search. Tabu search is a common approach to solving the travelling salesman problem.

• Keywords: problem trgovačkog putnika; tabu pretraživanje
• Keywords (english): travelling salesman problem; tabu search
• Language: croatian
• URN:NBN: urn:nbn:hr:168:081617
• Study programme: Title: 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 resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2018-02-06 11:54:26