Heuristički algoritmi za geometrijski problem trgovačkog putnika

undergraduate thesis

• Title (english): Heuristic Algorithms for Geometric Traveling Salesman Problem
• Author: Petar Mihalj
• Mentor: Mario Osvin Pavčević (mentor)
• Committee member: Mario Osvin Pavčević (predsjednik povjerenstva)
• Committee member: Mario Krnić (član povjerenstva)
• Committee member: Domagoj Kovačević (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2019-07-12, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

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.

Abstract (english)

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.

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