基于Spark的并行k均值聚类模拟退火算法求解MMTSP

来源：电子测量技术杂志2022年第20期北京时间：

作者：孙鉴，李昊，刘凇佐，刘品，陈攀，雷冰冰

单位：1.北方民族大学，计算机科学与工程学院，宁夏 银川 750021; 2.图像图形智能处理国家民委重点实验室, 宁夏 银川 750021

摘要：多起点闭回路多旅行商问题是旅行商问题的扩展。针对这个问题文中提出了一种基于Spark框架的并行k均值聚类模拟退火算法。该算法首先采用k均值聚类算法将所有城市分类，然后对应每个类建立一个旅行商问题，并通过一种改进的模拟退火算法对旅行商问题求解，MMTSP的解由这些类的最短路径之和计算得出。所提算法采用先聚类再执行模拟退火算法的求解策略可以极大的缩减模拟退火的搜索空间，并且由于Spark框架可以将聚类算法分好的若干类并行求解，从而更快的得到MMTSP问题的最优解。选取TSPLIB数据库中若干测试实例进行仿真实验，对求解精度和运行时间两个方面进行测试，与其他几种相关算法进行对比实验。实验结果表明，与目前FCMPGA、IPGA、IWO等算法相比，求解精度提高了5%~40%，求解效率上对比其他算法提升1~5倍，尤其在K值较大时表现更优。

关键词：多旅行商问题;旅行商问题;k均值聚类;模拟退火算法

基金资助：国家自然科学基金项目（62062002，62102201）；宁夏自然基金（2022AAC03289，2022AAC03245，2021AAC03034）北方民族大学中央高校基本科研业务费专项资金（FWNX09）；北方民族大学校级一般项目（2021XYZJK01）