Dynamic Path Optimization Based On The Genetic Algorithm

With the acceleration of the world economy, social progress, and the process of urbanization, the number of urban motor vehicle rapidly grow, and heavy traffic and even blocking phenomenon occurs frequently. It has become a negative factor affecting social development that traffic environment is deteriorating. Therefore, it has become an urgent need of solving the traffic problems in major cities how to improve the utilization of city roads, and to reduce vehicle’s travel time and the incidence and the negative impact of traffic congestion.Dynamic path optimization is the best way to solve the above traffic problems. It is based on mathematical modeling of the urban road. Its core is the dynamic path optimization algorithm, and its aim is to guide the vehicle to drive following the optimized route on the intelligent termina, enhance the utilization of city roads, reduce vehicle’s travel time, and to ease the traffic congestion.In designing the proposed algorithm, the foundation, core and purpose of the dynamic path optimization is considered. And the purpose of dynamic path optimization is throughout the entire process of modeling and designing algorithms. This paper mainly includes the following three parts:a dynamic model of the road network, an improved genetic algorithm based on dynamic network model, the convergence analysis of the improved GA and some simulation examples.Part Ⅰ:Dynamic model of the road network is the basis of route optimization and the entire optimization process. This paper designs two fuzzy controllers with two inputs and single output:for discontinuous traffic flow, the inputs are the average travel speed and the ratio of the queue; for continuous traffic flow, the inputs are the average travel speed and the flux; the output is the degree of crowdedness in the range of0to1. Dynamic model of the road network is established with combining the degree of crowdedness and the actual length of the road, which lays the foundation for the dynamic path optimization in the second part.Part Ⅱ:Dynamic path optimization algorithm is the core of the dynamic path optimization. The choice of algorithm is directly related to the dynamic nature, real-time and effectiveness of the dynamic path optimization. This paper selects the genetic algorithm to optimize path on the base of analysis and comparison of the commonly used shortest path algorithms, improves the selection, crossover and mutation operator, and an improved genetic algorithm based on dynamic model of the road network finally is built.Part Ⅲ:The clear definition of the convergence of genetic algorithm is given by consulting literatures. By this definition, the convergence of the improved GA is analyzed, and sufficient condition for the improved GA converging to the global optimal solution is reasoned. Finally, a simulation at MATLAB environment verifies the dynamic nature, real-time and effectiveness of the proposed algorithm.