Research, Genetic Shortest-path Algorithm Based On The Urban Road Network

The shortest path problem is not only the key point of traffic network analysis, but also the foundation of arc routing and resource allocation and etc. From the viewpoint of network model, shortest path is to find a route which obstacle encountered is minimum. Shortest path can indicate the distance is shortest, and it's extending in meaning can be time, expenses and oil wear. Over the years, there are a lot of research results in related areas. According to experience summed up by our predecessors, the paper has improved GA on the basis of increasing the retrieval efficiency, and presented self-program.The research results of this paper are as follows:(1) Gathering data of road network, accomplishing the topological structure on basis of Nanjing local map, and setting up test platform which is fit for shortest path searching.(2) On above testing platform and based on SGA, the paper adopts real-coding, uses improved adjacency matrix combined with priori knowledge to generate initial population and change and improved the operation mode. Compared with Dijkstra algorithm on search results, it shows that algorithm exits some shortness as follows:traping to local optima easily, generating bad individual in potential and etc.(3) Aimed to the shortness of above algorithm, the paper puts forward some feasible methods, including combing roulette selection and elite protecting, adopting new crossover restricted by gene sequence, two points mutation. It is proved improved that algorithm is more effective by searching instances.(4) It has analysed the methods to solve shortest path in following three conditions:there is barrier in some road, demanding the first k shortest paths and passing least number of crunode, and given the specific examples.