基于候选集和分段优化的蚁群算法对TSP问题的求解

作者：高晶英; 姜静清; 宋初一; 裴志利

来源：内蒙古民族大学学报(自然科学版), 2014, (02): 150-152+249.

DOI：10.14045/j.cnki.15-1220.2014.02.012

• 蚁群算法
• Delaunay三角剖分
• 分段优化
• 旅行商问题 Ant colony algorithm
• Delaunay triangulation
• Partitioned optimization
• Traveling salesman problem

传统的蚁群算法在求解规模比较大的旅行商问题(Traveling Salesman Problem,TSP)时遇到时间和精度的双重挑战.针对这些不足,提出了一种求解规模比较大的TSP问题的算法,该算法首先采用Delaunay三角剖分来建立每一个城市的候选城市集,然后在蚂蚁找到的最优路径上做优化处理,进一步提高解的质量.实验表明该算法收敛速度快,与传统的蚁群算法比较,求解效率有了显著的提高.

• 出版日期2014
• 单位内蒙古民族大学