计算机科学 ›› 2020, Vol. 47 ›› Issue (6): 219-224.doi: 10.11896/jsjkx.190500137
胡士娟1, 鲁海燕1,2, 向蕾1, 沈莞蔷1,2
HU Shi-juan1, LU Hai-yan1,2, XIANG Lei1, SHEN Wan-qiang1,2
摘要： 随着现代物流行业等应用领域的快速发展,多旅行商问题得到了越来越多的关注。针对多起点闭回路多旅行商问题(Multiple depots Multiple Traveling Salesman Problem,MMTSP),文中提出了一种模糊C均值聚类单亲遗传算法。该算法首先采用模糊C均值聚类方法将所有城市按照隶属度分成若干类,然后对应每个类建立一个旅行商问题,并通过一种改进的单亲遗传算法对旅行商问题进行求解,最后将各个类的结果综合作为MMTSP的解。所提算法采用先聚类再执行遗传操作的求解策略不仅可极大地缩减算法的搜索空间,而且可使种群在缩减后的搜索空间得到更充分的探索,从而更快地得到问题的最优解。对TSPLIB数据库中若干测试实例的求解实验结果表明,与其他几种相关算法相比,FCMPGA在不同规模问题上均具有良好的求解性能,尤其是在求解大规模问题时算法性能表现更优,且收敛速度更快。
中图分类号:
| [1]BEKTAS T.The multiple traveling salesman problem:an overview of formulations and solution procedures[J].Omega:International Journal of Management Science,2006,34(3):209-219. [2]LIU M,ZHANG P Y.New hybrid genetic algorithm for solving the multiple traveling salesman problem:an example of distribution of emergence materials[J].Journal of Systems & Management,2014,23(2):247-254. [3]ANN S,KIM Y,AHN J.Area allocation algorithm for multiple UAVs area coverage based on clustering and graph method[J].Ifac Papers-online,2015,48(9):204-209. [4]NIU Y C.Research of intelligent tourism route planning based on ant colony algorithm[D].Nanjing:Nanjing University of Posts and Telecommunications,2017. [5]WANG J W,DAI G M,XIE B Q,et al.A survey of solving the traveling salesman problem[J].Computer Engineering & Science,2008,30(2):72-74. [6]WANG Y Z,CHEN Y,YU Y Y.Improved grouping genetic algorithm for solving multiple traveling salesman problem[J].Journal of Electronics & Information Technology,2017,39(1):198-205. [7]BENAVENT,ENRIQUE,MARTINEZ,et al.Multi-depot multiple TSP:a polyhedral study and computational results[J].Annals of Operations Research,2013,207(1):7-25. [8]FANG H Y,YANG T H,ZONG F X,et al.Path optimization of multi-UAV cooperative reconnaissance based on MMTSP algorithm[J].Journal of Logistical Engineering University,2017,33(3):85-90. [9]HOU M S,LIU D B.A novel method for solving the multiple traveling salesmen problem with multiple depots[J].Chinese Science Bulletin,2012,57(15):1886-1892. [10]RAMADHANI T,HERTONO G F,HANDARI B D.An ant colony optimization algorithm for solving the fixed destination multi-depot Multiple Traveling Salesman Problem with Non-random Parameters[C]//American Institute of Physics Confe-rence Series.AIP Publishing LLC,2017,1862(1):030123. [11]KOUBAA A,CHEIKHROUHOU O,BENNACEUR H,et al.Move and improve:a market-based mechanism for the multiple depot multiple travelling salesmen problem[J].Journal of Intelligent & Robotic Systems,2017,85(2):307-330. [12]ZHOU H,SONG M,PEDRYCZ W.A comparative study of improved GA and PSO in solving multiple traveling salesmenpro-blem[J].Applied Soft Computing,2018,64:564-580. [13]QIAN W W,CHAI J R.Clustering genetic algorithm based on complex method[J].Computer Engineering and Applications,2017,53(3):87-94. [14]DE M,DAS B,MAITI M.Green logistics under imperfect production system:a rough age based multi-objective genetic algorithm approach[J].Computers & Industrial Engineering,2018 (119):100-113. [15]ENDER S,AHMET C.An evolutionary genetic algorithm foroptimization of distributed database queries[J].The Computer Journal,2018,54(5):717-725. [16]LI L,LUO H Q,DING Y L.A novel FCM clustering algorithm[J].Computer Technology and Development,2009,19(12):71-73. [17]ZHAO X C,GUO S.Analysis on the relative solution space for MTSP with genetic algorithm[J].CAAI Transactions on Intelligent Systems,2018,13(5):760-768. [18]HE D K,WANG F L,JIA M X.Uniform design of initial population and operational parameters of genetic algorithm[J].Journal of Northeastern University(Natural Science),2005,26(9):828-831. |
| [1] | 王永, 崔源. 基于四边形最优圈内最短路径的旅行商问题割边方法 Cutting Edge Method for Traveling Salesman Problem Based on the Shortest Paths in Optimal Cycles of Quadrilaterals 计算机科学, 2022, 49(6A): 199-205. https://doi.org/10.11896/jsjkx.210400065 |
| [2] | 杨德成, 李凤岐, 王祎, 王胜法, 殷慧殊. 智能3D打印路径规划算法 Intelligent 3D Printing Path Planning Algorithm 计算机科学, 2020, 47(8): 267-271. https://doi.org/10.11896/jsjkx.190700184 |
| [3] | 冯炳超, 吴璟莉. 求解自行车共享系统静态再平衡问题的单亲遗传算法 Partheno-genetic Algorithm for Solving Static Rebalance Problem of Bicycle Sharing System 计算机科学, 2020, 47(6A): 114-118. https://doi.org/10.11896/JsJkx.190700120 |
| [4] | 廖义辉, 杨恩君, 刘安东, 俞立. 基于改进变邻域搜索的数控裁床路径优化 Path Optimization in CNC Cutting Machine Based on Modified Variable Neighborhood Search 计算机科学, 2020, 47(10): 233-239. https://doi.org/10.11896/jsjkx.190800035 |
| [5] | 蔡延光, 陈厚仁, 戚远航. 混沌烟花算法求解旅行商问题 Chaotic Fireworks Algorithm for Solving Travelling Salesman Problem 计算机科学, 2019, 46(6A): 85-88. |
| [6] | 贾娟娟, 贾富杰. 结合爬山法的模糊C均值彩色图像分割方法 Fuzzy C-means Color Image Segmentation Algorithm Combining Hill-climbing Algorithm 计算机科学, 2018, 45(11A): 247-250. |
| [7] | 陈建荣,陈建华. 求解TSP问题的离散捕鱼策略优化算法 Discrete Fishing Strategy Optimization Algorithm for TSP 计算机科学, 2017, 44(Z6): 139-140. https://doi.org/10.11896/j.issn.1002-137X.2017.6A.032 |
| [8] | 朱春,李林国,郭剑. 基于改进布谷鸟优化的模糊聚类图像分割 Fuzzy Clustering Image Segmentation Algorithm Based on Improved Cuckoo Search 计算机科学, 2017, 44(6): 278-282. https://doi.org/10.11896/j.issn.1002-137X.2017.06.049 |
| [9] | 耿艳萍,郭小英,王华夏,陈磊,李雪梅. 基于小波图像融合算法和改进FCM聚类的MR脑部图像分割算法 MR Brain Image Segmentation Method Based on Wavelet Transform Image Fusion Algorithm and Improved FCM Clustering 计算机科学, 2017, 44(12): 260-265. https://doi.org/10.11896/j.issn.1002-137X.2017.12.047 |
| [10] | 吴杰,朱家明,陈静. 基于模糊聚类水平集的医学图像分割方法 Fuzzy Clustering Level Set Based Medical Image Segmentation Method 计算机科学, 2015, 42(Z11): 155-159. |
| [11] | 高峰,郑波. 基于IPSO算法的TSP问题求解研究 Study on TSP Solving Based on IPSO 计算机科学, 2014, 41(Z11): 69-71. |
| [12] | 文传军,汪庆淼,詹永照. 均衡模糊C均值聚类算法 Equalization Fuzzy C-means Clustering Algorithm 计算机科学, 2014, 41(8): 250-253. https://doi.org/10.11896/j.issn.1002-137X.2014.08.053 |
| [13] | 王诏远,李天瑞,易修文. 基于MapReduce的蚁群优化算法实现方法 Approach for Development of Ant Colony Optimization Based on MapReduce 计算机科学, 2014, 41(7): 261-265. https://doi.org/10.11896/j.issn.1002-137X.2014.07.054 |
| [14] | 柯良军，尚可，冯祖仁. 不确定旅行商问题的鲁棒模型及其算法研究 Robust Model and Algorithms for the Uncertain Traveling Salesman Problem 计算机科学, 2012, 39(Z6): 238-241. |
| [15] | 郝承伟,高慧敏. 求解TSP问题的一种改进的+进制MIMIC算法 Modified Decimal MIMIC Algorithm for TSP 计算机科学, 2012, 39(8): 233-236. |
|
||
首页