Research On Vehicle Routing Problem Based On Improved Genetic Algorithm

Vehicle routing is crucial for the continuous development of the logistics industry.With the emphasis on high-quality development,there is an increasing need to reduce the social logistics total cost.Vehicle routing problem has become a hot issue in logistics research.This study focuses on the Traveling Salesman Problem(TSP)and Capacitated Vehicle Routing Problem(CVRP),and designs and improves the genetic algorithm to solve the problem.(1)This paper provides an overview of the vehicle routing problem,related heuristic algorithms,and the classification of the problem’s elements.Based on this,the correlation between TSP and CVRP is clarified,and the corresponding solution method is proposed.(2)An improved genetic algorithm based on greedy strategy is proposed to solve TSP.The heuristic crossover operator uses a greedy strategy to enhance the algorithm’s global search ability,while three shift and mutation operators are used to maintain population diversity.The example test in TSPLIB demonstrates that the algorithm can maintain population diversity well during iteration and has high solving accuracy and fast convergence speed.It outperforms the generalized chromosome genetic algorithm,improved empire competition algorithm and brainstorming algorithm in examples with less than 600 nodes.(3)To solve the CVRP,an adaptive improved genetic algorithm is proposed.In the crossover phase,the adaptive coefficient is introduced.The heuristic crossover operator based on greedy strategy and partially matched crossover operator are combined to prevent premature convergence.In the selection stage,the combination of roulette and elite selection method is adopted to improve the quality of the next generation individuals.Three local optimization operators are used to optimize path and inter-path respectively.(4)The influence of different cross probabilities and mutation probabilities on algorithm optimization is tested for CVRP’s standard example.The probability combination of 0.8 and 0.1 is finally determined as the most suitable.The optimization effect of the crossover operators under different adaptive coefficients is discussed,and it is found that the optimization effect is best when the adaptive parameter is 0.84.The improved genetic algorithm significantly improves the solving accuracy and reduces solving time by about 90%,compared with the basic genetic algorithm.Compared with other algorithms,the improved genetic algorithm has better performance in solving accuracy and stability,and also under large-scale examples.