Shuffled Frog Leaping Algorithm And Its Applications On The Capacitated Vehicle Routing Problem

Logistics can ensure the business of goods,so it is the artery of commodity economy.As an optimization problem in logistics activities,the vehicle routing problem has significant research value.As a new kind of optimization algorithm,swarm intelligence optimization algorithm has better performance,but its performance is facing challenge from the problem of increasing complexity.Based on the above background,this paper studies the shuffled frog leaping algorithm and its application on the capacitated vehicle routing problem,and the main work are as follows:First,this paper analyzes the structural defects of the shuffled frog leaping algorithm,and then a new shuffled frog leaping algorithm based on reverse leaping in solution space and information interaction enhancement for solving the numerical optimization problem is proposed.The information exchange between sub-inferior solutions and sub-optimal solutions is added to enhance the utilization of information within sub-groups.In order to reduce the probability of inferior solutions and to enhance the spatial development ability,the idea of reverse leaping is introduced to improve the local update mechanism.In addition,the crossover of local optimal solutions is mutated to ensure the population diversity.And,the local optimal solution method is adopted to deepen the depth of interaction among subpopulations,and reverse leaping mechanism to prevent population assimilation.The simulation experiments are carried out with a test sets includes 23 different types of test functions.The experimental results show that the proposed strategy can improve the performance of the algorithm,and the proposed algorithm performance is better than that of those four kinds of comparative algorithm,showing a better solving accuracy and stability.Second,according to the characteristics of the traveling salesman problem,this paper proposes a shuffled leapfrog algorithm based on heuristic information for solving the traveling salesman problem.In this algorithm,an individual generating operator based on heuristic information is designed,which can extract effective information from the superior solution and the inferior solution at the same time.The opposite roulette selection is adopted to increase the population diversity.The algorithm framework based on the independent optimal subgroups is designed to strengthen the ability of algorithm development and balance the search ability of each subgroup.Then the mutation and optimization of the local optimal solution help to jump out of the local optimum,and the convergence accuracy and speed is improved by local search enhancement.The simulation experiments are carried out with 31 standard test instances to verify the validity of the individual generation operator and the improved strategy,and the proposed algorithm performance.The experimental results show that the individual generation operator and the improved strategy are effective.Then,compared with the eight comparison algorithms,the proposed algorithm has better accuracy and stability in solving the traveling salesman problem.Third,the similarities and differences between the capacitated vehicle routing problem and the traveling salesman problem are analyzed in this paper.Based on the above novel shuffled frog leaping algorithm based on heuristic information,the individual decoding method is modified to transform the constraint conditions from the vehicle capacity to the number of used vehicles.A penalty function is designed which is positively related to the degree of breaking the constraint,and the infeasible solution is eliminated in the iteration process.The original local search enhancement strategy is deleted,and the path of each vehicle is optimized separately in the individual decoding phase.In this paper,45 instances with different scales are used as test sets.By comparing with four representative algorithms recently,the experimental results show that the proposed algorithm has higher accuracy in solving the capacitated vehicle routing problem.