Fast approximation of Euclidean TSP

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.