The invention discloses a method for acquiring an all-source shortest path of an urban road network based on double-layer sharing calculation. The method comprises the following steps: 1, acquiring a real-time urban road network map; 2, selecting the intersection with the minimum number of non-p adjacent points from the intersections which do not belong to the p node in the road network intersection set; 3, if the number of non-p adjacent points of the intersection is 0, the intersection is an internal source point intersection, the upper bound of the weight of the shortest path from each adjacent intersection to the intersection in the road network is compared, the weight of the shortest path is directly updated, and otherwise, the weight of the shortest path is updated; selecting the intersection with the minimum number of non-p adjacent points in the adjacent intersections of which the intersection does not belong to the p node as a non-internal source point to obtain the weight of the shortest path; 4, the non-internal source point directly skips adjacent intersections of p nodes of the internal source point and the boundary source point when the upper bound of the weight of the shortest path is updated in each round; and 5, when all intersections in the intersection set are p nodes, ending searching and outputting. The implementation efficiency of large-scale road network navigation planning can be effectively improved.
本发明公开了一种基于双层共用计算的城市路网全源最短路径获取方法,包括:1获取实时城市道路路网图;2选出路网交叉口集合中不属于p节点的交叉口中非p邻点数最小的交叉口;3若该交叉口的非p邻点数为0,那么该交叉口为内部源点交叉口,对比经过各邻接交叉口到路网中交叉口的最短路径的权的上界直接更新最短路径的权,否则,选择该交叉口不属于p节点的邻接交叉口中非p邻点数最小的交叉口作为非内部源点来获取最短路径的权;4非内部源点在每一轮更新最短路径的权的上界时直接跳过内部源点和边界源点的p节点的邻接交叉口;5当交叉口集合中所有交叉口都为p节点,结束搜索并输出。本发明能有效提升大规模路网导航规划的实行效率。
Urban road network all-source shortest path acquisition method based on double-layer sharing calculation
一种基于双层共用计算的城市路网全源最短路径获取方法
2023-06-30
Patent
Elektronische Ressource
Chinesisch
IPC: | G06Q Datenverarbeitungssysteme oder -verfahren, besonders angepasst an verwaltungstechnische, geschäftliche, finanzielle oder betriebswirtschaftliche Zwecke, sowie an geschäftsbezogene Überwachungs- oder Voraussagezwecke , DATA PROCESSING SYSTEMS OR METHODS, SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL, SUPERVISORY OR FORECASTING PURPOSES / G08G Anlagen zur Steuerung, Regelung oder Überwachung des Verkehrs , TRAFFIC CONTROL SYSTEMS |
Urban road network shortest path acquisition method based on directivity induction
Europäisches Patentamt | 2021
|Europäisches Patentamt | 2021
|Urban K shortest path acquisition method considering real-time road condition
Europäisches Patentamt | 2024
|Urban K shortest path obtaining method based on shortest path tree
Europäisches Patentamt | 2024
|