Research On Route Planning Based On Programmed Cell Death Evolutionary Algorithm

Intelligent transportation system is an important means to solve the problem of modern urban traffic.And the route planning service of vehicles is an essential part of ITS.In this thesis,based on the analysis of the current vehicle route planning method,a method of vehicle route planning based on the programmed cell death evolutionary algorithm is presented.The establishment of road network model,evolutionary algorithm based on programmed cell death and its application in vehicle route planning are studied respectively.First of all,the method of graph theory is applied to establish the digital abstract description of urban traffic road map.Taking some areas in Beijing as an example,an urban traffic network model is made for solving the dynamic routing by using the information in the electronic map of the area.Secondly,in order to overcome the premature of genetic algorithm,the three key control genes of programmed cell death in physiology are introduced into genetic algorithm as operators.And an evolutionary algorithm based on programmed cell death is proposed.This new algorithm is used to solve the multi-peak function optimization problem to prove the feasibility and effectiveness of the algorithm.Then,the convergence of the algorithm is analyzed by Markov chain.Finally,the evolutionary algorithm based on programmed cell death is applied to the vehicle route planning.By comparing with other route planning algorithm,it is proved that the algorithm can works effectively in dynamic vehicle routing planning with ideal feasibility.This algorithm has important significance for solving the actual vehicle route planning problem.