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.