[發明專利]基于轉向關系的交通路網有向圖路徑模型構建及求解方法

有效

• 申請號: 201911084674.3
• 申請日: 2019-11-08
• 公開（公告）號: CN110807931B
• 公開（公告）日: 2021-09-17
• 發明（設計）人: 翟希;楊濤;許巖巖;鄭燁
• 申請（專利權）人: 許凌
• 主分類號: G08G1/01
• 分類號: G08G1/01
• 代理公司: 暫無信息
• 代理人: 暫無信息

本發明涉及一種基于轉向關系的交通路網有向圖路徑模型構建及求解方法。本發明填補了城市交通信號控制所需的有向路徑路網模型技術空白。本發明提出的空間邏輯拓撲關系較現有方法更加貼近現實，為路網級和車道級交通信號控制提供了專用控制路網構建的核心技術，并且能夠直接用于SCATS信號控制方案優化和性能評價，為城市交通管理水平提升，降低交通擁堵，優化交通出行環境起到重要作用。

技術領域

本發明涉及一種基于轉向關系的車道級交通路網有向圖路徑模型構建及求解方法，屬于城市道路交通信號控制理論與應用技術領域。

背景技術

隨著城市交通信息化基礎設施及智能交通系統建設的不斷發展，快速積累了大量的交通信息數據，可以為宏觀交通政策制定、交通行業管理、交通信息服務等提供有力支撐。目前，道路交通信息常見來源以線圈數據、GPS數據、車輛牌照數據、手機數據等為主。但是，以上海等城市為例，國內30多家城市擁有的道路交通信號控制SCATS系統，除了發揮交通信號控制的主要作用外，它作為一個重要的道路交通信息數據產生源，卻沒有被充分利用。

城市交通路網的有向圖數據模型是研究交通網絡問題的基礎環節。解決抽象數據與空間路網的映射和匹配，建立高效的路網拓撲結構及數據模型，在路徑規劃、最短路徑搜索和動態導航誘導問題方面具有重要意義。傳統路網模型的構建主要基于圖論的思想，依據時空間復雜度和求解問題的特點，將節點、路段和轉向這三個主要的路網要素抽象為帶有轉向賦權的有向圖問題。當交通路網被抽象成有向圖時，其拓撲結構的計算實現方法，就轉化成了有向圖“節點一路段一轉向”拓撲關系的數據結構問題。

主要的交通有向圖問題在數學和計算機領域已經被廣泛的研究，一般采用構建關聯矩陣、鄰接矩陣、鄰接表等拓撲結構，進行遍歷計算的方法。解決最短路徑問題的經典Djikstra算法，就是一種基于帶權的有向圖鄰接矩陣算法。以Djikstra算法為基礎，為了提高實際工程應用中數據存儲和計算的性能，還發展出單源路徑問題的各種優化算法和啟發式算法。但這些算法大多從計算機和運籌學出發，對實際城市路網結構的交通特性研究較少。

發明內容

本發明的目的是：以現有SCATS數據資源和實際城市道路空間結構特征分析為基礎，建立了一種車道級交通路網有向圖路徑模型構建方法。通過對路徑和交叉口節點的空間邏輯拓撲，建立分層次的拓撲關系和數據結構，可以對有向圖進行更多約束，便于優化各種算法和提高計算效率。

為了達到上述目的，本發明的技術方案是提供了一種基于轉向關系的交通路網有向圖路徑模型構建及求解方法，其特征在于，包括以下步驟：

步驟1、選取路網并建立該路網的路鏈方向矩陣W_d

將目標路網中每個路口定義為一個節點，第i個路口則為節點V_i，i＝1,2,...,N，相鄰兩個節點相連形成路鏈，第j條路鏈定義為E_j，j＝1,2,...,M，定義路鏈的方向，沿路鏈E_j的方向，將形成路鏈E_j的節點V_j及節點V_j+1分別定義為上游節點及下游節點，則有：

式中，E為目標路網有效路鏈集合，V_i,V_j為連接節點V_i及節點V_j的路鏈；

步驟2、建立路鏈轉向矩陣W_t

式中，定義當路鏈E_i轉入路鏈E_j為直行時w_t＝a，當路鏈E_i轉入路鏈E_j為左轉時w_t＝b，當路鏈E_i轉入路鏈E_j為右轉時W_t＝c。