[發明專利]基于擁塞傳播分析的道路瓶頸識別方法及其系統

有效

• 申請號: 201810040761.8
• 申請日: 2018-01-16
• 公開（公告）號: CN108062860B
• 公開（公告）日: 2020-12-15
• 發明（設計）人: 毛國強;歐陽毅剛
• 申請（專利權）人: 深圳市戴升智能科技有限公司
• 主分類號: G08G1/01
• 分類號: G08G1/01;G06F17/18
• 代理公司: 深圳市精英專利事務所 44242
• 代理人: 馮筠

1.基于擁塞傳播分析的道路瓶頸識別方法，其特征在于，所述方法包括：

確定道路的擁塞路段，記錄擁塞時間；

將擁塞路段連接形成多組交通擁塞相關聯的擁塞路段對，并根據擁塞路段對內的第一路段的擁塞時間進行多組擁塞路段對的排序；

刪除排序后的擁塞路段對中出現頻率不滿足設定頻率的擁塞路段對，形成擁塞路段對序列；

以形成擁塞路段對序列為基礎，構建樹形結構的有向圖；

分解有向圖，獲取樹，并最大化樹的有向邊數目，形成交通擁塞樹；

對交通擁塞樹的每個頂點進行權重分配；

根據Markov模型的概率分析算法分析交通擁塞樹中一個頂點傳播至另一個相鄰頂點的概率，形成連接兩個頂點的有向邊的權重；

根據頂點的權重以及連接兩個頂點的有向邊的權重，計算交通擁塞樹中每個頂點的綜合權重值，根據綜合權重確定交通擁塞瓶頸；

將擁塞路段連接形成多組交通擁塞相關聯的擁塞路段對，并對擁塞路段對內的第一路段按照擁塞時間進行排序的步驟，包括以下具體步驟：

根據城市區域路網拓撲結構確定最大距離門限；

提取擁塞路段中每兩條路段之間擁塞距離小于最大距離門限的擁塞路段對，形成待定擁塞路段對；

根據待定擁塞路段對內每兩條路段之間的相隔距離以及擁塞時間的間隔，計算各待定擁塞路段對的擁塞傳播速度；

根據擁塞傳播速度確定擁塞傳播速度的頻率分布情況，并確定一個置信區間，形成擁塞傳播速度門限；

刪除待定擁塞路段對中擁塞傳播速度在擁塞傳播速度門限之外的待定擁塞路段對，形成多組擁塞路段對；

根據各擁塞路段對中第一條路段的擁塞時間先后順序，對多組擁塞路段對進行排序；

以形成擁塞路段對序列為基礎，構建樹形結構的有向圖的步驟，包括以下具體步驟：

初始化一個空集合G以及空集合S，將空集合S作為集合G的子集；

輸入一組擁塞路段對，并將所述擁塞路段對加入集合S中；

輸入下一組擁塞路段對，根據此擁塞路段對的兩條路段以及集合G的子集S內存儲的路段情況，對集合G進行更新處理；

判斷此擁塞路段對是否為最后一組擁塞路段對；

若是，則輸出集合G，形成有向圖；

若否，則返回所述輸入下一組擁塞路段對，判斷此擁塞路段對中兩條路段是否有且僅有一條路段在集合G的一個子集S中的步驟；

分解有向圖，獲取樹，并最大化樹的有向邊數目，形成交通擁塞樹的步驟，包括以下具體步驟：

將有向圖用鄰接矩陣表示；

初始化一個隊列，初始化一個集合A；

將有向圖中一個節點加入隊列，記此節點作為有向圖內樹的根節點，并對此節點進行標記；

判斷隊列是否為空；

若隊列不為空，獲取隊列內的隊尾節點；

輸入有向圖中另一個節點；

判斷此節點是否與隊尾節點相連且不在隊列中；

若否，返回所述輸入有向圖中另一個節點的步驟；

若是，將此節點加入隊列中，并標記此節點，將此節點與隊尾節點連接的邊加入到集合A中；

判斷此節點是否為有向圖中最后一個節點；

若否，返回所述輸入有向圖中另一個節點的步驟；

若是，則將隊尾節點從隊列中刪除，并返回判斷隊列是否為空的步驟；

若隊列為空，則輸出集合A；

判斷有向圖中輸入的樹的根節點是否為有向圖中最后一個節點；

若有向圖中輸入的樹的根節點不是有向圖中最后一個節點，則返回初始化一個隊列，初始化一個集合A的步驟；

若有向圖中輸入的樹的根節點是有向圖中最后一個節點，則判斷此有向圖是否為最后一個有向圖；

若是，則進入對交通擁塞樹的每個頂點進行權重分配的步驟；

若否，返回將有向圖用鄰接矩陣表示的步驟；

根據頂點的權重以及連接兩個頂點的有向邊的權重，計算交通擁塞樹中每個頂點的綜合權重值，根據綜合權重確定交通擁塞瓶頸的步驟，包括以下具體步驟：

獲取交通擁塞樹中所有出度為0的節點；

將出度為0的節點的頂點權重分別乘以出度為0的節點所連接的有向邊的權重，并將乘值分別加到出度為0的節點對應父節點的頂點權重中；

刪除出度為0的節點及出度為0的節點所對應的連接到父節點的有向邊；

判斷此交通擁塞樹中是否只剩下一個節點；

若否，則返回獲取交通擁塞樹中所有出度為0的節點的步驟；

若是，則輸出此交通擁塞樹中所有節點的權重；

判斷此交通擁塞樹是否為最后一個交通擁塞樹；

若否，則返回獲取交通擁塞樹中所有出度為0的節點的步驟；

若是，則刪除交通擁塞樹內各節點權重中的傳播路徑相同的重復項，將剩余的節點權重相加，形成各交通擁塞樹的各節點的傳播權重；

將各節點傳播權重與頂點權重相加，形成各節點的綜合權重；

選取各節點的綜合權重最大的節點，形成交通擁塞瓶頸。