基于层次空间推理的交通网络行车最优路径算法

讨论了如何在贪心策略及方向策略的基础上,利用人类思维的层次空间推理方法建立空间启发式搜索策略,以提高交通网络最短路径算法的效率和适用性,并使行车最优路径的选择更符合人类的思维特点。

An Optimum Vehicular Path Algorithm for Traffic Network Based on Hierarchical Spatial Reasoning

Among the known shortest path algorithms, most of which only take the greedy strategy as the searching strategy and concentrate on designing more delicate operational data structures and searching algorithms, to improve the running efficiency of sequential shortest path algorithms as much as possible under the consistent time complexity. However, greedy strategy is not the pronoun for heuristics, and the combination of several kinds of heuristics can apparently improve the running efficiency of the shortest path algorithms. Human beings' intellection is characteristic of a distinct hierarchy and it can be taken to construct a heuristic in the shortest path algorithms. It is detailed in this paper how to utilize the hierarchical reasoning method on the basis of greedy and directional strategy, to establish a spatial heuristic, so as to improve the running efficiency and suitability of the shortest path algorithm for traffic network, and to make the determination of the shortest path conform to the characteristics of human being intellection. The author discussed the spatial structure of urban traffic networks and divided the urban traffic network into three hierarchies, namely trunk road, ordinary road and alley. A new node hierarchy division rule is set forward through changing the corresponding relations between the nodes in the node sets of adjacent hierarchies. It avoids the unreliable solution of the shortest path that possibly emerges with the former node division rule. In the procedure of determining the shortest path between the source and the destination, through the hierarchical division of traffic network, the beginning calculation hierarchy is judged firstly for the source and the destination, which makes the shortest paths be determined on the higher hierarchies as much as possible. Then the shortest paths be-tween the respective adjacent nodes of the source and the destination in the higher hierarchies, [FK(W18°40ZQ]and the shortest paths between the nodes and the entrance nodes to the higher hierarchies are determined recursively and connected to form the last result. The shortest path algorithm based on spatial hierarchy reasoning is a kind of loss algorithm.It can not ensure that the result is the shortest path. The author argued that the shortest path, no matter distance shortest or time shortest, is usually not the favorite of drivers in practice. Some factors that are difficult to expect or quantify about the roads influence the drivers' choice greatly. It makes the drivers prefer to choose a less shortest, but more reliable or flexible path to travel. The algorithm that is set forward, in addition to improve the running efficiency of shortest path algorithms to several times, reduce the emergence of those factors compared to the non-hierarchical algorithms, and more conform to the intellection characteristic of human beings, and is more easily accepted by drivers. Moreover, because the gradual retrospect characteristic of the algorithm from the higher hierarchies to the lower hierarchies, it does not require the completeness of the networks in the lowest hierarchy, which makes some networks that are not full connected can be taken as the inputting. It improves the applicability and fault tolerance of the algorithm. The experimental results show the advantages of the optimum vehicular path algorithm based on spatial hierarchical reasoning.The author argued that the algorithm has great application potential for the navigation systems of large scale traffic networks.