Calculation method of central guidance path optimization
Jing Li · 2011
Based on parallel calculation technology and network data storage method,traveler preferences were considered,the multi-level network decomposing method and the shortest path calculation method of deque were analyzed,and a new central guidance path optimization calculation method was put out.On the basis of the practical data of road networks in Changsha City and Changchun City,and tests on three different parallel calculation platforms including ordinary PC cluster,Lenovo server cluster and HP workstation cluster were carried out.Test result indicates that by using network data storage method,the storage locations of adjacency nodes and corresponding arcs can be determined directly,and the query time of node information obviously decreases.According to multi-level network decomposing method,the probability of main road as cutted arc reduces,and the commutation amounts of processors during the shortest path calculation process reduce.By using the shortest path calculation method of deque,the calculation speed of shortest path obviously increases.Through the new calculation method,the calculation time of 4 million shortest paths in Changsha City is 46 s,the calculation time of 11.7 million shortest paths in Changchun City is 72 s,and both of them satisfy the demand that central guidance path optimization time should be less than 5 min.