Please use this identifier to cite or link to this item:
https://www.um.edu.mt/library/oar/handle/123456789/76697
Title: | Fast approximation of Euclidean TSP |
Authors: | Glushkov, Nikola (2020) |
Keywords: | Traveling-salesman problem Vehicle routing problem Transportation -- Environmental aspects Genetic algorithms |
Issue Date: | 2020 |
Citation: | Glushkov, N. (2020). Fast approximation of Euclidean TSP (Bachelor's dissertation). |
Abstract: | Determining feasible routing paths is a substantial challenge in the humanitarian, civil, military, and commercial spheres. Specifically, finding a tour with lower cost on a road network is a principal concern in planning logistics. The essence of this problem is characterised by the Travelling Salesman Problem (TSP). One of the many applications of TSP is the Green Vehicle Routing Problem (G-VRP) which considers fuel tank capacity and refuelling stops. This study proposes an effective approach to the Euclidean TSP and G-VRP that utilises a Quad-Tree plane partitioning algorithm. The algorithm embeds all tour nodes on a plane, recursively partitions them into quad-tree squares and connects them to form a complete Hamiltonian cycle which is an approximate solution. The final step of the study involves comparing this Quad-Tree PTAS with another sample solution based on a Genetic Algorithm (GA) approach, as well as adapting the QT-PTAS to approximate G-VRP instances. The experiments are performed on real-life datasets of varying sizes. All the datasets are passed through the algorithms and the outcomes are analysed. The results obtained show that, for the first part of the experimentation the QT-PTAS consistently outperforms the GA in terms of tour length cost and computational time. The improvement in cost and time and the effectiveness of the QT-PTAS when compared to the GA approach grows with the size of the dataset. This may indicate that this improvement would increase with larger datasets. The QT-PTAS also provides reasonably fast approximations for the G-VRP instances. Therefore, the proposed QT-PTAS approach holds promise and may be applied effectively to other problems within the domain of combinatorial optimisation. |
Description: | B.Sc. IT (Hons)(Melit.) |
URI: | https://www.um.edu.mt/library/oar/handle/123456789/76697 |
Appears in Collections: | Dissertations - FacICT - 2020 Dissertations - FacICTCIS - 2020 |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
20BITCB005.pdf Restricted Access | 3.92 MB | Adobe PDF | View/Open Request a copy |
Items in OAR@UM are protected by copyright, with all rights reserved, unless otherwise indicated.