基于深度優先搜索算法的交通流向供需失衡路徑辨識

2021-07-29 02:09:06李襯襯李大龍宋子文

科學技術與工程 2021年14期

李襯襯，孫鋒，孫猛，李大龍，宋子文

(山東理工大學交通與車輛工程學院，淄博 255000)

城市交通系統是維持經濟發展與日常生活的基礎，交通形態和交通環境的復雜性以及交通供給的時滯性、有限性對城市路網中的交通出行者形成干擾，產生了不平衡的交通流分布，由此引發的交通擁堵嚴重制約了高峰時段的路網運行效率。中外學者針對此問題開展了一系列研究，柳波[1]建立了基于用戶均衡的交通流演化模型，研究了從一種非均衡交通流狀態到另外一種非均衡交通流狀態的過程；He等[2]通過預測-修正模型描述了交通流中斷后逐漸趨于均衡狀態的過程；Kumar等[3]認為路網靜態不均衡會導致駕駛員改變出行路徑，并建立了出行者動態路徑選擇模型；Naguney等[4]建立了由非穩定向穩定狀態轉化的模擬方法；Lida等[5]對出行者動態路徑的選擇行為進行了研究，認為道路交通流的理想均衡狀態難以達到；馬海波等[6]對交通流網格自適應負載平衡預測進行了研究。上述成果都集中在非均衡交通流向均衡交通流的演化規律及過程研究，而關于交通流向失衡特征及快速識別的研究卻涉及較少。分別針對交叉口、路段的流向失衡特征進行分析，并基于圖論和深度優化搜索算法(deep first search,DFS)算法構建了交通流失衡路徑識別模型，以期為流向供需失衡狀態下交通流管控奠定一定的理論基礎。

1 交通擁堵及供需失衡特征

流向供需失衡是指路段或交叉口不同方向流量比在不同時段表現出顯著差異性，導致空間資源供需錯位的運行狀態。該狀態在交叉口表現為進口不同轉向之間的非均衡性，在路段上表現為雙向車流之間的非對稱性。

1.1 交叉口流向供需失衡特征

交叉口流向供需失衡的表現特征是進口道不同轉向車流的時段性變化顯著，導致固有的車道功能劃分在部分時段無法適用，造成某一流向車道浪費而其他流向擁堵的現象。交通流轉向不平衡最明顯的特征是進口道各轉向交通流之比在不同時段有明顯差異性。

(1)交通流量變化。流向供需失衡進口道在流量變化方面呈現方向性轉向不平衡及波動明顯的現象。基于交叉口地磁檢測數據，對淄博市華光路—西五路交叉口15:30—19:30的車流量進行統計，統計結果如圖1所示。由圖1可知，平峰與晚高峰的直行與左轉車流量的比值變化浮動較大，呈現明顯的非均衡性。

(2)排隊長度變化。根據實地觀測，不同時段的平均排隊車輛數如圖2所示,晚高峰時段，直行排隊較長，達到了左轉排隊的3倍，影響綠燈期間的車流釋放效率。

圖2 交叉口不同時段的平均排隊車輛數Fig.2 Average number of queuing vehicles in different periods of intersection

由此可見，交叉口進口流向供需失衡特征可通過式(1)來描述：

(1)

式(1)中：Ai為路網節點失衡的閾值，可作為開啟可變車道條件的評價指標；d為轉向不均衡系數；x為飽和度。

(2)

式(2)中：Ql為左轉車車輛數；Qs為直行車車輛數；Qr為右轉車車輛數；b為左轉車車輛在總車數中所占的比例；d為標準轉向不均衡系數；n為左轉直行車道數總和；bgl,max、bpl,max分別為高峰期與平峰期左轉車輛的比例最大值；bgl,min、bpl,min分別為高峰期與平峰期左轉車輛的比例最小值；x為飽和度[7-8]。

當交叉口具有顯著轉向不平衡特征時，d≥1；當0.5≤d＜1時，交叉口具有輕微的不平衡特征；當d＜0.5時,交叉口不具有不均衡特征[9-10]。

1.2 路段流向供需失衡特征

路段流向供需失衡主要是由于兩個原因造成：①居民的通勤出行造成的潮汐交通流，其顯著特點是在時間上呈現規律性與周期性；②突發性事件造成的偶發性流向供需失衡[11-12]。

現基于路段微波檢測數據，對淄博市城區主干路世紀大道的潮汐交通特征進行調查，調查結果如表1所示。

表1 早晚高峰交通流量及方向分布系數對比表Table 1 Comparison of traffic flow and direction distribution coefficient in morning and evening peak

