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短路。本发明考虑利用最短路径树,减少重复计算,从而能提高导航搜索效率,促进交通的高效运行。


    Access

    Download


    Export, share and cite



    Title :

    Urban K shortest path obtaining method based on shortest path tree


    Additional title:

    一种基于最短路径树的城市K最短路径获取方法


    Contributors:
    DING JIANXUN (author) / YANG BEINUO (author) / DUAN RUI (author) / CHEN YU (author) / HUANG JUNPENG (author) / WANG YUYUE (author) / LONG JIANCHENG (author)

    Publication date :

    2024-01-09


    Type of media :

    Patent


    Type of material :

    Electronic Resource


    Language :

    Chinese


    Classification :

    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

    Wagner, Dorothea / Wilhalm, Thomas / Zaroliagis, Christos | Tema Archive | 2004


    Approximate shortest path algorithms for network-tree model

    Guozhen Tan, / Xiaojun Han, / Yilin Zhao, | IEEE | 2003


    Approximate Shortest Path Algorithms for Network-Tree Model

    Tan, G. / Han, X. / Zhao, Y. et al. | British Library Conference Proceedings | 2003


    Shortest Dubins path to a circle

    Manyam, Satyanarayana G. / Casbeer, David / Von Moll, Alexander L. et al. | AIAA | 2019


    A Multiple Pairs Shortest Path Algorithm

    Wang, I.-Lin | Online Contents | 2005