Solving The Min-max Clustered Traveling Salesmen Problem Based On Genetic Algorithm

The traveling salesman problem is a classic combinatorial optimization problem in computer science and operations research,and the multiple traveling salesman problem and clustered traveling salesman problem are two widely concerned generalized variants of it.These two problems have a wide range of applications in real life,such as vehicle path planning,manufacturing process optimization,computer operations,printing press scheduling,school bus scheduling,and so on.Therefore,it is of great theoretical significance and practical value to conduct scientific research on these two problems and their generalization deformations.This paper studies the min-max clustered traveling salesman problem,which is a generalized deformation of the multiple traveling salesman problem and the clustered traveling salesman problem.It can be described as follows:given several cities,they are distributed in a network.All cities are divided into several subsets,and each subset is called a cluster.Given a number of traveling salesmen,they need to visit all cities.The requirement of the problem is to design a tour for each traveling salesman so that all cities can be visited and the cities in each cluster are visited consecutively.The goal of the problem is to minimize the weight of the maximum weight tour.In this paper,we investigate the single-depot and multi-depot min-max clustered traveling salesman problem from the perspective of genetic algorithms,and the main results are as follows:The first problem considered in this paper is the single-depot min-max clustered traveling salesman problem.Given a complete undirected graph G=（V,E）,V={1,2,,n}is vertex set,were 1 is the common starting vertex of all traveling salesmen,and each vertex in{2,,n}corresponds to a city.The vertex set V is partitioned into l clusters V₁,V ₂,,V_l,and ₁V={1}.Each edge（i,j）in set E is associated with a non-negative real number d_ij,representing the distance between city i and city j.Given a set E’（?）E,define the weight of E’as the sum of the lengths of all edges in E’.Given m salesmen,the single-depot MMCTSP requires computing a tour for each salesman so that all cities are visited and the cities within each cluster are visited consecutively.The objective of the problem is to minimize the weight of the maximum weight tour.Aiming at this problem,a two-stage solution method based on genetic algorithm is designed.Specifically,in the first stage,a TSP is abstracted for each cluster,and then a genetic algorithm for TSP is applied to determine the visit order of vertices within the cluster.In the second stage,firstly,each cluster is considered as a node,and the distance between every two nodes is defined by combining the results of the first stage and with a combination of greed and random,and an MTSP is then constructed.Finally,a grouping-based genetic algorithm for the MTSP is applied to determine the assignment of clusters and visiting order of the assigned clusters for each salesman.The experiment results indicate that in small-scale instances,compared with the exact results obtained by Cplex software,the best results obtained by proposed algorithm has a relative error of no more than 1.5%,but the solving time is significantly reduced;in medium-scale and large-scale instances,our algorithm shows good solution performance compared with the two related two-stage strategies in the literature.The second problem considered in this paper is the multi-depot MTSP.Compared with the first problem,the number of depots is increased from 1 to m in this problem,that is,each traveling salesman corresponds to a depot.The requirement of the problem is to design a tour for each traveling salesman starting from its depot and finally returning to this depot,so that all cities can be visited and the cities in each cluster are visited consecutively.The goal of the problem is still to minimize the weight of the maximum weight tour.Aiming at this problem,a two-stage solution method based on genetic algorithm is also designed.Compared with the first problem,in the second stage of this solution method,each cluster is also regarded as a node,and then an MTSP is abstracted.However,when solving the MTSP,since each traveling salesman corresponds to a depot,the same subset is clustered,and the feasible solutions corresponding to different orders are also different.Therefore,at this stage,the genetic algorithm based on disordered grouping is used to solve it.Experiment results show that in small-scale instances,compared with the results obtained by Cplex software within a limited time,the algorithm in this paper reduces the solution time significantly and at the same time has higher solution accuracy;in medium-scale and large-scale instances,compared with the two related two-stage strategies in the literature,the algorithm in this paper also shows good solution performance.