喬文瑛, 黃敏,3, 張小蘭
1.中山大學(xué)智能工程學(xué)院,廣東 深圳 518107
2.廣東省智能交通系統(tǒng)重點(diǎn)實(shí)驗(yàn)室,廣東 深圳 518107
3.廣東省交通環(huán)境智能監(jiān)測與治理工程技術(shù)研究中心,廣東 深圳 518107
4.廣東工貿(mào)職業(yè)技術(shù)學(xué)院,廣東 廣州 510510
城市交通大腦旨在利用實(shí)時(shí)全量的交通數(shù)據(jù)全局優(yōu)化城市交通資源,實(shí)現(xiàn)城市運(yùn)轉(zhuǎn)效能的根本提升(謝一明,2022)。在車輛個(gè)體身份感知方面,相比于其他傳統(tǒng)的交通傳感器,交通卡口能夠結(jié)合圖像處理技術(shù),實(shí)現(xiàn)細(xì)粒度更高的車輛識(shí)別,但受成本等因素限制很難實(shí)現(xiàn)路網(wǎng)全覆蓋,需要制定科學(xué)合理的選址方案,以滿足檢測需求。
大量學(xué)者對傳統(tǒng)檢測器的布設(shè)進(jìn)行了優(yōu)化。何勝學(xué)等(2016)提出了一種圖論算法,以流量檢測為目標(biāo)優(yōu)化定量線圈的布局。Hu et al.(2009)提出了一種基于路段來表示路網(wǎng)結(jié)構(gòu)的方法,通過檢測器布設(shè)能夠在穩(wěn)態(tài)條件下準(zhǔn)確估計(jì)所有鏈路流量。Xu et al.(2016)和Salari et al.(2019)引入檢測器故障或其他不確定因素,通過最小化先驗(yàn)路徑流量不確定性,優(yōu)化檢測器布設(shè)。Yang et al.(1991)首次提出“最大可能相對誤差”的概念,利用檢測數(shù)據(jù)分析估計(jì)OD 矩陣的可信度。劉明等(1993)對該方法做了進(jìn)一步研究。楊曉光等(2011)依據(jù)不同的OD 矩陣估計(jì)模型進(jìn)行布點(diǎn)優(yōu)化。Hao et al.(2022)利用協(xié)方差衡量不同時(shí)期OD需求的相關(guān)性,通過最小化OD 需求估計(jì)的不確定性來優(yōu)化多類型交通檢測器的布設(shè)。Kim et al.(2011)基于微觀交通仿真,研究檢測器布設(shè)位置對旅行時(shí)間估計(jì)的影響。Danczy et al.(Danczy et al.,2011;Danczy et al.,2016)通過最小化旅行時(shí)間估算誤差來優(yōu)化交通檢測器布設(shè)方案。Jenelius et al.(2018)研究了在城市路網(wǎng)背景下,利用AⅤⅠ檢測器、浮動(dòng)車等移動(dòng)檢測器對旅行時(shí)間進(jìn)行檢測估計(jì)。
近年來,也有部分學(xué)者研究了視頻監(jiān)控點(diǎn)的選點(diǎn)規(guī)劃。劉暢(2015)提出“全范圍無盲區(qū),交互構(gòu)成封閉”的攝像機(jī)布設(shè)原則,以實(shí)現(xiàn)流量出入監(jiān)測和重點(diǎn)區(qū)域監(jiān)測等目的。逯峰等(2016)使用機(jī)器學(xué)習(xí)挖掘卡口布設(shè)與時(shí)空要素的關(guān)系,針對未來的路網(wǎng)空間進(jìn)行了卡口布設(shè)優(yōu)化。2017 年,He et al.(2018)首次在車輛交通和攝像頭位置之間建立聯(lián)系,以實(shí)現(xiàn)更好的安全監(jiān)控。沈凌等(2021)針對橋梁覆蓋率、重要場所出入口覆蓋率和關(guān)鍵性節(jié)點(diǎn)覆蓋率等指標(biāo),研究了城市道路監(jiān)控設(shè)備布設(shè)方案評價(jià)方法。
綜上所述,由于傳統(tǒng)檢測器獲取的信息有局限性,如僅能檢測道路截面信息、主要檢測宏觀信息等,目前的研究大多為面向宏觀交通狀態(tài)檢測的傳統(tǒng)檢測器布設(shè),而針對卡口檢測器布設(shè)的研究較少。因此,本文將以有向路網(wǎng)為研究對象,在保證流量檢測和OD 檢測的基礎(chǔ)上,從車輛出行軌跡重構(gòu)效果最優(yōu)出發(fā),將缺失軌跡離散度作為表征軌跡重構(gòu)準(zhǔn)確度的參數(shù),構(gòu)建了卡口布設(shè)優(yōu)化問題模型和求解框架,并通過算例驗(yàn)證模型的可行性。
本文以有向路網(wǎng)為研究對象,如圖1所示。在當(dāng)前卡口布設(shè)下,車輛veh1和veh2均存在軌跡缺失。面向個(gè)體出行檢測優(yōu)化卡口布設(shè),就是要在卡口數(shù)量約束下布設(shè)卡口實(shí)現(xiàn)車輛軌跡重構(gòu)可靠度最高。首先,對基本信息和相關(guān)概念做出闡述。文中所涉及的符號(hào)及其含義如表1所示。
表1 符號(hào)及含義Table 1 Symbols and Meanings
圖1 示例路網(wǎng)Fig.1 Road network example
由于卡口設(shè)備的布設(shè)位置不同,其檢測信息也有所不同。將卡口設(shè)備分為兩類:
1)路段檢測卡口:通常布設(shè)在路段中,可以檢測所在路段流量、速度等宏觀信息,也可以識(shí)別途徑車輛的個(gè)體身份信息,精細(xì)識(shí)別車輛個(gè)體的時(shí)空狀態(tài)。由圖1 可見,路段檢測卡口tq1可檢測局部軌跡().
2)轉(zhuǎn)向檢測卡口:通常布設(shè)在交叉口進(jìn)口道、高速公路出入口匝道處等,可以檢測所在路段宏觀交通信息,還可以識(shí)別車輛下游行駛路段。如圖1 所示,轉(zhuǎn)向檢測卡口tp1可檢測軌跡為
1.2.1 可行路徑集考慮到經(jīng)濟(jì)、省時(shí)等因素,大多數(shù)司機(jī)在兩點(diǎn)間出行時(shí),往往優(yōu)先選擇距離最短路徑或較短路徑,此類路徑稱為可行路徑??尚新窂蕉x為:在有向路網(wǎng)G=(V,E)中,規(guī)定起點(diǎn)F的最短路權(quán)為L(F) = 0,其他節(jié)點(diǎn)設(shè)為∞,遍歷相鄰節(jié)點(diǎn),參照Dijkstra 算法,利用路段長度標(biāo)記每個(gè)節(jié)點(diǎn)的最短路權(quán)L.設(shè)有路徑rF,T=(… -- …),只要滿足其中任一路段∈E,均有L(i) =L(j),則定義rF,T為由起點(diǎn)F到訖點(diǎn)T的一條可行路徑(鄒志云,1997)。任意兩點(diǎn)間的所有可行路徑即構(gòu)成了兩點(diǎn)間的可行路徑集。
1.2.2 缺失軌跡重構(gòu)原理基于車輛個(gè)體的單次出行卡口檢測序列,將車輛每次出行時(shí)空軌跡通過卡口設(shè)備和路網(wǎng)關(guān)聯(lián)關(guān)系映射到路網(wǎng),可以得到卡口檢測下的部分出行軌跡。進(jìn)一步,對缺失部分進(jìn)行重構(gòu),根據(jù)相鄰兩次卡口檢測序列間的缺失情況,將其分為兩種情況:(1)缺失部分只含一條可行路徑;(2)缺失部分含多條可行路徑。對于情況(1),可以利用唯一的可行路徑直接補(bǔ)全缺失部分,定義為一次重構(gòu)。對于情況(2),則需要在多條可行路徑中確定一條最優(yōu)軌跡,作為重構(gòu)軌跡,定義為二次重構(gòu)。在現(xiàn)階段的研究中,不少學(xué)者利用卡口檢測數(shù)據(jù)進(jìn)行軌跡重構(gòu),主要方法包括:不基于交通流模型的方法、基于交通流模型的方法、混合模型方法(邢皓等,2019)。其中,不基于交通流模型的方法忽略擁堵和排隊(duì)等交通動(dòng)態(tài)模式,只利用時(shí)間、速度等數(shù)值計(jì)算方法對缺失的軌跡進(jìn)行重構(gòu)。在進(jìn)行軌跡點(diǎn)還原的過程中,通常會(huì)針對兩條確切軌跡之間軌跡缺失的部分,確定一組備選軌跡集。然后,引入路段數(shù)量、轉(zhuǎn)彎次數(shù)、理論速度等決策屬性,計(jì)算各備選方案與最優(yōu)方案的接近程度,最終選取最接近的備選軌跡作為最優(yōu)軌跡(楊帥等,2016)。
基于此原理,記兩段確切軌跡A、B 之間的缺失軌跡集為MPAB={mpAB1,mpAB2,…,mpABm}.其中,對于某條缺失軌跡mpABi=(e1,e2,…,en),途徑路段數(shù)記為ni,軌跡長度記為理論通行時(shí)間記為其中spek為路段ek的理論速度。因此,由m條缺失軌跡的屬性值組成m× 3的初始決策矩陣,記為
對初始決策矩陣進(jìn)行標(biāo)準(zhǔn)化,得到標(biāo)準(zhǔn)化決策矩陣
設(shè)置權(quán)重向量
對屬性值賦權(quán),備選軌跡加權(quán)屬性值為
根據(jù)卡口序列記錄的實(shí)際過車時(shí)間,計(jì)算理論軌跡屬性值,最接近的備選軌跡即為最優(yōu)軌跡。因此,基于本文提出的缺失軌跡一次重構(gòu)和二次重構(gòu)原理,能夠創(chuàng)建相應(yīng)指標(biāo)以構(gòu)建優(yōu)化模型。
優(yōu)化模型的決策變量Q、P,為0-1 對角矩陣。路網(wǎng)原始布設(shè)矩陣表示為Q0、P0,對于無卡口的全新路網(wǎng),Q0=P0= diag(0,0,…,0).
基于卡口布設(shè)矩陣和路段流量矩陣計(jì)算流量捕獲率大小,即卡口可覆蓋的流量占路網(wǎng)總流量的比例,以衡量卡口對于路網(wǎng)在途車輛的檢測情況。即
其中I=[1 1 … 1 ]1×n;Ζ= diag(z1,…,zn),表示路段ei是否存在卡口布設(shè)。且
即當(dāng)路段布設(shè)至少一個(gè)卡口時(shí),該路段流量可被捕獲,否則不被捕獲。
對軌跡缺失部分進(jìn)行一次重構(gòu),具有較高的可靠度。本文定義軌跡覆蓋率,以衡量卡口設(shè)備對車輛軌跡檢測的完整性。假設(shè)某OD 量為XOD,其間有多條可行路徑POD={p1p2…pi…},流量占比為FOD=[f1f2…fi… ] ,單條可行路徑的軌跡覆蓋率為一次重構(gòu)后的局部檢測軌跡權(quán)值占完整軌跡權(quán)值的比率ci, 記COD=[c1c2…ci… ].參考MⅠⅠACR 法(Feng et al.,2019),本文基于靜態(tài)拓?fù)浣Y(jié)構(gòu)和動(dòng)態(tài)GPS 數(shù)據(jù)對路段關(guān)鍵程度進(jìn)行量化,軌跡權(quán)值即軌跡途徑路段關(guān)鍵程度之和?;诖耍琌D 間所有軌跡的平均覆蓋率為
整個(gè)路網(wǎng)所有OD對之間的軌跡覆蓋率均值
其中sum表示路網(wǎng)中OD對數(shù)量。
基于缺失軌跡二次重構(gòu)的原理,用缺失軌跡離散度衡量二次重構(gòu)的可靠性。對于確切軌跡A、B 間備選軌跡的加權(quán)屬性值SAB=?!T=[sAB1sAB2…sABm]T,用方差衡量備選軌跡集MPAB的離散度。有
面向出行軌跡重構(gòu)最優(yōu),本文以最大化路網(wǎng)缺失軌跡離散度SD為優(yōu)化目標(biāo),優(yōu)化模型如下:
其中ΔQ、ΔP表示新增布設(shè)矩陣。式(12)-(14)依次對卡口數(shù)量、監(jiān)測流量、覆蓋軌跡進(jìn)行了約束,從而保證一定程度的軌跡監(jiān)測;在此基礎(chǔ)上對缺失軌跡離散度進(jìn)行優(yōu)化,實(shí)現(xiàn)了更有效可靠的軌跡重構(gòu)與檢測。
考慮到實(shí)際路網(wǎng)的規(guī)模大小,優(yōu)化模型的求解為NP-hard 問題,難以采用傳統(tǒng)的精確算法進(jìn)行求解。因此,本文采用粒子群算法(PSO,particle swarm optimization)求解模型近似最優(yōu)解。PSO算法通過群體中個(gè)體之間的協(xié)作和信息共享來尋找最優(yōu)解,具體流程如圖2所示。
圖2 粒子群算法流程圖Fig.2 Flow chart of particle swarm optimization
以廣州市海珠區(qū)某局部區(qū)域路網(wǎng)為例,路網(wǎng)拓?fù)湟妶D3。過濾孤立點(diǎn)、孤立路段等要素,經(jīng)過預(yù)處理后的路網(wǎng)共有44 個(gè)節(jié)點(diǎn),124 條有向路段,當(dāng)前已布設(shè)17 個(gè)交通檢測卡口,包括7 個(gè)轉(zhuǎn)向檢測卡口和10 個(gè)路段檢測卡口;遵循經(jīng)驗(yàn),其布設(shè)主要分布于外圍主干路,缺少對次干路、支路的軌跡檢測(圖4)。在當(dāng)前實(shí)際卡口布設(shè)方案下,整體路網(wǎng)的流量捕獲率為12.89%,軌跡覆蓋率為74.00%,缺失軌跡離散度為0.036。
圖3 研究區(qū)域局部路網(wǎng)Fig.3 Local road network in the study area
圖4 當(dāng)前布設(shè)下的檢測軌跡與缺失軌跡Fig.4 The monitored trajectory and missing trajectory at present
將案例路網(wǎng)看作無基礎(chǔ)卡口的全新路網(wǎng),采用PSO 算法求解優(yōu)化模型。以當(dāng)前布設(shè)方案相關(guān)指標(biāo)為閾值,設(shè)置模型參數(shù)Nmax= 17,Vmin= 12%,COVmin= 70%,T= 500,求解得到的卡口布設(shè)優(yōu)化方案如圖5 所示,對路網(wǎng)的檢測情況如圖6 所示。結(jié)果表明,與當(dāng)前布設(shè)相比,優(yōu)化方案更多地兼顧了次干路、支路級(jí)布設(shè)規(guī)模,提升了卡口設(shè)備檢測細(xì)粒度。路網(wǎng)整體指標(biāo)如表2所示。對比路網(wǎng)整體指標(biāo),可以發(fā)現(xiàn):優(yōu)化方案整體路網(wǎng)流量捕獲率為19.09%,軌跡覆蓋率為76.76%,缺失軌跡離散度為0.086。與當(dāng)前實(shí)際布設(shè)方案相比,優(yōu)化方案在流量捕獲率方面提升了6.20%,軌跡覆蓋率提升了2.76%,缺失軌跡離散度提升了139%。與傳統(tǒng)的兩類布設(shè)方案相比,優(yōu)化方案在軌跡檢測方面均表現(xiàn)出更優(yōu)的效果。
表2 路網(wǎng)整體指標(biāo)對比Table 2 Comparison of overall road network indicators
圖5 卡口布設(shè)優(yōu)化結(jié)果Fig.5 Bayonet layout optimization results
圖6 優(yōu)化布設(shè)下的檢測軌跡與缺失軌跡Fig.6 The monitored trajectory and missing trajectory after optimizition
在廣州市2021年8月29日的車輛GPS數(shù)據(jù)中,隨機(jī)選取研究區(qū)域內(nèi)的100條車輛出行軌跡,對比優(yōu)化前后卡口布設(shè)方案的軌跡覆蓋率(見圖7 和表3)、軌跡重構(gòu)準(zhǔn)確率情況(見圖8 和表4)。結(jié)果表明,優(yōu)化方案在加強(qiáng)軌跡檢測和車輛個(gè)體出行軌跡重構(gòu)方面取得了更優(yōu)的效果。同時(shí),受限于卡口設(shè)備數(shù)量,仍有個(gè)別軌跡檢測率和軌跡重構(gòu)準(zhǔn)確率較低,需通過增加卡口數(shù)量進(jìn)一步完善。
表3 隨機(jī)100條軌跡的軌跡覆蓋率區(qū)間對比Table 3 Comparison of track coverage interval of 100 random tracks
表4 隨機(jī)100條軌跡的軌跡重構(gòu)準(zhǔn)確率區(qū)間Table 4 Accuracy intervals of track reconstruction for 100 random tracks
圖7 隨機(jī)100條軌跡的軌跡覆蓋率Fig.7 Track coverage of 100 random tracks
圖8 隨機(jī)100條軌跡的軌跡重構(gòu)準(zhǔn)確率Fig.8 Track reconstruction accuracy of random 100 tracks
以當(dāng)前卡口布設(shè)為基礎(chǔ)(即Q0、P0已知),新增卡口以實(shí)現(xiàn)最優(yōu)檢測目標(biāo)。模型約束條件同上,Vmin= 12%,COVmin= 70%,以缺失軌跡離散度為優(yōu)化目標(biāo),依次新增1-6個(gè)卡口進(jìn)行模型求解。新增5 個(gè)卡口的位置和新增卡口布設(shè)優(yōu)化結(jié)果如圖9和表5 所示。結(jié)果表明:隨著新增卡口數(shù)量的增多,各指標(biāo)均表現(xiàn)出上升狀態(tài)。以N= 5 為例,在江南大道、紫丹大街、寶業(yè)路、懷德大道新增路口卡口,在紫金大街新增路段卡口,可以獲得最優(yōu)的效果,相應(yīng)位置如圖9 所示。在此新增方案下,流量捕獲率為16.07%,軌跡覆蓋率為74.91%,缺失軌跡離散度達(dá)到0.12。
表5 新增卡口布設(shè)優(yōu)化結(jié)果Table 5 Added bayonet layout optimization results
圖9 新增5個(gè)卡口位置示意圖Fig.9 Position of five bayonets added
針對有向路網(wǎng),從軌跡重構(gòu)效果最優(yōu)角度出發(fā),本文面向車輛個(gè)體出行檢測任務(wù)構(gòu)建了卡口布設(shè)優(yōu)化模型。并以廣州市海珠區(qū)某局部路網(wǎng)為例,對全新布設(shè)和新增布設(shè)兩類應(yīng)用場景進(jìn)行了算例分析,結(jié)果表明:在全新布設(shè)下,優(yōu)化布設(shè)方案比當(dāng)前方案的流量捕獲率提高了6.20%、軌跡覆蓋率提高了2.76%、缺失軌跡離散度提高了139%,能夠有效提升軌跡檢測力度和軌跡重構(gòu)可靠性,在車輛個(gè)體出行檢測任務(wù)中發(fā)揮更好的效益。在新增布設(shè)下,分別對新增1-6個(gè)卡口進(jìn)行求解,得到了新增位置及最優(yōu)解。在未來,還可以拓展模型的應(yīng)用場景,調(diào)用不同的指標(biāo),制定可兼容多功能的卡口布設(shè)優(yōu)化方案,以達(dá)到更佳的布設(shè)效果?;蛘邔⒖谂c其他檢測器相結(jié)合,考慮多種類檢測器的布設(shè)優(yōu)化。