一种求解对称TSP的简单候选集方法

摘要：

TSP（旅行商问题）作为一种解决组合优化问题的有效方法,在近几十年来受到了广泛的研究。理论证明它是一个典型的NP难问题,为了更快捷地求解,候选集方法在多种求解算法比如LKH算法中都有用到,一般是用于产生一个接近局部最优的初始解,较少用于寻路过程中。本文提出了一种新的简单的候选集方法,它采用一种新的距离度量,更好地符合了对称TSP的寻路规则。将其应用于最大最小蚁群算法（MMAS）的寻路过程中,实验结果表明针对对称TSP问题,该方法能比基本的MMAS取得更好的性能。这种候选集方法也可以用于其他求解对称TSP问题的进化计算。

关键词：对称TSP、蚁群优化、最大最小蚁群、候选集

所属期刊栏目：10

分类号：TP319.9(计算技术、计算机技术)

资助基金：国家自然科学基金项目60971120,61172165,71101096;广东省自然科学基金项目9251817204000001,S201101000849;深圳市科研项目JC201006020807A;深圳信息职业技术学院博士创新项目BC2009018

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

页数：共6页

页码：12-17