通過表1可以看出，在早高峰由西向東的方向分布系數為66.81%，已經超過臨界方向分布不均衡系數，達到了設置潮汐車道的交通條件。但是設置以后必須確保輕交通流方向上的路段飽和度不能低于重交通流方向上的路段飽和度，其通行能力能夠滿足該方向的交通需求。

由此可見，路段的失衡特征可以通過方向分布系數來描述：

(3)

式(3)中:Qq為輕交通流方向交通量；Qz為重交通流方向交通量;α為交通流影響因子。

根據方向分布系數和車流密度共同來確定路段可變車道的方向特征和管控策略，如式(4)所示：

(4)

式(4)中：Cl為路網路段供需失衡的閾值，可作為潮汐車道是否開啟的相關參照；k為方向分布系數；Iij為路段密度。

(5)

式(5)中:Iij為交叉口i與交叉口j之間的路段密度；k為車道數；L為路段長度。

1.3 網絡路徑流向供需失衡特征

目前，城市的網絡路徑流向供需失衡主要是由于城市規劃的功能分區布局不合理造成的。城市新建區域功能單一，多為居民住宅小區。商業、醫療、教育等資源仍然分布于城市中心，由此帶來的便是城市結構向組團式方向發展，如圖3所示。潮汐交通主要是由于人們白天進入中心城區辦公，下班后離開中心城區所導致的，此現象呈現出一定的規律性和周期性[13-14]。

流向供需失衡初期表現為節點、路段的流向供需失衡，隨著供需矛盾激化，逐步演化為區域路徑的流向供需失衡。區域性供需失衡問題需更加綜合和智能的管控手段去解決。而快速識別區域失衡路徑和組合可變導向車道、潮汐車道進行管控，是制定區域流向供需失衡管控對策的關鍵。網絡交通流向供需失衡特征演變如圖4所示。

圖3 網絡流向不均衡交通空間形成Fig.3 Diagram of tidal traffic spatial characteristics

圖4 網絡交通流向供需失衡特征Fig.4 Characteristics of imbalance between supply and demand of network traffic flow

為了解決上述問題，提出將可變車道與潮汐車道綜合使用的思路。首先潮汐車道默認為開啟狀態，可變車道設置原理為通過改變各流向的車道數來改變流量比，流量比反映了交通供給與交通需求的匹配情況，以左轉與直行方向的交通流量比為閾值，作為可變車道功能屬性轉換的依據。

假設可變導向車道初始狀態為左轉，則由左轉切換為直行需滿足的條件如式(6)所示：

(6)

可變導向車道功能由直行切換為左轉需滿足的條件如式(7)所示：

(7)

式中：Yl、Ys分別為左轉、直行方向流量比;Ql、Qs分別為左轉、直行方向交通量；Nl、Ns分別為左轉、直行方向車道數；Sl、Ss分別為左轉、直行方向單車道飽和流量；α、β為修正系數，可取0.8～0.9。

2 交通流向供需失衡路徑辨識模型

2.1 路網模型

網絡流向失衡特征可通過檢測路段及交叉口的流向供需失衡來確定，路口可轉化為路網上的節點，節點之間的路段可轉化為雙向線，并在節點和連線上賦予權重信息，整體路網就可以抽象為1個加權有向圖。可用式(8)表示：

G=(N,L,W)

(8)

路網的拓撲結構反應路段和交叉口之間的相互關系如圖5所示。

圖5 區域路網網絡圖例Fig.5 Legend of regional road network

路網權重可使用有向圖鄰接矩陣的邏輯結構來表示，一維數組可存儲路網中所有節點信息，若節點共有N個，則其對應的鄰接矩陣A={aij}在規則路網下是一個N×N的二維矩陣。二維數組中元素為1時，說明對應的兩個節點之間有著路段相連，反之則為0，如式(9)所示。

(9)

2.2 深度優先搜索算法

深度優化算法是一種搜索算法，其目的是達到被搜索結構的葉結點。其搜索原理[15]是當與節點v相鄰的邊全被搜索過，將回溯到發現節點v所在邊的起始節點，直到源節點可達到的所有節點，若還存在未被發現的節點，選擇其中未被發現的一個節點作為源節點，重復上述過程直到所有節點全部被訪問，搜索過程如圖6所示。

2.3 失衡路徑辨識模型

基于圖論的基礎理論和DFS算法，構建了一個路網失衡路徑的搜索模型。首先，分析路網的拓撲結構，利用有向加權圖的數據結構來定義節點和路段的關系，構建路網的基本結構模型；然后，對相關數據進行處理，利用上述供需失衡理論得出相應指標的閾值矩陣TM，與路網結構進行結合得到路網矩陣RM；最后，對重新構建的路網矩陣進行條件標記處理和DFS查找操作，計算和存儲查找得到的路徑，并將其輸出為路網路徑圖。其流程如圖7所示。