Journal of South China University of Technology (Natural Science Edition) ›› 2013, Vol. 41 ›› Issue (3): 29-34.doi: 10.3969/j.issn.1000-565X.2013.03.005

• Computer Science & Technology • Previous Articles     Next Articles

Genetic Algorithm of Distance Matrix Remodeling for Solving theSecond Kind of GTSP

Tan Yang1 Hao Zhi-feng1,2 Huang Han3 Zhao Sen1,4   

  1. 1.School of Computer Science and Engineering,South China University of Technology,Guangzhou 510006,Guangdong,China;2.Faculty of Computer,Guangdong University of Technology,Guangzhou 510006,Guangdong,China;3.School of Software Engineering,South China University of Technology,Guangzhou 510006,Guangdong,China;4.Department of Computer Science,Jinan University,Guangzhou 510632,Guangdong,China
  • Received:2012-06-08 Revised:2012-11-10 Online:2013-03-25 Published:2013-02-01
  • Contact: 谭阳(1978-)，男，博士生，主要从事进化算法、机器学习、模式识别、人工智能研究． E-mail:tanyang26@126.com
  • About author:谭阳(1978-)，男，博士生，主要从事进化算法、机器学习、模式识别、人工智能研究．
  • Supported by:

    国家自然科学基金资助项目( 61070033，61100148) ; 广东省自然科学基金资助项目( 9251009001000005，S2011040004804)

PDF

933

Abstract:

Considering the lack of solving methods and the high computation complexity of the existing methods ofthe second kind of GTSP ( Generalized Traveling Salesman Problem) ,an algorithm to remodel the distance matrix ispresented by analyzing the characters of distance matrix,which converts the second kind of GTSP into the firstkind,and then solves the converted first kind of GTSP by using the hybrid-chromosome genetic algorithm.Thus,the second kind of GTSP is successfully solved in an indirect mode.The results indicate that the conversion increasesthe solution accuracy and decreases the computation complexity significantly.Moreover,according to the testedresults of the second kind of GTSP composed of 14 benchmark problems from the TSPLIB,it is found that the proposedalgorithm is effective.

Key words: generalized traveling salesman problem, second kind of GTSP, distance matrix remodeling, geneticalgorithm

CLC Number: