An Improved Greedy Heuristic Based on Solving Traveling Salesman Problem
Chun Jin · Yunchou yu guanli · 2012
In this paper,we analyze the properties of the classic construction heuristic GR.It is found that the main disadvantage of GR is that the edges added by GR at last are too long,resulting in a poor tour.Thus an approach transforming distance matrix(TDM)is proposed to improve the tour quality of GR,based on the theory of Held Karp model.As a consequence,GR combining TDM(GR-TDM)results in an efficient and effective heuristic,and GR-TDM overcomes significantly the disadvantage of GR.The experimental results on 40 instances from TSPLIB and TSP Challenge website show that GR-TDM is slower by 0.5～2% than GR for all instances,but the average tour quality of GR-TDM is better by 43% than that of GR.Moreover,GR-TDM is the first class heuristic among existing construction heuristics by comparing their tour quality and running time.