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.

    本发明公开了一种基于图分区技术的高速公路最短路径拟合方法,包括:构建高速公路路网模型;选取关键性枢纽节点;采用图分区技术对高速公路路网模型进行区域初步划分;根据确定后的边界枢纽节点重新进行区域划分;计算每个分区内任意两个枢纽节点间的最短路径的中间参数,得到第一中间参数集合;计算任意两个边界枢纽节点间的最短路径的中间参数,得到第二中间参数集合;对任意两个收费站点,对第一中间参数集合和第二中间参数集合的最短路径进行拟合处理,得到两个收费站点间的最短路径。这样,可以解决计费模块加载的中间参数内存占用过多的问题,能够有效地降低中间参数内存占用量,同时具有较好的路径拟合性能。


    Zugriff

    Download


    Exportieren, teilen und zitieren



    Titel :

    Expressway shortest path fitting method based on graph partitioning technology


    Weitere Titelangaben:

    一种基于图分区技术的高速公路最短路径拟合方法


    Beteiligte:
    KUANG YONGQIANG (Autor:in) / LI YUANPENG (Autor:in) / ZHOU GANG (Autor:in)

    Erscheinungsdatum :

    25.04.2025


    Medientyp :

    Patent


    Format :

    Elektronische Ressource


    Sprache :

    Chinesisch


    Klassifikation :

    IPC:    G08G Anlagen zur Steuerung, Regelung oder Überwachung des Verkehrs , TRAFFIC CONTROL SYSTEMS



    A Shortest Path Algorithm Based on Hierarchical Graph Model

    Wu, Y. / Xu, J. / Hu, Y. et al. | British Library Conference Proceedings | 2003


    A shortest path algorithm based on hierarchical graph model

    Wu Yimin, / Xu Jianmin, / Hu Yucong, et al. | IEEE | 2003


    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

    Vehicle code fitting method and system for expressway scene

    LIU YULAI / JIANG ZHIPENG / XU PINGHU et al. | Europäisches Patentamt | 2024

    Freier Zugriff

    Finding Shortest Path in Road Networks Based on Jam-Distance Graph and Dijkstra’s Algorithm

    Ali, Sarah Fouad / Abdulrazzaq, Musaab Riyadh / Gaata, Methaq Talib | Springer Verlag | 2022