K-means聚类蚁群优化算法求解大型TSP问题

详细信息    查看全文 | 推荐本文 |

英文篇名：K-means Clustering ant Colony Algorithm for Large-scale TSP Problems 作者：郑旭峰 ; 周健勇 英文作者：ZHENG Xufeng;ZHOU Jianyong;Management School, University of Shanghai for Science and Technology; 关键词：聚类 ; 蚁群算法 ; 旅行商问题 ; 物流配送 英文关键词：clustering;;ant colony algorithm;;traveling salesman problem;;logistics distribution 中文刊名：LTKJ 英文刊名：Logistics Sci-Tech 机构：上海理工大学管理学院; 出版日期：2018-02-10 出版单位：物流科技 年：2018 期：v.41;No.270 语种：中文; 页：LTKJ201802013 页数：4 CN：02 ISSN：10-1373/F 分类号：43-46

摘要

对于大型TSP问题,传统蚁群算法出现收敛速度慢,求解时间长,精度低等问题。针对物流配送过程中目的地聚集化现象,提出一种解决带有聚类特性TSP问题的K-means聚类蚁群算法。该算法首先对大规模的TSP问题进行K-means算法聚类,分解成小规模的子问题,小规模的TSP问题可通过传统蚁群算法求解,最后将每个聚类连接起来,完成对整个大规模问题的求解。仿真实验比较了传统蚁群算法,蚁群聚类蚁群算法以及K-means聚类蚁群算法,结果表明K-means聚类蚁群算法不仅求解速度得到极大提升,最短路径误差率也有一定下降,具有较好的效果。
        For large-scale traveling salesman problem(TSP), ant colony algorithm(ACA) has the weakness of slow convergence rate, long computing time as well as declining accuracy. According to destination gathering phenomenon in logistics distribution,K-means ant colony algorithm is proposed to tackle large-scale TSP with characteristic of clustering. First the TSP problem was divided into several sub-problems by clustering using K-means algorithm that can be solved in parallelization by traditional ACA algorithm. At last access city of each sub-problem was connected with each other to make the oversized TSP problem be completed. The traditional ACA, Ant clustering Ant colony algorithm(ACACA) and the proposed K-means clustering Ant colony algorithm(KMACA) were compared in the simulated experiment. The result shows the KMACA method not only has the advantage of shorter computing time, but also a lower error rate with a better effect.

引文

[1]Tzle T,Dorigo M.ACO algorithms for the quadratic assignment problem[M].Mc Graw-Hill Ltd.UK,1999.
    [2]张军英,敖磊,贾江涛.求解TSP问题的改进蚁群算法[J].西安电子科技大学学报,2005,32(5):681-685.
    [3]戚玉涛,刘芳,焦李成.求解大规模TSP问题的自适应归约免疫算法[J].软件学报,2008,19(6):1265-1273.
    [4]张维泽,林剑波,吴洪森.基于改进蚁群算法的物流配送路径优化[J].浙江大学学报(工学版),2008,42(4):574-578.
    [5]袁亚博,刘羿,吴斌.改进蚁群算法求解最短路径问题[J].计算机工程与应用,2016,52(6):8-12.
    [6]张立毅,王迎,费腾.混沌扰动模拟退火蚁群算法低碳物流路径优化[J].计算机工程与应用,2017,53(1):63-68.
    [7]孙士保,秦克云.改进的k-平均聚类算法研究[J].计算机工程,2007,33(13):200-201.
    [8]孙吉贵,刘杰,赵连宇.聚类算法研究[J].软件学报,2008(1):48-61.
    [9]朱连江,马炳先,赵学泉.基于轮廓系数的聚类有效性分析[J].计算机应用,2010(s2):139-141.
    [10]柳长源,毕晓君,韦琦.基于蚁群算法求解TSP问题的参数优化与仿真[J].信息技术,2009(4):129-131.