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

završni rad

• Naslov (engleski): Applicability of the Tabu Search Metaheuristic in Solving the Traveling Salesman Problem
• Autor: Sven Srebot
• Mentor: Lea Skorin-Kapov (mentor)
• Član povjerenstva: Lea Skorin-Kapov (predsjednik povjerenstva)
• Član povjerenstva: Tomislav Grgić (član povjerenstva)
• Član povjerenstva: Ivan Slivar (č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: 2016-09-05, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

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.

Sažetak (engleski)

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.

• Ključne riječi: problem trgovačkog putnika; tabu pretraživanje
• Ključne riječi (engleski): travelling salesman problem; tabu search
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:081617
• Studijski program: Naziv: 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 resursa: tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2018-02-06 11:54:26