求解第二类GTSP的距离矩阵重构遗传算法  

Genetic Algorithm of Distance Matrix Remodeling for Solving the Second Kind of GTSP

作　　者：谭阳[1] 郝志峰[1,2] 黄翰[3] 赵森[1,4] 

机构地区：[1]华南理工大学计算机科学与工程学院,广东广州510006 [2]广东工业大学计算机学院,广东广州510006 [3]华南理工大学软件学院,广东广州510006 [4]暨南大学计算机科学系,广东广州510632

出　　处：《华南理工大学学报（自然科学版）》2013年第3期29-34,共6页Journal of South China University of Technology(Natural Science Edition)

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

摘　　要：目前第二类广义旅行商问题(GTSP)求解方法少,仅有的一些方法也存在运算复杂度高等缺陷,为此,文中通过分析距离矩阵的性质,提出了一种重构距离矩阵的算法,将第二类GTSP转化为第一类GTSP,然后利用混合染色体遗传算法求解转化后的第一类GTSP,从而间接求解了原问题(第二类GTSP).通过转化,大大提高了求解的精度,降低了运算的复杂度.最后,采用文中提出的算法对TSP问题库内的14个基准问题构成的第二类GTSP进行了测试,结果表明该算法可以有效地进行求解.Considering the lack of solving methods and the high computation complexity of the existing methods of the second kind of GTSP （ Generalized Traveling Salesman Problem） , an algorithm to remodel the distance matrix is presented by analyzing the characters of distance matrix, which converts the second kind of GTSP into the first kind, 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 increases the solution accuracy and decreases the computation complexity significantly. Moreover, according to the tested results of the second kind of GTSP composed of 14 benchmark problems from the TSPLIB, it is found that the pro- posed algorithm is effective.

关 键 词：广义旅行商问题 第二类广义旅行商问题 距离矩阵重构 遗传算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]