Vehicle Routes Optimization for the Purpose of Mobile Network Quality Research by Applying Algorithms for Travelling Salesman Problem

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.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