基于多细节路网Voronoi层次模型的最优路径算法

随着城市交通的日渐拥堵，最优路径算法已然成为众多研究学者共同关注的话题。本文在分析了线Voronoi图相关特性的基础上，构建了基于路段的Voronoi图层及其相对应的Voronoi多细节层次模型。在此基础上，结合空间层次推理的思想，本文进一步设计了一种基于线Voronoi图的最优路径算法，该算法首先利用起止点所在的Voronoi区域查找路径的主干部分，在找到的路径中，如果相应小区域内对应的道路不连通，则获取相关区域内的次级路网数据及其对应的Voronoi数据，继续计算最优路径，直到形成一个连通路段的集合。在此基础上，计算由起止点连接路径主干部分的分支路径。实验证明，该算法不仅符合人们对出行线路规划时的思维过程，还能有效地缩短车辆的出行时间，为人们的出行提供可靠、快捷的诱导策略。

The optimal path algorithm based on the hierarchical model of Voronoi-graph of roads with level of detail

With the increasing congestion in urban transport, the algorithm for finding the optimal path has become a topic of common concern for many research scholars. Based on the analysis of relevant properties of line-voronoi, the layer of voronoi-graph based on the road segment and the corresponding model of level of detail (LOD) were constructed. Upon this, an algorithm for finding the optimal path based on the line-voronoi was further proposed in this article. This algorithm first uses the voronoi-graph where the origin/destination is located to find the main part of the path. Within this path, if the corresponding road in each voronoi cell is not touched, lower level of roads in the relevant area and its corresponding voronoi-graphs are to be obtained. This process is continued to calculate the optimal path until a set of connected roads is computed. On this basis, the branch path connecting the main part of the path from the origin and destination is calculated in a similar way. Experiments showed that this algorithm not only conforms to the thinking process of route planning, but also can effectively shorten the traveling time, thereby providing a reliable and fast induction strategy for people to travel.