Dynamic Routing Algorithm And Implementation Based On Spatio-Temporal Predicting

The big traffic data in urban city transportation system provide abundant road network information and spatio-temporal traffic flow information.On one hand,those data lay a foundation for managers to predict and supervise the urban traffic conditions from macro perspective.On the other hand,they have important impact on individual travel,such as path choice problem.As a classical problem in graph theory,vehicle routing problem mostly assumes that the road network is static,that is,the impedance of the road section is constant.In the case of increasingly congested urban traffic,it is particularly necessary to introduce the random time-varying characteristics of road network traffic status into the vehicle routing problem to improve the level of logistics and distribution services.Based on the traffic flow theory and data analysis method,we discuss the traffic state's evolution law of large-scale urban road network,which is huge and has complicated structure.Then we propose a novel shortest path planning algorithm in stochastic time-varying networks according to the discovered law.Finally,we use the ground network of Shanghai as an example to verify the algorithm and a simple routing system is designed based on the algorithm.The detailed researching work is as follows:1)Proprose a strong association regions mining algorithm and a new prediction method based on strongly associated information.Firstly,the whole traffic network is rasterized by traffic partition method and data is fused in the grid.By this way the road segment data and intersection data are converted into grid data(or region data).Based on those region data,we studied the correlation information between adjacent regions,and defined a generation condition of strong associated regions by association rule theory,to discover the strong associated regions in whole network.Further we add the correlated information as an impact factor into the original prediction method in local region.Taking experiments,finally we compared results with the prediction methods without impact factor.2)Propose a double-layer dynamic routing algorithm.Based on the predict information of global traffic status and local vehicle flow,we implement a dynamic scrolling path planning algorithm.Firstly,for the rasterized grid,the traffic state and the real road network information are combined into the weight value,which means that the real road network is converted into a weighted directed graph.Then,we obtain the global path on upper layer(grid to grid)by Dijkstra algorithm.According to the upper planning result and the currently vehicle position,we again plan the adjacent lower path(intersection to intersection).Refresh the traffic status dynamicly,we judge whether it is necessary to re-plan the upper path,if it is,we re-plan the upper path.Otherwise we continue the lower routing.Finally,the algorithm is compared with the static routing method,and it is found the proposed algorithm could achieve good results in travel time.3)Apply the above algorithm to an interactive webpage,to realize the design of a simple path planning system.The interfiace framework of the system uses php language,and other tools are D3.js library of JavaScript and geographic information system ArcGIS platform.Firstly,the map files are converted into GeoJSON on ArcGIS,which D3.js require,and finally we realized the visualization of the administrative region and the ground network.The interface layout adopts CSS and HTML markup language,and uses its form functions to realize the interaction with users,namely obtain the input coordinates,then calls the path planning code(by python),gets planning relult and visualizes it on the interface.