The invention discloses an urban K shortest path obtaining method based on a shortest path tree. The method comprises the following steps: 1, constructing an urban road network according to road condition information; 2, defining parameters and initializing; 3, expanding a starting point intersection node as a shortest path tree of a root node; 4, acquiring the kth short circuit from the starting point intersection node to the terminal point intersection; 4, acquiring an offset path of the kth short circuit between starting and ending point intersection nodes, and updating the distance to search the upper bound of the driving time; and 5, continuously expanding the shortest path tree according to the upper bound, and obtaining a K short circuit from the starting point intersection node to the terminal point intersection node. According to the method, the shortest path tree is considered and utilized, and repeated calculation is reduced, so that the navigation search efficiency can be improved, and efficient traffic operation is promoted.
本发明公开了一种基于最短路径树的城市K最短路径获取方法,包括:1.由路况信息构建城市路网;2.定义参数及初始化;3.拓展起点交叉口节点作为根节点的最短路径树;4.获取起点交叉口节点到终点交叉口的第k短路;4.并获取起终点交叉口节点间第k短路的偏移路径,更新路程搜索行车时间上界;5.依据上界继续拓展最短路径树,获取起点交叉口节点到终点交叉口节点的K短路。本发明考虑利用最短路径树,减少重复计算,从而能提高导航搜索效率,促进交通的高效运行。
Urban K shortest path obtaining method based on shortest path tree
一种基于最短路径树的城市K最短路径获取方法
2024-01-09
Patent
Electronic Resource
Chinese
IPC: | G08G Anlagen zur Steuerung, Regelung oder Überwachung des Verkehrs , TRAFFIC CONTROL SYSTEMS / 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 |
Geometric shortest path containers
Tema Archive | 2004
|Approximate Shortest Path Algorithms for Network-Tree Model
British Library Conference Proceedings | 2003
|Shortest Dubins path to a circle
AIAA | 2019
|A Multiple Pairs Shortest Path Algorithm
Online Contents | 2005
|