摘要
传统的蚁群算法在求解规模比较大的旅行商问题(Traveling Salesman Problem,TSP)时遇到时间和精度的双重挑战.针对这些不足,提出了一种求解规模比较大的TSP问题的算法,该算法首先采用Delaunay三角剖分来建立每一个城市的候选城市集,然后在蚂蚁找到的最优路径上做优化处理,进一步提高解的质量.实验表明该算法收敛速度快,与传统的蚁群算法比较,求解效率有了显著的提高.
Traditional ant colony algorithm for solving large scale traveling salesman problem（TSP）encounters the dual challenges of time and precision. For these shortcomings, this paper proposes an algorithm for TSP problem. This algorithm establishes a candidate city set based on Delaunay triangulation for every city. And then optimizes the opti-mal path to improve the quality of solution. The experiments show that compared with traditional ant colony algorithm, the proposed algorithm improves the convergence speed and solving efficiency.
出处
《内蒙古民族大学学报（自然科学版）》
2014年第2期150-152,249,共3页
Journal of Inner Mongolia Minzu University：Natural Sciences
基金
国家自然科学基金资助项目(61163034
61373067)
内蒙古自然科学基金资助项目(2013MS0910
2013MS0911)
关键词
蚁群算法
DELAUNAY三角剖分
分段优化
旅行商问题
Ant colony algorithm
Delaunay triangulation
Partitioned optimization
Traveling salesman problem
