Solving Geographic Travelling Salesman Problem Based on Space Transformation

One of the most important optimization problem in combinatorial algorithms is Travelling Salesman Problem. This is due to its practical usages, especially in geospatial information technology. It is proved that the problem complexity is NP-Hard, but many heuristic methods are presented for practical applications. In this paper, the space transformation method is used to transform a geographic instance of travelling salesman problem into a simpler Euclidean one, such that traditional heuristics can be applied more successfully. Additionally, a heuristic technique to solve the transformed instance is introduced. The results confirm the superiority of the proposed method in terms of both the tour length and running time of the method in comparison with similar techniques.