The invention discloses an expressway shortest path fitting method based on a graph partitioning technology. The expressway shortest path fitting method comprises the following steps: constructing an expressway road network model; key hub nodes are selected; carrying out region preliminary division on the expressway road network model by adopting a graph partitioning technology; carrying out region division again according to the determined boundary hub nodes; calculating an intermediate parameter of a shortest path between any two hub nodes in each partition to obtain a first intermediate parameter set; calculating an intermediate parameter of a shortest path between any two boundary hub nodes to obtain a second intermediate parameter set; and for any two toll stations, carrying out fitting processing on the shortest path of the first intermediate parameter set and the second intermediate parameter set to obtain the shortest path between the two toll stations. Therefore, the problem of excessive memory occupation of the intermediate parameters loaded by the charging module can be solved, the memory occupation amount of the intermediate parameters can be effectively reduced, and meanwhile, the method has relatively good path fitting performance.
本发明公开了一种基于图分区技术的高速公路最短路径拟合方法,包括:构建高速公路路网模型;选取关键性枢纽节点;采用图分区技术对高速公路路网模型进行区域初步划分;根据确定后的边界枢纽节点重新进行区域划分;计算每个分区内任意两个枢纽节点间的最短路径的中间参数,得到第一中间参数集合;计算任意两个边界枢纽节点间的最短路径的中间参数,得到第二中间参数集合;对任意两个收费站点,对第一中间参数集合和第二中间参数集合的最短路径进行拟合处理,得到两个收费站点间的最短路径。这样,可以解决计费模块加载的中间参数内存占用过多的问题,能够有效地降低中间参数内存占用量,同时具有较好的路径拟合性能。
Expressway shortest path fitting method based on graph partitioning technology
一种基于图分区技术的高速公路最短路径拟合方法
25.04.2025
Patent
Elektronische Ressource
Chinesisch
IPC: | G08G Anlagen zur Steuerung, Regelung oder Überwachung des Verkehrs , TRAFFIC CONTROL SYSTEMS |
A Shortest Path Algorithm Based on Hierarchical Graph Model
British Library Conference Proceedings | 2003
|Urban K shortest path obtaining method based on shortest path tree
Europäisches Patentamt | 2024
|Vehicle code fitting method and system for expressway scene
Europäisches Patentamt | 2024
|Finding Shortest Path in Road Networks Based on Jam-Distance Graph and Dijkstra’s Algorithm
Springer Verlag | 2022
|