Solution Space Analysis Of Mtsp And Application In VRP Optimization

Our society is colorful and all-inclusive.We live in the era of big data.Vehicle transportation connects all aspects of our lives.Vehicle routing problem is a combinatorial optimization problem which is widely used in logistics transportation and resource allocation.It is a further extension of traveling salesman problem.The main research problem is how to optimize the vehicle routing and how to allocate vehicles reasonably.With the development of various complex optimization problems in industrial design and scientific research,there are many difficulties in solving complex optimization problems by using traditional optimization algorithms.In this context,the emergence of swarm intelligence optimization algorithm provides a new way to solve complex optimization problems.Among many swarm intelligence algorithms,genetic algorithm has been widely used in engineering optimization,system identification,automatic control and other fields because of its strong global search function,high robustness,strong adaptability,simple calculation process and easy integration with other algorithms.It is a more effective global method to solve NP-hard problems.The purpose of this paper is to analyze and verify the crucial role of the design of chromosome coding schemes in solving the multi-traveling salesman problem by genetic algorithm from both theoretical and experimental perspectives.Based on the concept of relative solution space,the relationship between the solution space corresponding to the three chromosome coding schemes in the limit sense is first analyzed,and then the relationship between the number of traveling salesmen and the number of cities in different situations is analyzed.Approximate Relative Size Relation in Solution Space.This paper provides scientific guidance for solving engineering problems based on the theoretical results of quantitative analysis of search space.Therefore,it is applied to the current popular vehicle routing optimization problem,and a genetic algorithm based on two-segment coding scheme is creatively proposed.At the same time,this paper focuses on the influence of chromosome encoding on the size of solution space in genetic algorithm,and the guidance of this influence on searching for the optimal position of population.A genetic algorithm based on two-segment encoding is proposed.The construction process of initial solution is improved by using the method of routing first and clustering later.The C-W-saving algorithm is used to optimize the route of vehicle,the selection strategy in selection operation,the selection method of solution,and the insertion operator is adjusted to perform specific crossover and mutation operation on the selected parent chromosome.Finally,the convergence speed of the algorithm is simulated and tested on small data sets,and the effectiveness of the algorithm is demonstrated by comparing with the original algorithm on large data sets.