Optimizacija ruta vozila za potrebe istraživanja kvalitete mobilne mreže primjenom algoritama za rješavanje problema trgovačkog putnika

master's thesis

• Title (english): Vehicle Routes Optimization for the Purpose of Mobile Network Quality Research by Applying Algorithms for Travelling Salesman Problem
• Author: Zoran Dukić
• Mentor: Juraj Fosin (mentor)
• Committee member: Štefica Mrvelj (predsjednik povjerenstva)
• Committee member: Marko Matulin (član povjerenstva)
• Committee member: Tonči Carić (član povjerenstva)
• Granter: University of Zagreb; Faculty of Transport and Traffic Sciences; (Independent chairs); (Chair of Applied Mathematics and Statistics); Zagreb
• Defense date and country: 2017-09-21, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Traffic and Transport Technology; Postal and Telecommunications Traffic

Abstract

Cilj ovog diplomskog rada je pronaći rješenje po kojem se može minimizirati ukupna prijeđena udaljenost za poduzeće P3 Communications, koje se bavi istraživanjem kvalitete mobilne mreže. Da bi se dala generalna slika kvalitete mobilne mreže na nekom geografskom području, potrebno je provesti mjerenja različitih parametara na različitim mjestima, ali i na prometnicama koja povezuju ta mjesta. Često se radi o velikom broju mjesta koje treba posjetiti. Kako bi se obišla sva mjesta u što kraćem vremenu, poduzeće P3 Communications koristi više vozila. U svrhu minimiziranja prijeđene udaljenosti, izrađeno je programsko rješenje koje koristi algoritme za rješavanje problema trgovačkog putnika. Programsko rješenje koristi ukupno dva algoritma za rješavanje problema trgovačkog putnika i jedan algoritam za grupiranje. Prvi korišteni algoritam je algoritam k-srednjih vrijednosti, koji spada u algoritme particijskog grupiranja. Druga dva algoritma su algoritam najbližeg susjeda, koji spada u skupinu heurističkih algoritama, i 2-Opt algoritam koji poboljšava inicijalno rješenje dobiveno algoritmom najbližeg susjeda. Rješenja dobivena programskim rješenjem prikazana su slikama sučelja na kojem je iscrtana ruta kojom se svako vozilo treba kretati.

Abstract (english)

The aim of this Master's Thesis is to find a way how to minimize the total distance traveled by P3 Communications company, a company that conducts mobile network quality research. In order to give a general picture of the quality of a mobile network for some geographic area, it is necessary to perform measurements of different parameters at different places but also on the roads linking these places. It is often a great number of places that needs to be visited. To visit all places in the shortest amount of time, company P3 Communications uses more than one vehicle. For the purpose of minimizing the total traveled distance, a software solution has been developed using algorithms based on solving traveling salesman problem. The solution uses a total number of three algorithms, two which are used for solving traveling salesman problem and one algorithm used for clustering. Algorithm used for clustering is called K-means algorithm, which is one of the partitions algorithms. The other two algorithms are nearest neighbour algorithm, a heuristics algorithm, and 2-Opt algorithm, which improves the initial solution obtained by the nearest neighbour algorithm. The solutions provided by the software are shown on a graphical user interface on which different routes are drawn, for each vehicle separately.

• Keywords: problem trgovačkog putnika; istraživanje kvalitete mobilne mreže; algoritam najbližeg susjeda; 2-Opt algoritam; grupiranje
• Keywords (english): traveling salesman problem; mobile network quality research; nearest neighbour algorithm; 2-Opt algorithm
• Language: croatian
• URN:NBN: urn:nbn:hr:119:790638
• Study programme: Title: Traffic and Transport; specializations in: Road Traffic and Transport, Railway Traffic and Transport, Water Traffic and Transport, Air Traffic and Transport, Postal Traffic, Information and Communication Traffic, Urban Traffic and Transport; Course: Information and Communication Traffic; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra inženjer/inženjerka prometa (magistar/magistra inženjer/inženjerka prometa)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Repository: Faculty of Transport and Traffic Sciences
• Created on: 2017-11-24 13:20:31