求解MMTSP的模糊聚类单亲遗传算法

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

随着现代物流行业等应用领域的快速发展,多旅行商问题得到了越来越多的关注。针对多起点闭回路多旅行商问题(Multiple depots Multiple Traveling Salesman Problem,MMTSP),文中提出了一种模糊C均值聚类单亲遗传算法。该算法首先采用模糊C均值聚类方法将所有城市按照隶属度分成若干类,然后对应每个类建立一个旅行商问题,并通过一种改进的单亲遗传算法对旅行商问题进行求解,最后将各个类的结果综合作为MMTSP的解。所提算法采用先聚类再执行遗传操作的求解策略不仅可极大地缩减算法的搜索空间,而且可使种群在缩减后的搜索空间得到更充分的探索,从而更快地得到问题的最优解。对TSPLIB数据库中若干测试实例的求解实验结果表明,与其他几种相关算法相比,FCMPGA在不同规模问题上均具有良好的求解性能,尤其是在求解大规模问题时算法性能表现更优,且收敛速度更快。

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.