[發明專利]一種城市的有效路徑集搜索方法

在審

• 申請號: 202110281475.2
• 申請日: 2021-03-16
• 公開（公告）號: CN113065073A
• 公開（公告）日: 2021-07-02
• 發明（設計）人: 王煒;金坤;李欣然;秦韶陽;周偉
• 申請（專利權）人: 東南大學
• 主分類號: G06F16/9537
• 分類號: G06F16/9537;G06F16/9535;G06F16/29
• 代理公司: 南京經緯專利商標代理有限公司 32200
• 代理人: 羅運紅

1.一種城市的有效路徑集搜索方法，其特征在于，所述方法包括：

獲取目標分配區域內所有節點的節點信息、所有路段的路段信息及所有OD點對的OD點對信息；

根據所有節點的所述節點信息和所有路段的所述路段信息，構建電子道路地圖網絡；

根據所述電子道路地圖網絡，構建對偶的電子道路地圖網絡；

根據所有OD點對的所述OD點對信息及所述對偶的電子道路地圖網絡進行有效路徑集的搜索，獲得所述目標分配區域內的有效路徑集。

2.根據權利要求1所述的方法，其特征在于，所述根據所有OD點對的所述OD點對信息及所述對偶的電子道路地圖網絡進行有效路徑集的搜索，獲得所述目標分配區域內的有效路徑集的步驟，包括：

根據所有OD點對的所述OD點對信息，確定所有OD點對的OD點對終節點；

基于堆優化的最短路算法，計算所述OD點對終節點到所述對偶的電子道路地圖網絡的對偶節點集合中所有其他節點的最短距離，獲得所述OD點對終節點到所有其他節點的最短距離；

根據所述OD點對終節點到所有其他節點的最短距離，確定有效路段；

根據所述有效路段，在所述電子道路地圖網絡中進行深度優先搜索，確定所述目標分配區域內的有效路徑集。

3.根據權利要求2所述的方法，其特征在于，所述根據所述OD點對終節點到所有其他節點的最短距離，確定有效路段的步驟，包括：

對所述目標分配區域內所有路段的起節點到所述OD點對終節點的最短距離進行分析，獲得起節點到所述OD點對終節點的最短距離；

對所述目標分配區域內所有路段的終節點到所述OD點對終節點的最短距離進行分析，獲得終節點到所述OD點對終節點的最短距離；

依次從所述目標分配區域內所有路段中選取當前路段，當所述當前路段的所述起節點到所述OD點對終節點的最短距離大于所述當前路段的終節點到所述OD點對終節點的最短距離時，確定所述當前路段為有效路段；

當所述當前路段的所述起節點到所述OD點對終節點的最短距離小于等于所述當前路段的終節點到所述OD點對終節點的最短距離時，確定所述當前路段為無效路段。

4.根據權利要求2所述的方法，其特征在于，所述根據所述有效路段，在所述電子道路地圖網絡中進行深度優先搜索，確定所述目標分配區域內的有效路徑集的步驟，包括：

在所述電子道路地圖網絡中，按照以OD點對的OD點對起節點到OD點對終節點進行深度優先搜索，確定所有OD點對對應的有效路徑；

根據所有OD點對對應的有效路徑的路徑阻抗對所有OD點對對應的有效路徑進行篩選，確定所述目標分配區域內的有效路徑集。