[發明專利]基于位序的多式聯運有效路徑搜索方法

在審

• 申請號: 202211534930.6
• 申請日: 2022-11-30
• 公開（公告）號: CN116090940A
• 公開（公告）日: 2023-05-09
• 發明（設計）人: 周博見;李世豪;陳婧煦;董瀟瀟;陳曉偉;張永
• 申請（專利權）人: 東南大學
• 主分類號: G06Q10/0835
• 分類號: G06Q10/0835;G06Q10/047
• 代理公司: 南京經緯專利商標代理有限公司 32200
• 代理人: 陳月菊

1.一種基于位序的多式聯運有效路徑搜索方法，其特征在于，包括如下步驟：

S1、采集各運輸方式下的多式聯運路網數據，根據多式聯運路網數據建立各運輸方式下運輸網絡中各節點及各路段的連通信息，根據連通信息連接不同運輸方式的運輸網絡，得到多式聯運網絡；

S2、初始化多式聯運網絡；輸入起始節點集和終訖節點集，路網中所有節點的坐標信息，以及建立每個節點的相鄰節點集；

S3：確定搜索的基準面；

S4：采用坐標變換的方式確定節點與基準面的相對位置；

S5：基于位序確定定向搜索節點的順序，包括確定容忍系數、創建同位序節點集以及在對同位序節點集中的節點按照排列組合原理羅列后按照位序對所有節點排序；

S6：建立多式聯運所有節點的轉運時間集；

S7：輸入多式聯運路段時間成本；

S8：基于位序進行搜索多式聯運有效路徑，包括初始化、檢查搜索節點判斷相鄰節點集的搜索情況、判斷轉運次數是否超過最大允許轉運次數、判斷是否完成搜索并在完成搜索后進行下一節點的搜索；

S9：建立時間成本最小的多式聯運的有效路徑集；

S10：終止本次起訖點的搜索，重新選取另一對起訖點，重復以上搜索過程，取遍所有相異的起訖點對則算法停止。

2.根據權利要求1所述的方法，其特征在于，多式聯運有效路徑為滿足以下幾個條件的路徑：

路徑k是無環簡單路徑，即只通過一個路段最多一次；

路徑k的費用c_OD處在最短路徑費用的(1+H)倍以內，即其中H為延展系數，是非負常數；

路徑k的轉運次數不超過多式聯運最大允許轉運次數Trn_max。

3.根據權利要求2所述的方法，其特征在于，步驟S1中，根據多式聯運路網數據建立各運輸方式下運輸網絡各節點及各路段的連通信息，具體包括：

構建一個多式聯運網絡G(N,A)，其中，N是節點集合、A是路段集合，令W表示多式聯運網絡中所有OD對的集合。起始節點集以O表示，終訖點集以D表示，節點i的坐標以v_i(x_i,y_i)表示，s(i)表示節點i的相鄰節點集；v_O為起始節點，v_O∈O，v_D為終訖節點，v_D∈D；c_ij表示節點i和節點j之間的路段時間費用；ε為容忍系數，為確定性參數；n_p為多式聯運有效路徑數量；Trn_max為多式聯運最大允許轉運次數。

4.根據權利要求3所述的方法，其特征在于，步驟S3中，確定搜索的基準面，具體包括：

選定單一OD對的起點坐標v_O(x₀,y₀)及訖點坐標v_D(x₁,y₁)；按起訖點連線的方向建立垂直平面，并保證該平面經過起點坐標v_O(x₀,y₀)，將該平面作為搜索基準面。

5.根據權利要求4所述的方法，其特征在于，步驟S4中，采用坐標變換的方式確定節點與基準面的相對位置，具體包括：

對節點坐標v_i(x_i,y_i)進行坐標變換，坐標變換方式為