Heuristički algoritmi za geometrijski problem trgovačkog putnika

završni rad

• Naslov (engleski): Heuristic Algorithms for Geometric Traveling Salesman Problem
• Autor: Petar Mihalj
• Mentor: Mario Osvin Pavčević (mentor)
• Član povjerenstva: Mario Osvin Pavčević (predsjednik povjerenstva)
• Član povjerenstva: Mario Krnić (član povjerenstva)
• Član povjerenstva: Domagoj Kovačević (č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: 2019-07-12, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

Problem trgovačkog putnika (TSP) poznati je problem kombinatorne optimizacije koji se bavi određivanjem hamiltonovskog ciklusa najmanje težine u danom grafu. Istražujemo heurističke algoritme za posebnu vrstu ovog problema - geometrijski TSP (GTSP). GTSP je poseban slučaj TSP-a koji zahtijeva da vrhovima odgovaraju točke euklidskog prostora i da težine bridova odgovaraju udaljenostima između točaka.
Implementirali smo i egzaktne i heurističke algoritme, zajedno sa potrebnim strukturama podataka.
Nakon procjene performansi heurističkih algoritama na uniformnim skupovima podataka, testirali smo ih na grafovima iz TSPLIB baze grafova. Heuristički algoritmi dali su relativno dobre rezultate za neke primjene, i implementirani sa prikladnim strukturama podataka, pokazali iznimnu brzinu izvođenja.

Sažetak (engleski)

Travelling salesman problem (TSP) is a well known combinatorial optimisation problem concerned with finding a Hamiltonian cycle with minimum weight in a given graph. We discuss heuristic algorithms for a specific type of this problem - geometric TSP (GTSP). GTSP is a specific case of TSP that requires vertices to be assigned points in Euclidean space and edge weights to be equal to Euclidean distances between points.
We have implemented both exact and heuristic algorithms, along with required data structures.
After evaluating the performance of heuristic algorithms on uniform datasets, we have tested algorithms on graphs in TSPLIB graph library. Heuristic algorithms have given relatively good results for some applications, and have shown exceptional runtime speed when implemented using appropriate data structures.

• Ključne riječi: Geometrijski problem trgovačkog putnika; heuristički algoritmi; kombinatorna optimizacija
• Ključne riječi (engleski): Geometric travelling salesman problem; heuristic algorithms; combinatorial optimisation
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:998359
• 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: 2020-01-07 20:22:15