A hybrid minimum spanning tree method for traveling salesman problem
Hehua Li1, Wei Xiong1, Yong Wang2
COMPUTER MODELLING & NEW TECHNOLOGIES 2014 18(12C) 40-45
1Institute of Information Security Technology, Chongqing College of Electronic Engineering, Chongqing 401331, China
2North China Electric Power University, Beijing 102206, China
Traveling salesman problem (TSP) has a wide range of applications in communication, transportation, manufacturing etc. However, it is proven to be NP-complete in mathematics. An approximate method based on the Minimum Spanning Tree (MST) with an optimal four-vertex path is presented for the triangle TSP. We first compute the MST with a complete weighted graph. Then an Eulerian graph is generated by doubling the edges of the MST from an initial vertex. The optimal four-vertex path is used to simplify the Eulerian graph into a Hamiltonian cycle. Different from the common MST heuristics for TSP, all the generated four-vertex paths in the Hamiltonian cycle are the optimal four-vertex paths. Therefore, the approximation computed with the hybrid MST method is generally shorter than that produced with the common MST heuristics. The experiments for the Euclidean TSP examples also give the same conclusion.