摘要
对于大型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 convergencerate, 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 wasdivided into several sub-problems by clustering using K-means algorithm that can be solved in parallelization by traditional ACAalgorithm. At last access city of each sub-problem was connected with each other to make the oversized TSP problem be com-pleted. The traditional ACA, Ant clustering Ant colony algorithm （ACACA） and the proposed K-means clustering Ant colony al-gorithm （KMACA ） were compared in the simulated experiment. The result shows the KMACA method not only has the advantageof shorter computing time, but also a lower error rate with a better effect.
出处
《物流科技》
2018年第2期37-40,共4页
Logistics Sci-Tech
关键词
聚类
蚁群算法
旅行商问题
物流配送
clustering
ant colony algorithm
traveling salesman problem
logistics distribution
