Experiential Hierarchical Model Of Road Network For Route Choice

Finding optimal paths in road networks was a fundamental application in various navigation services which ran on mobile equipments or map websites. Conventional path planning algorithms computed shortest paths between source nodes and target nodes in a graph abstracted from real-world road networks. However, optimal paths produced by conventional methods were usually different from paths adopted by experienced brains who were familiar with local road networks. The paths by human beings were always more reasonable than those computed by machines. Therefore, we proposed a novel hierarchy model of road network for route planning from the perspective of empirical knowledge. The model was extensively studied by the paper and its main contents consists of four parts.1. We reviewed shortest path algorithms, its variants for preprocessing methods and its dynamic variants. We noted the importance of its preprocessing methods for road network. For both academic research and industrial applications, the preprocess-ing methods was widely adopted as a part of standard optimal path computation procedure. Nevertheless, these methods ignore the empirical knowledge owned by brains in the literatures.2. We studied on a topological index and hierarchy traits of road network. The com-putation of the topological index,Betweenness Centrality, was based on the shortest path algorithm. Therefore, it was used to evaluate the topological importance of seg-ments in road networks. Six typical urban road networks were selected for Between-ness Centrality analysis. The experimental results showed that the distribution of Betweenness Centrality presented consistency and had a hierarchical property. The statistical results of Betweenness Centrality illustrated that the majority of road segments in high administrative levels characterized high value while the majority of road segments in low administrative levels had low value in urban road networks.3. We proposed an experienced methodology that constructed hierarchical road net-works for route planning. It depended on taxi drivers’ experience mining from massive GPS trajectories. The method mainly consisted of three steps. First, expe-rience routes of taxi drivers were recovered from original trajectories. Second, the experience roads were recognized and classified using travel frequency, speed infor- mation of experience routes and Betweenness Centrality of road segments. Third, strongly connected network of hierarchy were constructed from the classified roads so that hierarchical route planning can be implemented. A case study of a metropoli-tan area, Wuhan city, showed that experiential optimal paths can be dynamically obtained during different time intervals, particularly in rush hours. Experiments demonstrated that travel time of the experiential paths was less than that of the paths planned by conventional methods.4. We proposed a Voronoi-based hierarchical graph model of road network for route planning. It constructed the hierarchical graph and utilized graph Voronoi diagram to associate adjacent levels in hierarchical graph of road network. The method, by which this hierarchical model determined the nearest neighbor of entry or exit node of upper level road network, coincided with the way of thinking in which human would find entrance, which was nearest to him, to highway when he drove to somewhere faraway. Because of using graph Voronoi diagram, the hierarchical graph model can make the hierarchical searching process simpler and more efficient. The searching range was shrinked and the running time was decreased in the hierarchical route planning.