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

有效

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

本發明公開了一種快速確定道路網絡容量最大路徑的方法、裝置及存儲介質，方法具體為：對于給定的OD對(r,s)，設定起點r為永久標號節點，r∈P，網絡其余各節點j均為臨時標號節點，j∈T，j≠r；根據MC(j)＝min(MC(r),c_rj)逐步確定起點r至下游所有節點的路徑最大容量，將集合T中MC(j)最大值對應的臨時標號節點修改為永久標號節點；檢查所有節點，直至所有節點均為永久標號節點；根據每個永久標號節點的上游節點、指向每個永久標號節點的路段編號、起點r至所有永久標號節點的路徑的最大容量，從終點開始，反向追蹤至起點，確定網絡中OD對(r,s)間的容量最大路徑。本發明快速確定從網絡任意節點到其他各節點的容量(或剩余容量)最大的路徑，確定該路徑的最大容量(或剩余容量)值，準確性高，搜索速度快。

技術領域

本發明屬于網絡系統工程技術領域，特別是涉及一種快速確定道路網絡容量最大路徑的方法、裝置及存儲介質。

背景技術

在交通運輸規劃與管理領域，經常需要對網絡交通流的均衡分布模式進行預測，進而開展各種交通規劃與管理工作。網絡流的均衡分布模式是由出行者的出行路徑選擇行為決定的，領域內一般假設出行者均選擇時間最短或者費用最小的路徑出行，這種路徑選擇行為最終在網絡上形成用戶均衡(User Equilibrium)分布模式。目前關于用戶均衡流的建模理論與求解方法比較成熟，相關成果非常豐富，構成了經典交通規劃內容。

事實上，出行者的出行路徑選擇行為具有多樣性，且影響路徑選擇行為的因素眾多，而目前的研究基本較少涉及。選擇既快捷又舒適的路徑出行是路徑選擇的一般性要求。選擇時間最短路徑體現的僅僅是出行者對出行快捷性的要求，如何描述出行者選擇舒適程度高的路徑，并進一步確定最終的均衡流模式是一個值得深入研究的問題，是將來構建由快捷性和舒適性路徑選擇行為共同構成的混合均衡流模式的前提基礎。

目前車輛導航系統給出行者推薦的路徑呈現多樣化的趨勢，不但推薦時間最短路徑，還推薦其他類型的路徑，如距離短紅綠燈多、高速多限速多(采用高德地圖導航時推薦的路徑選項)等路徑?，F有的圖論和系統工程分析方法多局限于如何求解網絡的最小(最短)路徑，如交通網絡中的時間最短路、費用最小路等等，然而在實際工程領域中存在著對網絡最大路徑的諸多需求，如在交通領域如何獲得可靠度最大的路徑，應急疏散能力最大的路徑等。

發明內容

本發明實施例的目的在于提供一種快速確定道路網絡容量最大路徑的方法、裝置及存儲介質，能夠快速確定從網絡中任意節點到其他各節點的容量(或剩余容量)最大的路徑，進而確定該路徑的最大容量值(或剩余容量最大值)，準確性高，搜索速度快。

為解決上述技術問題，本發明所采用的技術方案是，一種快速確定道路網絡容量最大路徑的方法，具體為：

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)間的容量最大路徑。