Computer Science ›› 2020, Vol. 47 ›› Issue (6): 219-224.doi: 10.11896/jsjkx.190500137

• Artificial Intelligence • Previous Articles     Next Articles

Fuzzy C-means Clustering Based Partheno-genetic Algorithm for Solving MMTSP

HU Shi-juan1, LU Hai-yan1,2, XIANG Lei1, SHEN Wan-qiang1,2   

  1. 1 School of Science,Jiangnan University,Wuxi,Jiangsu 214122,China
    2 Wuxi Engineering Technology Research Center for Biological Computing,Wuxi,Jiangsu 214122,China
  • Received:2019-05-23 Online:2020-06-15 Published:2020-06-10
  • About author:HU Shi-juan,born in 1994,graduate student,is a member of China ComputerFederation.Her research direction is optimization and control.
    LU Hai-yan,born in 1970,Ph.D,asso-ciate professor.Her research direction is intelligence algorithms and combinatorialoptimization.
  • Supported by:
    This work was supported by the National Natural Science Foundation of China(61772013,61402201) and Fundamental Research Funds for the Central Universities of Ministry of Education of China (114205020513526)

Abstract: Due to the rapid development of application fields such as modern logistics industry,the multiple traveling salesman problem has attracted more and more attention.Thus,for the multiple traveling salesman problem with multiple depots and closed paths(MMTSP),this paper proposes a fuzzy C-means clustering based partheno-genetic algorithm (FCMPGA).The algorithm firstly uses the fuzzy C-means clustering method to classify all cities into several classes according to their subordinative degrees,and then establishes a corresponding traveling salesman problem for each class and solve it using an improved partheno-genetic algorithm.Finally,the results for each class are combined together to form a solution of the MMTSP.The solution strategy adopted in the proposed algorithm,which performs clustering prior to genetic operations,can not only greatly reduce the search space of the algorithm,but also make the reduced search space be explored more adequately and thereby obtain optimal solutions of the problems more quickly.Compared with several other related algorithms,the experimental results of a number of test instances in the TSPLIB database show that FCMPGA exhibits overall good performance on all test instances of different sizes,and especially on large-scale problems,the performance of the algorithm is better and its convergence speed is faster.

Key words: Fuzzy C-means clustering, Multiple traveling salesman problem, Partheno-genetic algorithm, Traveling salesman pro-blem

CLC Number: 

  • TP301.6
[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] MAO Sen-lin, XIA Zhen, GENG Xin-yu, CHEN Jian-hui, JIANG Hong-xia. FCM Algorithm Based on Density Sensitive Distance and Fuzzy Partition [J]. Computer Science, 2022, 49(6A): 285-290.
[2] FENG Bing-chao and WU Jing-li. Partheno-genetic Algorithm for Solving Static Rebalance Problem of Bicycle Sharing System [J]. Computer Science, 2020, 47(6A): 114-118.
[3] JIA Juan-juan, JIA Fu-jie. Fuzzy C-means Color Image Segmentation Algorithm Combining Hill-climbing Algorithm [J]. Computer Science, 2018, 45(11A): 247-250.
[4] ZHU Chun, LI Lin-guo and GUO Jian. Fuzzy Clustering Image Segmentation Algorithm Based on Improved Cuckoo Search [J]. Computer Science, 2017, 44(6): 278-282.
[5] GENG Yan-ping, GUO Xiao-ying, WANG Hua-xia, CHEN Lei and LI Xue-mei. MR Brain Image Segmentation Method Based on Wavelet Transform Image Fusion Algorithm and Improved FCM Clustering [J]. Computer Science, 2017, 44(12): 260-265.
[6] HOU Xiao-fan and WU Cheng-mao. Fast Fuzzy Local Information C-means Clustering Segmentation Algorithm [J]. Computer Science, 2016, 43(10): 297-303.
[7] LIU Meng-jiao and WU Cheng-mao. Research on Improved Local Fuzzy C-means Clustering Segmentation Algorithm [J]. Computer Science, 2015, 42(Z6): 190-194.
[8] WU Jie, ZHU Jia-ming and CHEN Jing. Fuzzy Clustering Level Set Based Medical Image Segmentation Method [J]. Computer Science, 2015, 42(Z11): 155-159.
[9] WEN Chuan-jun,WANG Qing-miao and ZHAN Yong-zhao. Equalization Fuzzy C-means Clustering Algorithm [J]. Computer Science, 2014, 41(8): 250-253.
[10] . Improved Possibilistic C-means Clustering Algorithm Based on Particle Swarm Optimization [J]. Computer Science, 2012, 39(11): 122-126.
[11] YANG Hong-ying,WANG Xiang-yang,WANG Chun-hua. Improved Adaptive FCM Color Image Segmentation Algorithm [J]. Computer Science, 2009, 36(8): 281-284.
[12] . [J]. Computer Science, 2008, 35(8): 134-137.
[13] HAN Bing ,GAO Xin-Bo, JI Hong-Bing (School of Electronic Engineering , Xidian Univ, , Xi'an 710071). [J]. Computer Science, 2006, 33(6): 225-231.
[14] LIU Si Yuan, LI Xiao-Feng ,LI Zai-Ming (School of Communication and Information Engineering,UESTC,Chengdu 610054). [J]. Computer Science, 2006, 33(4): 225-227.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!