求解多起点多旅行商问题的K-means聚类信息传播算法

摘要：

多旅行商问题在实际生活中有着较为广泛的应用价值,该问题的求解受到越来越多学者的关注.信息传播算法是一类求解组合优化问题最为有效的方法,基于K-means聚类技术,给出了求解多起点多旅行商问题(multiple depots multiple traveling salesman problem,MMTSP)的信息传播算法,该算法采用K-means聚类算法将旅行商问题进行聚类,从而形成若干不同类,对每一个类采用信息传播算法进行旅行商搜索,将每一个类的搜索结果进行综合,得到MMTSP问题的解.通过对旅行商标准测试数据集中的多种实例进行测试,并与ABC、ACO、PSO、IWO、TWPS、AC-PGA、STASA_2OPT和STASA 8种算法进行试验对比分析.结果表明本文算法最优值小于其他算法和算法稳定的优点.

关键词：旅行商问题、多旅行商问题、K-means聚类、信息传播算法

所属期刊栏目：22

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

资助基金：国家自然科学基金;国家自然科学基金;国家自然科学基金;国家自然科学基金;北方民族大学重大专项;宁夏自然科学基金项目;宁夏自然科学基金项目;宁夏自然科学基金项目;宁夏自然科学基金项目

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

页数：共9页

页码：10146-10154