A Simple Algorithm for Solving Travelling Salesman Problem

The traveling salesman problem (TSP) is a well known and important combinatorial optimization problem. Taking convex hull as a tool to find the shortest cycle to a TSP, this paper divides vertices representing cities into some nested Hamiltonian cycles without intersection and a residual set of vertices, presents a simple algorithm called Convex Partition and Gradual Insertion (CPGI) Algorithm, and in some cases proves that using CPGI algorithm the shortest cycle can be found. It is also proved in this paper that vertices in the first convex hull are of the same connecting order as in the shortest cycle. By means of the fact, search time for the shortest cycle can be reduced largely.