A Polynomial Time Algorithm for Solving the Shortest Circuit of China Traveling Salesman Problem

To present a new polynomial time algorithm for China traveling salesman problem, first, point set was partitioned into a number of subpoint sets by using convex hull and medial axis. Then the method for solving the convex hulls of subpoint sets and partitioning the remaining subsets was repeatedly used to obtain a subpath through the subpoint set. Finally, the subpaths were joined to form a circuit. The time complexity of the new algorithm is O(n2lbn). And its application to China traveling salesman problem will give the shortest circuit 15404 km in length. There exists polynomial time algorithm to solve China traveling salesman problem and obtain the shortest circuit.