基于深度優(yōu)先搜索算法的交通流向供需失衡路徑辨識(shí)

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

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

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

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

流向供需失衡是指路段或交叉口不同方向流量比在不同時(shí)段表現(xiàn)出顯著差異性，導(dǎo)致空間資源供需錯(cuò)位的運(yùn)行狀態(tài)。該狀態(tài)在交叉口表現(xiàn)為進(jìn)口不同轉(zhuǎn)向之間的非均衡性，在路段上表現(xiàn)為雙向車流之間的非對(duì)稱性。

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

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

(1)交通流量變化。流向供需失衡進(jìn)口道在流量變化方面呈現(xiàn)方向性轉(zhuǎn)向不平衡及波動(dòng)明顯的現(xiàn)象?；诮徊婵诘卮艡z測(cè)數(shù)據(jù)，對(duì)淄博市華光路—西五路交叉口15:30—19:30的車流量進(jìn)行統(tǒng)計(jì)，統(tǒng)計(jì)結(jié)果如圖1所示。由圖1可知，平峰與晚高峰的直行與左轉(zhuǎn)車流量的比值變化浮動(dòng)較大，呈現(xiàn)明顯的非均衡性。

(2)排隊(duì)長(zhǎng)度變化。根據(jù)實(shí)地觀測(cè)，不同時(shí)段的平均排隊(duì)車輛數(shù)如圖2所示,晚高峰時(shí)段，直行排隊(duì)較長(zhǎng)，達(dá)到了左轉(zhuǎn)排隊(duì)的3倍，影響綠燈期間的車流釋放效率。

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

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

(1)

式(1)中：Ai為路網(wǎng)節(jié)點(diǎn)失衡的閾值，可作為開啟可變車道條件的評(píng)價(jià)指標(biāo)；d為轉(zhuǎn)向不均衡系數(shù)；x為飽和度。

(2)

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

當(dāng)交叉口具有顯著轉(zhuǎn)向不平衡特征時(shí)，d≥1；當(dāng)0.5≤d＜1時(shí)，交叉口具有輕微的不平衡特征；當(dāng)d＜0.5時(shí),交叉口不具有不均衡特征[9-10]。

1.2 路段流向供需失衡特征

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

現(xiàn)基于路段微波檢測(cè)數(shù)據(jù)，對(duì)淄博市城區(qū)主干路世紀(jì)大道的潮汐交通特征進(jìn)行調(diào)查，調(diào)查結(jié)果如表1所示。

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

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

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

(3)

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

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

(4)

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

(5)

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

1.3 網(wǎng)絡(luò)路徑流向供需失衡特征

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

流向供需失衡初期表現(xiàn)為節(jié)點(diǎn)、路段的流向供需失衡，隨著供需矛盾激化，逐步演化為區(qū)域路徑的流向供需失衡。區(qū)域性供需失衡問題需更加綜合和智能的管控手段去解決。而快速識(shí)別區(qū)域失衡路徑和組合可變導(dǎo)向車道、潮汐車道進(jìn)行管控，是制定區(qū)域流向供需失衡管控對(duì)策的關(guān)鍵。網(wǎng)絡(luò)交通流向供需失衡特征演變?nèi)鐖D4所示。

圖3 網(wǎng)絡(luò)流向不均衡交通空間形成Fig.3 Diagram of tidal traffic spatial characteristics

圖4 網(wǎng)絡(luò)交通流向供需失衡特征Fig.4 Characteristics of imbalance between supply and demand of network traffic flow

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

假設(shè)可變導(dǎo)向車道初始狀態(tài)為左轉(zhuǎn)，則由左轉(zhuǎn)切換為直行需滿足的條件如式(6)所示：

(6)

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

(7)

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

2 交通流向供需失衡路徑辨識(shí)模型

2.1 路網(wǎng)模型

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

G=(N,L,W)

(8)

路網(wǎng)的拓?fù)浣Y(jié)構(gòu)反應(yīng)路段和交叉口之間的相互關(guān)系如圖5所示。

圖5 區(qū)域路網(wǎng)網(wǎng)絡(luò)圖例Fig.5 Legend of regional road network

路網(wǎng)權(quán)重可使用有向圖鄰接矩陣的邏輯結(jié)構(gòu)來表示，一維數(shù)組可存儲(chǔ)路網(wǎng)中所有節(jié)點(diǎn)信息，若節(jié)點(diǎn)共有N個(gè)，則其對(duì)應(yīng)的鄰接矩陣A={aij}在規(guī)則路網(wǎng)下是一個(gè)N×N的二維矩陣。二維數(shù)組中元素為1時(shí)，說明對(duì)應(yīng)的兩個(gè)節(jié)點(diǎn)之間有著路段相連，反之則為0，如式(9)所示。

(9)

2.2 深度優(yōu)先搜索算法

