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节点,结束搜索并输出。本发明能有效提升大规模路网导航规划的实行效率。


    Zugriff

    Download


    Exportieren, teilen und zitieren



    Titel :

    Urban road network all-source shortest path acquisition method based on double-layer sharing calculation


    Weitere Titelangaben:

    一种基于双层共用计算的城市路网全源最短路径获取方法


    Beteiligte:
    DING JIANXUN (Autor:in) / YIN HUIJUAN (Autor:in) / FAN YINCHAO (Autor:in) / HUANG LINXUAN (Autor:in) / FAN ZHEYAN (Autor:in) / YANG BEINUO (Autor:in) / LIU HAOXIANG (Autor:in) / LONG JIANCHENG (Autor:in)

    Erscheinungsdatum :

    2023-06-30


    Medientyp :

    Patent


    Format :

    Elektronische Ressource


    Sprache :

    Chinesisch


    Klassifikation :

    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

    DING JIANXUN / JIANG YUPENG / ZHOU RUNDONG et al. | Europäisches Patentamt | 2021

    Freier Zugriff

    Urban road network shortest path acquisition method based on angle limitation and bidirectional search

    DING JIANXUN / FENG ZHANYU / JIANG YUPENG et al. | Europäisches Patentamt | 2021

    Freier Zugriff

    Urban K shortest path acquisition method considering real-time road condition

    DING JIANXUN / SHAN YUNHAN / DUAN RUI et al. | Europäisches Patentamt | 2024

    Freier Zugriff

    Urban K shortest path obtaining method based on shortest path tree

    DING JIANXUN / YANG BEINUO / DUAN RUI et al. | Europäisches Patentamt | 2024

    Freier Zugriff

    Time-constrained shortest path search algorithm for urban road network

    Jun, Kang / Zihao, Wu / Qianqian, Wang | IEEE | 2023