K-DSA for the multiple traveling salesman problem

Aimed at a multiple traveling salesman problem(MTSP)with multiple depots and closed paths,this paper proposes a k-means clustering donkey and a smuggler algorithm(KDSA).The algorithm first uses the k-means clustering method to divide all cities into several categories based on the center of various samples;the large-scale MTSP is divided into multiple separate traveling salesman problems(TSPs),and the TSP is solved through the DSA.The proposed algorithm adopts a solution strategy of clustering first and then carrying out,which can not only greatly reduce the search space of the algorithm but also make the search space more fully explored so that the optimal solution of the problem can be more quickly obtained.The experimental results from solving several test cases in the TSPLIB database show that compared with other related intelligent algorithms,the K-DSA has good solving performance and computational efficiency in MTSPs of different scales,especially with large-scale MTSP and when the convergence speed is faster;thus,the advantages of this algorithm are more obvious compared to other algorithms.

An evolutionary algorithm approach for the constrained multi-depot vehicle routing problem

Purpose-The purpose of this paper is to explore a real world vehicle routing problem(VRP)that has multi-depot subcontractors with a heterogeneous fleet of vehicles that are available to pickup/deliver jobs with varying time windows and locations.Both the overall job completion time and number of drivers utilized are analyzed for the automated job allocations and manual job assignments from transportation field experts.Design/methodology/approach-A nested genetic algorithm(GA)is used to automate the job allocation process and minimize the overall time to deliver all jobs,while utilizing the fewest number of drivers-as a secondary objective.Findings-Three different real world data sets were used to compare the results of the GA vs transportation field experts’manual assignments.The job assignments from the GA improved the overall job completion time in 100 percent(30/30)of the cases and maintained the same or fewer drivers as BS Logistics(BSL)in 47 percent(14/30)of the cases.Originality/value-This paperprovidesa novel approach to solving a real world VRPthathasmultiple variants.While there have been numerous models to capture a select number of these variants,the value of this nested GA lies in its ability to incorporate multiple depots,a heterogeneous fleet of vehicles as well as varying pickup times,pickup locations,delivery times and delivery locations for each job into a single model.Existing research does not provide models to collectively address all of these variants.