TSP algorithm based on two dimensional convex hull
Wenyong Zhou · Jisuanji gongcheng yu sheji · 2009
The 2D-convex hull refers to the minimal simple polygon consisting of all the points of the planar set and is applied widely in GIS.TSP algorithm based on 2D convex hull is proposed by integrating 2D-convex hull with TSP,firstly,the convex hull of all city points,which is a circuit that some of cities cross and the rest lies inside,is constructed by using the quick algorithm for convex hull,the rest cities are inserted into the circuit and formed the new one whose incremental length is minimal until the circuit goes through all the cities.Experiment result s on TSPL IB indicated that the proposed algorithms can achieve the solution of TSP quickly.