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

摘要：

目前第二类广义旅行商问题(GTSP)求解方法少,仅有的一些方法也存在运算复杂度高等缺陷,为此,文中通过分析距离矩阵的性质,提出了一种重构距离矩阵的算法,将第二类GTSP转化为第一类GTSP,然后利用混合染色体遗传算法求解转化后的第一类GTSP,从而间接求解了原问题(第二类GTSP).通过转化,大大提高了求解的精度,降低了运算的复杂度.最后,采用文中提出的算法对TSP问题库内的14个基准问题构成的第二类GTSP进行了测试,结果表明该算法可以有效地进行求解.

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

所属期刊栏目：41

分类号：TP301.6(计算技术、计算机技术)

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

在线出版日期：2013-05-28（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：29-34