一种基于K-means聚类算法和CNGA算法的用于求解MTSP问题的启发式算法  

A Heuristic Algorithm for Solving MTSP Problems is Developed Based on the K-means Clustering Algorithm and the CNGA Algorithm

作　　者：陈果 吕广强 石鑫 谢延景 董芳艳 陈科伟 CHEN Guo;LV Guangqiang;SHI Xin;XIE Yanjing;DONG Fangyan;CHEN Kewei(School of Mechanical Engineering and Mechanics,Ningbo University,Ningbo Zhejiang 315211,China;Ningbo Institute of Technology Special Robot and High end Equipment Intelligent Interaction Design and Manufacturing Research Institute,Zhejiang University,Ningbo Zhejiang 315100,China;Ningbo Guangqiang Robot Technology Co.,Ltd.,Ningbo Zhejiang 315000,China)

机构地区：[1]宁波大学机械工程与力学学院,江浙宁波315211 [2]浙大宁波理工学院特种机器人与高端装备智能交互设计制造研究院,浙江宁波315100 [3]宁波广强机器人科技有限公司,浙江宁波315000

出　　处：《佳木斯大学学报(自然科学版)》2024年第12期140-142,共3页Journal of Jiamusi University:Natural Science Edition

基　　金：宁波市国际合作项目(2023H007);宁波市“揭榜挂帅”暨“科技创新2025”重大专项(2023Z180)。

摘　　要：针对MinMaxMTSP问题,对所有旅行商所走的环路,寻求最大长度最小化,旨在最小化所有旅行推销员行程中最长行程的长度,本研究提出了一种名为KCNGA的启发式算法,将聚类算法和遗传算法相结合,通过启发式算法的初步计算生成优秀的基因片段,可以有效提高后续计算的收敛速度。通过对城市进行分组以减小问题的规模,提高了计算效率,简化了问题的复杂性。同时,通过对每个子集应用启发式算法来提高理解质量。本算法对MinMaxMTSP问题解决具有较强的针对性,本研究中通过对tsplib数据集中的部分数据集使用KCNGA算法与GA算法进行不同旅行商数的分组实验,证明了KCNGA算法在MinMAxMTSP问题的解决中具有准确性和快速收敛性。This article focuses on the MinMaxMTSP problem and seeks to minimize the maximum length of the loops traveled by all travel agents,aiming to minimize the length of the longest journey among all travel salesman journeys.This article proposes a heuristic algorithm called KCNGA,which combines clustering algorithm and genetic algorithm to generate excellent gene fragments through preliminary calculations of heuristic algorithm,which can effectively improve the convergence speed of subsequent calculations.By grouping cities to reduce the size of the problem,computational efficiency has been improved and the complexity of the problem has been simplified.Meanwhile,by applying heuristic algorithms to each subset,the quality of understanding can be improved.This algorithm has strong specificity for solving MinMaxMTSP problems.In this paper,we conducted grouping experiments using KCNGA algorithm and GA algorithm with different travel quotients on some datasets in the tsplib dataset,and proved that KCNGA algorithm has accuracy and fast convergence in solving MinMaxMTSP problems.

关 键 词：MTSP问题 Kmeans算法 GA 近旁测度 

分 类 号：N32[自然科学总论]