深度優(yōu)化算法是一種搜索算法，其目的是達(dá)到被搜索結(jié)構(gòu)的葉結(jié)點(diǎn)。其搜索原理[15]是當(dāng)與節(jié)點(diǎn)v相鄰的邊全被搜索過，將回溯到發(fā)現(xiàn)節(jié)點(diǎn)v所在邊的起始節(jié)點(diǎn)，直到源節(jié)點(diǎn)可達(dá)到的所有節(jié)點(diǎn)，若還存在未被發(fā)現(xiàn)的節(jié)點(diǎn)，選擇其中未被發(fā)現(xiàn)的一個(gè)節(jié)點(diǎn)作為源節(jié)點(diǎn)，重復(fù)上述過程直到所有節(jié)點(diǎn)全部被訪問，搜索過程如圖6所示。

2.3 失衡路徑辨識(shí)模型

基于圖論的基礎(chǔ)理論和DFS算法，構(gòu)建了一個(gè)路網(wǎng)失衡路徑的搜索模型。首先，分析路網(wǎng)的拓?fù)浣Y(jié)構(gòu)，利用有向加權(quán)圖的數(shù)據(jù)結(jié)構(gòu)來定義節(jié)點(diǎn)和路段的關(guān)系，構(gòu)建路網(wǎng)的基本結(jié)構(gòu)模型；然后，對(duì)相關(guān)數(shù)據(jù)進(jìn)行處理，利用上述供需失衡理論得出相應(yīng)指標(biāo)的閾值矩陣TM，與路網(wǎng)結(jié)構(gòu)進(jìn)行結(jié)合得到路網(wǎng)矩陣RM；最后，對(duì)重新構(gòu)建的路網(wǎng)矩陣進(jìn)行條件標(biāo)記處理和DFS查找操作，計(jì)算和存儲(chǔ)查找得到的路徑，并將其輸出為路網(wǎng)路徑圖。其流程如圖7所示。

3 案例仿真分析

在對(duì)基礎(chǔ)路網(wǎng)進(jìn)行拓?fù)浣Y(jié)構(gòu)分析后，構(gòu)建其路網(wǎng)矩陣，利用DFS進(jìn)行供需失衡節(jié)點(diǎn)和路段的查找，得到節(jié)點(diǎn)的查找結(jié)果如圖9所示。

擁堵節(jié)點(diǎn)數(shù)為:10。

擁堵節(jié)點(diǎn)：節(jié)點(diǎn)2、節(jié)點(diǎn)5、節(jié)點(diǎn)6、節(jié)點(diǎn)7、節(jié)點(diǎn)9、節(jié)點(diǎn)11、節(jié)點(diǎn)12、節(jié)點(diǎn)13、節(jié)點(diǎn)16、節(jié)點(diǎn)17。

圖8 路網(wǎng)基礎(chǔ)結(jié)構(gòu)Fig.8 Road network infrastructure

圖9 供需失衡節(jié)點(diǎn)Fig.9 Supply and demand imbalance node

路段的查找結(jié)果如圖10所示。

擁堵路徑數(shù)為:2。

路徑1：節(jié)點(diǎn)2→節(jié)點(diǎn)6；節(jié)點(diǎn)6→節(jié)點(diǎn)7；節(jié)點(diǎn)7→節(jié)點(diǎn)11；節(jié)點(diǎn)11→節(jié)點(diǎn)12；

路徑2：節(jié)點(diǎn)12→節(jié)點(diǎn)16；節(jié)點(diǎn)17→節(jié)點(diǎn)13；點(diǎn)13→節(jié)點(diǎn)9；節(jié)點(diǎn)9→節(jié)點(diǎn)5。

圖10 供需失衡的路段Fig.10 Sections with unbalanced supply and demand

結(jié)合節(jié)點(diǎn)和路段的分析結(jié)果，輸出路網(wǎng)中供需失衡的路徑圖和相應(yīng)的路網(wǎng)矩陣熱力圖，如圖11及圖12所示。

綜上所述，路網(wǎng)失衡路徑的搜索模型能精確地搜索出相關(guān)的失衡節(jié)點(diǎn)和路段，可以快速找到失衡路徑，為可變車道和潮汐車道的合理管控提供了依據(jù)和技術(shù)支持。

圖11 路網(wǎng)供需失衡Fig.11 Analysis of imbalance between supply and demand of road network

圖12 路網(wǎng)矩陣熱力圖Fig.12 Thermal diagram of matrix of road network

4 結(jié)論

(1)針對(duì)交叉口、路段和網(wǎng)絡(luò)層面的流向失衡特征進(jìn)行分析，從路網(wǎng)節(jié)點(diǎn)供需失衡、路段供需失衡逐步演化出的區(qū)域路徑供需失衡出發(fā)，探討了可變導(dǎo)向車道和潮汐車道組合使用的問題，并列出了不同情況下的轉(zhuǎn)化條件。

(2)基于圖論和DFS算法構(gòu)建了交通流向失衡路徑識(shí)別模型，試驗(yàn)結(jié)果表明，路網(wǎng)失衡路徑的搜索模型能在基礎(chǔ)路網(wǎng)上精確地搜索出相關(guān)失衡節(jié)點(diǎn)、路段和失衡路徑，為可變導(dǎo)向車道和潮汐車道組合使用奠定了基礎(chǔ)。