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

K-means Clustering Information Propagation Algorithm for Multiple Depots Multiple Traveling Salesman Problem

作　　者：程亚南 王晓峰[1,2] 刘凇佐 莫淳惠 CHENG Ya-nan;WANG Xiao-feng;LIU Song-zuo;MO Chun-hui(College of Computer Science and Engineering,North Minzu University,Yinchuan 750021,China;The Key Laboratory of Images&Graphics Intelligent Processing of State Ethnic Affairs Commission,North Minzu University,Yinchuan 750021,China)

机构地区：[1]北方民族大学计算机科学与工程学院,银川750021 [2]北方民族大学,图像图形智能处理国家民委重点实验室,银川750021

出　　处：《科学技术与工程》2022年第23期10146-10154,共9页Science Technology and Engineering

基　　金：国家自然科学基金(62062001,61762019,61862051,61962002);北方民族大学重大专项(ZDZX201901);宁夏自然科学基金(2020AAC03214,2020AAC03219,2019AAC03120,2019AAC03119)。

摘　　要：多旅行商问题在实际生活中有着较为广泛的应用价值,该问题的求解受到越来越多学者的关注。信息传播算法是一类求解组合优化问题最为有效的方法,基于K-means聚类技术,给出了求解多起点多旅行商问题(multiple depots multiple traveling salesman problem, MMTSP)的信息传播算法,该算法采用K-means聚类算法将旅行商问题进行聚类,从而形成若干不同类,对每一个类采用信息传播算法进行旅行商搜索,将每一个类的搜索结果进行综合,得到MMTSP问题的解。通过对旅行商标准测试数据集中的多种实例进行测试,并与ABC、ACO、PSO、IWO、TWPS、AC-PGA、STASA_2OPT和STASA 8种算法进行试验对比分析。结果表明本文算法最优值小于其他算法和算法稳定的优点。The multi-travelling salesman problem has a wide range of application value in real life, and the solution of this problem has attracted more and more scholars’ attention. The information propagation algorithm is the most effective method for solving combinatorial optimization problems. Based on K-means clustering technology, an information propagation algorithm for solving the multiple depots multiple traveling salesman problem(MMTSP) was given. The traveling salesman problem was clustered by K-means clustering algorithm to form several different classes. The information propagation algorithm was used for each class to conduct traveling salesman search, and the search results of each class were synthesized to obtain the solution of the MMTSP problem. By testing various instances in the standard test data set of traveling salesman, the eight algorithms with ABC, ACO, PSO, IWO, TWPS, AC-PGA, STASA_2 OPT and STASA were compared and analyzed, the results show that the optimal value of the algorithm in this paper is smaller than other algorithms and the advantages of the algorithm are stable.

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

分 类 号：TP301[自动化与计算机技术—计算机系统结构]