Research On Dynamic Route Planning Problem Based On Community Detection

In recent years, the rapid development of domestic economy has brought an increasing traffic demand. Traffic congestion has become a comm on phenomenon in urban traffic and it affects people’s travel safety and efficiency. Vehicle navigation system becoms much more important in this case. Vehicle navigation system can relieve the road congestion by offering valid path planning stragety. The core function of vehicle navigation system is to offer an optimal or near-optimal route in a short time. It puts forwards a very high demand on the timeliness and accuracy of the route planning algorithm.Traditional route planning algorithm can not be directly applied to vehic le navigation system in large-scale road networks. Currently, route planning algorithm exploits hierarchial methods to reduce the scope of the search space by partitioning the road network into multiple subnet. Community detection method can find the community structure of the road network to form a hierarchical structure model. It puts the nodes which are similar into the same community, and puts the nodes which are not similar into different communities. This paper researchs on the strategy of building hierarchial road network model and hierarchial dynamic route planning algorithm based on community detection, and the major contribution is as follows:We take travel time as the closeness or similarity between nodes, and constuct a hierarchical representation of the road network based on community detection. We propose a hierarchical search method using the hierarchical road network model. The search will take place predominantly at higher levels of the road netwokr model w hich tend to be sparse and take the search result of higher levels as the search space of lower levels. It recursively reduces the search space from higher levels to lower levels. Finally, the search space of the actual road network will be limited in a very small scope. And the search process of each level is independent, so the implementation of each level can be adjusted according to different demands. We employ this method to Fuzhou traffic road network and make comparative experiments. Experiments results show that our method not only reduce the scope of search space, improve the search efficiency, but also improve the search accuracy when the start point and target point is far away.We apply the proposed hierarchical search method to different traffic scenarios, such as road construction, traffic accidents. The method can make dynamic local adjustment to the hierarchical road network stucture and replan the route. Expriments results show that the proposed method can effectively avoid the road constuction and traffic accidents.Based on the proposed community-based hierarchical search strategy, we apply Ant Colony Optimization(ACO) algorithm to the dynamic route planning problem. In dynamic traffic environment, vehicle needs to replan the route because of the dynamic nature of the traffic condition. We introduce the historical statistics to analyze the dynamic real-time traffic condition. Experiments results show that our improved ACO algorithm can inproves the accuracy of the route planning.