Traffic prediction based route planning in urban road networks

Computing the fastest driving routes in the presence of varying traffic conditions is an essential problem in modern navigation systems. Most existing systems compute the fastest route based on the current traffic conditions, while ignoring the effects of potential dynamics at a future moment. To solve this problem, a time-varying hierarchical graph model is presented for structuring the urban road network, and a hierarchical route computation algorithm is then proposed, which can compute the fastest congestion-avoidance driving routes in very fast response times. The experimental evaluation on a challenging urban environment of Jinan city demonstrates the effectiveness of the algorithm.