A Parallel Hybrid Metaheuristic Algorithm For Minimum Latency Problem

The Minimum Latency Problem(MLP)is a variant of the Traveling Salesman Problem(TSP),which aims to solve the cumulative waiting time of all customers in the route.Compared with the TSP,the MLP is more difficult to solve.The current solution methods can only have higher performance when the number of customers is small.When the number of customers is large,it is difficult for the algorithm to balance the running time and the solution quality.Based on the above problems,this paper studies how to obtain a high-quality solution to the problem of MLP with large data volume in a short time.At present,Metaheuristic Algorithm is mainly used to solve the MLP with large amount of data.Based on this,a hybrid Metaheuristic Algorithm is proposed.Genetic Algorithm(GA)and Variable Neighborhood Search(VNS)are combined in fine granularity to realize variable neighborhood search within the framework of GA.When the algorithm falls into a local optimal solution,the neighborhood structure of the offspring chromosomes can be changed during the crossover process of the GA,and the mutation process of the GA can be improved,so that the offspring chromosomes can be optimized with a greater probability while increasing diversity.Data preprocessing is also carried out on the algorithm,and the time complexity of generating offspring chromosomes is reduced by constructing gene node index list for each chromosome.In order to speed up the operation of the algorithm further,GPU is used to realize the parallelization of the algorithm,and the parallelization algorithm is improved according to the operation characteristics of GPU.The crossover and mutation processes of parallel algorithms are run separately and synchronously in units of thread block,and each thread has a fixed chromosome selection position and generation position.On the whole,the algorithm runs in parallel with thread blocks as a unit,so as to ensure that the parallel algorithm avoids the problem of thread divergence and reduces the thread communication overhead,and at the same time realizes the dynamic selection of chromosomes.In addition,the algorithm is combined with the perturbation mechanism to enhance the global search capability of the parallel algorithm,and the final solution is generated by multiple improvements.The performance of the algorithm is further improved by the above methods.In order to verify the performance of the algorithm,comparative experiments are carried out on the algorithm.The number of nodes for test data varies from 51 to 10150.The experimental results show that compared with other Metaheuristic Algorithms,the proposed algorithm can obtain high-quality solutions in a short time in CPU environment.In CPU-GPU environment,when the data scale is large,obvious acceleration effect can be obtained.The larger the data scale,the more obvious the acceleration effect is.Compared with other parallel algorithms in the experiment,this parallel algorithm has better performance.Therefore,the parallel hybrid metaheuristic algorithm can obtain high-quality solutions in a relatively short time for the MLP with large amount of data.