[發明專利]快速確定道路網絡容量最大路徑的方法、裝置及存儲介質

有效

• 申請號: 202110472779.7
• 申請日: 2021-04-29
• 公開（公告）號: CN113128010B
• 公開（公告）日: 2022-07-08
• 發明（設計）人: 黃汝晴;況愛武;張生;黃中祥
• 申請（專利權）人: 長沙理工大學
• 主分類號: G06F30/18
• 分類號: G06F30/18;G08G1/01
• 代理公司: 西安知誠思邁知識產權代理事務所(普通合伙) 61237
• 代理人: 閔媛媛

1.一種快速確定道路網絡容量最大路徑的方法，其特征在于，具體為：

S1：對于給定的OD對(r,s)，從起點r開始，設定起點r為永久標號節點，r∈P，道路網絡中其余各節點j均為臨時標號節點，j∈T，j≠r；根據MC(j)＝min(MC(r),c_rj)逐步確定起點r至下游所有節點的路徑的最大容量，將T中MC(j)最大值對應的臨時標號節點修改為永久標號節點；

其中，(r,s)表示起點為r訖點為s的OD對，MC(j)表示起點r至節點j的路徑的最大容量；P為永久標號節點集合，T表示臨時標號節點的集合，起點至臨時標號節點的路徑和路徑容量尚未求出，起點r至道路網絡中臨時標號節點的路徑的最大容量的初始值均為0；起點r到起點r的路徑的最大容量為+∞，即MC(r)＝+∞；c_rj表示連接節點r至節點j的路段(r,j)的初始容量；

S2：檢查所有節點，直至所有節點均為永久標號節點；

S3：根據每個永久標號節點的上游節點、指向每個永久標號節點的路段編號、起點r至所有永久標號節點的路徑的最大容量，從終點開始，反向追蹤終點至起點，從而確定道路網絡中OD對(r,s)間的容量最大路徑；

所述步驟S1中，根據MC(j)＝min(MC(r),c_rj)逐步確定起點r至下游所有節點的路徑的最大容量，將T中MC(j)最大值對應的臨時標號節點修改為永久標號節點，具體步驟是：

S11：依次考察離開起點r的各條路段(r,j)，求出起點r至各下游節點j的路徑的最大容量MC(j)，MC(j)＝min(MC(r),c_rj)；如果MC(j)大于其初始值，則替換其初始值，并記錄通往節點j的上游節點為節點r，即NTON(j)＝r；

S12：根據確定T中最大值對應的臨時標號節點，如果起點至節點k的路徑的最大容量最大，k∈T，那么將節點k由T標號點修改為P標號點，即P(k)＝p。

2.根據權利要求1所述的一種快速確定道路網絡容量最大路徑的方法，其特征在于，所述步驟S2具體為：檢查所有節點是否均為永久標號節點，如果有節點仍為臨時標號節點，以最近修改的永久標號節點替換起點r，重復步驟S11和步驟S12，直至所有節點均為永久標號節點。

3.根據權利要求1所述的一種快速確定道路網絡容量最大路徑的方法，其特征在于，所述步驟S12還包括：記錄起點r至節點k的路段編號，并檢查起點r至節點k間是否存在平行路段，如果存在平行路段，則找出其中容量最大的路段編號l，并記錄該編號，即LTON(k)＝l，LTON(k)＝l表示通往節點k的路徑包含路段l。

4.根據權利要求1所述的一種快速確定道路網絡容量最大路徑的方法，其特征在于，所述步驟S3中，節點r至節點s的容量最大路徑的最大容量為MC(s)，s為終點且為永久標號節點，s∈P。

5.根據權利要求1所述的一種快速確定道路網絡容量最大路徑的方法，其特征在于，當所述MC(j)＝min(MC(r),c_rj)中的c_rj表示路段(r,j)的剩余容量時，能夠得到網絡中起點到其他各節點的剩余容量最大的路徑，路段剩余容量等于c_rj-x_rj，x_rj表示路段(r,j)的當前車流量。

6.一種快速確定道路網絡最大路徑的裝置，其特征在于，采用如權利要求1-5任一項所述的方法實現。

7.一種計算機存儲介質，其特征在于，所述存儲介質中存儲有至少一條程序指令，所述至少一條程序指令被處理器加載并執行以實現如權利要求1-5任一項所述的方法。