面向車輛個(gè)體出行檢測(cè)的卡口布設(shè)優(yōu)化模型

喬文瑛， 黃敏，3， 張小蘭

1.中山大學(xué)智能工程學(xué)院，廣東 深圳 518107

2.廣東省智能交通系統(tǒng)重點(diǎn)實(shí)驗(yàn)室，廣東 深圳 518107

3.廣東省交通環(huán)境智能監(jiān)測(cè)與治理工程技術(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é)合理的選址方案，以滿足檢測(cè)需求。

大量學(xué)者對(duì)傳統(tǒng)檢測(cè)器的布設(shè)進(jìn)行了優(yōu)化。何勝學(xué)等（2016）提出了一種圖論算法，以流量檢測(cè)為目標(biāo)優(yōu)化定量線圈的布局。Hu et al.（2009）提出了一種基于路段來表示路網(wǎng)結(jié)構(gòu)的方法，通過檢測(cè)器布設(shè)能夠在穩(wěn)態(tài)條件下準(zhǔn)確估計(jì)所有鏈路流量。Xu et al.（2016）和Salari et al.（2019）引入檢測(cè)器故障或其他不確定因素，通過最小化先驗(yàn)路徑流量不確定性，優(yōu)化檢測(cè)器布設(shè)。Yang et al.（1991）首次提出“最大可能相對(duì)誤差”的概念，利用檢測(cè)數(shù)據(jù)分析估計(jì)OD 矩陣的可信度。劉明等（1993）對(duì)該方法做了進(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)化多類型交通檢測(cè)器的布設(shè)。Kim et al.（2011）基于微觀交通仿真，研究檢測(cè)器布設(shè)位置對(duì)旅行時(shí)間估計(jì)的影響。Danczy et al.（Danczy et al.，2011;Danczy et al.，2016）通過最小化旅行時(shí)間估算誤差來優(yōu)化交通檢測(cè)器布設(shè)方案。Jenelius et al.（2018）研究了在城市路網(wǎng)背景下，利用AⅤⅠ檢測(cè)器、浮動(dòng)車等移動(dòng)檢測(cè)器對(duì)旅行時(shí)間進(jìn)行檢測(cè)估計(jì)。

近年來，也有部分學(xué)者研究了視頻監(jiān)控點(diǎn)的選點(diǎn)規(guī)劃。劉暢（2015）提出“全范圍無盲區(qū)，交互構(gòu)成封閉”的攝像機(jī)布設(shè)原則，以實(shí)現(xiàn)流量出入監(jiān)測(cè)和重點(diǎn)區(qū)域監(jiān)測(cè)等目的。逯峰等（2016）使用機(jī)器學(xué)習(xí)挖掘卡口布設(shè)與時(shí)空要素的關(guān)系，針對(duì)未來的路網(wǎng)空間進(jìn)行了卡口布設(shè)優(yōu)化。2017 年，He et al.（2018）首次在車輛交通和攝像頭位置之間建立聯(lián)系，以實(shí)現(xiàn)更好的安全監(jiān)控。沈凌等（2021）針對(duì)橋梁覆蓋率、重要場(chǎng)所出入口覆蓋率和關(guān)鍵性節(jié)點(diǎn)覆蓋率等指標(biāo)，研究了城市道路監(jiān)控設(shè)備布設(shè)方案評(píng)價(jià)方法。

綜上所述，由于傳統(tǒng)檢測(cè)器獲取的信息有局限性，如僅能檢測(cè)道路截面信息、主要檢測(cè)宏觀信息等，目前的研究大多為面向宏觀交通狀態(tài)檢測(cè)的傳統(tǒng)檢測(cè)器布設(shè)，而針對(duì)卡口檢測(cè)器布設(shè)的研究較少。因此，本文將以有向路網(wǎng)為研究對(duì)象，在保證流量檢測(cè)和OD 檢測(cè)的基礎(chǔ)上，從車輛出行軌跡重構(gòu)效果最優(yōu)出發(fā)，將缺失軌跡離散度作為表征軌跡重構(gòu)準(zhǔn)確度的參數(shù)，構(gòu)建了卡口布設(shè)優(yōu)化問題模型和求解框架，并通過算例驗(yàn)證模型的可行性。

1 問題描述

本文以有向路網(wǎng)為研究對(duì)象，如圖1所示。在當(dāng)前卡口布設(shè)下，車輛veh1和veh2均存在軌跡缺失。面向個(gè)體出行檢測(cè)優(yōu)化卡口布設(shè)，就是要在卡口數(shù)量約束下布設(shè)卡口實(shí)現(xiàn)車輛軌跡重構(gòu)可靠度最高。首先，對(duì)基本信息和相關(guān)概念做出闡述。文中所涉及的符號(hào)及其含義如表1所示。

表1 符號(hào)及含義Table 1 Symbols and Meanings

圖1 示例路網(wǎng)Fig.1 Road network example

1.1 卡口分類

由于卡口設(shè)備的布設(shè)位置不同，其檢測(cè)信息也有所不同。將卡口設(shè)備分為兩類：

1）路段檢測(cè)卡口：通常布設(shè)在路段中，可以檢測(cè)所在路段流量、速度等宏觀信息，也可以識(shí)別途徑車輛的個(gè)體身份信息，精細(xì)識(shí)別車輛個(gè)體的時(shí)空狀態(tài)。由圖1 可見，路段檢測(cè)卡口tq1可檢測(cè)局部軌跡().

2）轉(zhuǎn)向檢測(cè)卡口：通常布設(shè)在交叉口進(jìn)口道、高速公路出入口匝道處等，可以檢測(cè)所在路段宏觀交通信息，還可以識(shí)別車輛下游行駛路段。如圖1 所示，轉(zhuǎn)向檢測(cè)卡口tp1可檢測(cè)軌跡為

1.2 基于卡口檢測(cè)序列的軌跡重構(gòu)

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(zhǎng)(F) = 0，其他節(jié)點(diǎn)設(shè)為∞，遍歷相鄰節(jié)點(diǎn)，參照Dijkstra 算法，利用路段長(zhǎng)度標(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è)體的單次出行卡口檢測(cè)序列，將車輛每次出行時(shí)空軌跡通過卡口設(shè)備和路網(wǎng)關(guān)聯(lián)關(guān)系映射到路網(wǎng)，可以得到卡口檢測(cè)下的部分出行軌跡。進(jìn)一步，對(duì)缺失部分進(jìn)行重構(gòu)，根據(jù)相鄰兩次卡口檢測(cè)序列間的缺失情況，將其分為兩種情況：（1）缺失部分只含一條可行路徑；（2）缺失部分含多條可行路徑。對(duì)于情況（1），可以利用唯一的可行路徑直接補(bǔ)全缺失部分，定義為一次重構(gòu)。對(duì)于情況（2），則需要在多條可行路徑中確定一條最優(yōu)軌跡，作為重構(gòu)軌跡，定義為二次重構(gòu)。在現(xiàn)階段的研究中，不少學(xué)者利用卡口檢測(cè)數(shù)據(jù)進(jìn)行軌跡重構(gòu)，主要方法包括：不基于交通流模型的方法、基于交通流模型的方法、混合模型方法（邢皓等，2019）。其中，不基于交通流模型的方法忽略擁堵和排隊(duì)等交通動(dòng)態(tài)模式，只利用時(shí)間、速度等數(shù)值計(jì)算方法對(duì)缺失的軌跡進(jìn)行重構(gòu)。在進(jìn)行軌跡點(diǎn)還原的過程中，通常會(huì)針對(duì)兩條確切軌跡之間軌跡缺失的部分，確定一組備選軌跡集。然后，引入路段數(shù)量、轉(zhuǎn)彎次數(shù)、理論速度等決策屬性，計(jì)算各備選方案與最優(yōu)方案的接近程度，最終選取最接近的備選軌跡作為最優(yōu)軌跡（楊帥等，2016）。

基于此原理，記兩段確切軌跡A、B 之間的缺失軌跡集為MPAB={mpAB1，mpAB2，…，mpABm}.其中，對(duì)于某條缺失軌跡mpABi=(e1，e2，…，en)，途徑路段數(shù)記為ni，軌跡長(zhǎng)度記為理論通行時(shí)間記為其中spek為路段ek的理論速度。因此，由m條缺失軌跡的屬性值組成m× 3的初始決策矩陣，記為

對(duì)初始決策矩陣進(jìn)行標(biāo)準(zhǔn)化，得到標(biāo)準(zhǔn)化決策矩陣

設(shè)置權(quán)重向量

對(duì)屬性值賦權(quán)，備選軌跡加權(quán)屬性值為

根據(jù)卡口序列記錄的實(shí)際過車時(shí)間，計(jì)算理論軌跡屬性值，最接近的備選軌跡即為最優(yōu)軌跡。因此，基于本文提出的缺失軌跡一次重構(gòu)和二次重構(gòu)原理，能夠創(chuàng)建相應(yīng)指標(biāo)以構(gòu)建優(yōu)化模型。

2 優(yōu)化模型構(gòu)建

優(yōu)化模型的決策變量Q、P，為0-1 對(duì)角矩陣。路網(wǎng)原始布設(shè)矩陣表示為Q0、P0，對(duì)于無卡口的全新路網(wǎng)，Q0=P0= diag(0，0，…，0).

2.1 流量捕獲率約束

基于卡口布設(shè)矩陣和路段流量矩陣計(jì)算流量捕獲率大小，即卡口可覆蓋的流量占路網(wǎng)總流量的比例，以衡量卡口對(duì)于路網(wǎng)在途車輛的檢測(cè)情況。即

其中I=[1 1 … 1 ]1×n；Ζ= diag(z1，…，zn)，表示路段ei是否存在卡口布設(shè)。且

即當(dāng)路段布設(shè)至少一個(gè)卡口時(shí)，該路段流量可被捕獲，否則不被捕獲。

2.2 軌跡覆蓋率約束

對(duì)軌跡缺失部分進(jìn)行一次重構(gòu)，具有較高的可靠度。本文定義軌跡覆蓋率，以衡量卡口設(shè)備對(duì)車輛軌跡檢測(cè)的完整性。假設(shè)某OD 量為XOD，其間有多條可行路徑POD={p1p2…pi…}，流量占比為FOD=[f1f2…fi… ] ，單條可行路徑的軌跡覆蓋率為一次重構(gòu)后的局部檢測(cè)軌跡權(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ù)對(duì)路段關(guān)鍵程度進(jìn)行量化，軌跡權(quán)值即軌跡途徑路段關(guān)鍵程度之和。基于此，OD 間所有軌跡的平均覆蓋率為

整個(gè)路網(wǎng)所有OD對(duì)之間的軌跡覆蓋率均值

其中sum表示路網(wǎng)中OD對(duì)數(shù)量。

2.3 缺失軌跡離散度優(yōu)化

基于缺失軌跡二次重構(gòu)的原理，用缺失軌跡離散度衡量二次重構(gòu)的可靠性。對(duì)于確切軌跡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）依次對(duì)卡口數(shù)量、監(jiān)測(cè)流量、覆蓋軌跡進(jìn)行了約束，從而保證一定程度的軌跡監(jiān)測(cè)；在此基礎(chǔ)上對(duì)缺失軌跡離散度進(jìn)行優(yōu)化，實(shí)現(xiàn)了更有效可靠的軌跡重構(gòu)與檢測(cè)。

3 求解算法

考慮到實(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

4 算例分析

4.1 案例路網(wǎng)

以廣州市海珠區(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è)交通檢測(cè)卡口，包括7 個(gè)轉(zhuǎn)向檢測(cè)卡口和10 個(gè)路段檢測(cè)卡口；遵循經(jīng)驗(yàn)，其布設(shè)主要分布于外圍主干路，缺少對(duì)次干路、支路的軌跡檢測(cè)（圖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è)下的檢測(cè)軌跡與缺失軌跡Fig.4 The monitored trajectory and missing trajectory at present

4.2 無基礎(chǔ)卡口的全新布設(shè)

將案例路網(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 所示，對(duì)路網(wǎng)的檢測(cè)情況如圖6 所示。結(jié)果表明，與當(dāng)前布設(shè)相比，優(yōu)化方案更多地兼顧了次干路、支路級(jí)布設(shè)規(guī)模，提升了卡口設(shè)備檢測(cè)細(xì)粒度。路網(wǎng)整體指標(biāo)如表2所示。對(duì)比路網(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)化方案在軌跡檢測(cè)方面均表現(xiàn)出更優(yōu)的效果。

表2 路網(wǎng)整體指標(biāo)對(duì)比Table 2 Comparison of overall road network indicators

圖5 卡口布設(shè)優(yōu)化結(jié)果Fig.5 Bayonet layout optimization results

圖6 優(yōu)化布設(shè)下的檢測(cè)軌跡與缺失軌跡Fig.6 The monitored trajectory and missing trajectory after optimizition

在廣州市2021年8月29日的車輛GPS數(shù)據(jù)中，隨機(jī)選取研究區(qū)域內(nèi)的100條車輛出行軌跡，對(duì)比優(yōu)化前后卡口布設(shè)方案的軌跡覆蓋率（見圖7 和表3）、軌跡重構(gòu)準(zhǔn)確率情況（見圖8 和表4）。結(jié)果表明，優(yōu)化方案在加強(qiáng)軌跡檢測(cè)和車輛個(gè)體出行軌跡重構(gòu)方面取得了更優(yōu)的效果。同時(shí)，受限于卡口設(shè)備數(shù)量，仍有個(gè)別軌跡檢測(cè)率和軌跡重構(gòu)準(zhǔn)確率較低，需通過增加卡口數(shù)量進(jìn)一步完善。

表3 隨機(jī)100條軌跡的軌跡覆蓋率區(qū)間對(duì)比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

4.3 有基礎(chǔ)卡口的新增布設(shè)

以當(dāng)前卡口布設(shè)為基礎(chǔ)（即Q0、P0已知），新增卡口以實(shí)現(xiàn)最優(yōu)檢測(cè)目標(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

5 結(jié) 論

針對(duì)有向路網(wǎng)，從軌跡重構(gòu)效果最優(yōu)角度出發(fā)，本文面向車輛個(gè)體出行檢測(cè)任務(wù)構(gòu)建了卡口布設(shè)優(yōu)化模型。并以廣州市海珠區(qū)某局部路網(wǎng)為例，對(duì)全新布設(shè)和新增布設(shè)兩類應(yīng)用場(chǎng)景進(jìn)行了算例分析，結(jié)果表明：在全新布設(shè)下，優(yōu)化布設(shè)方案比當(dāng)前方案的流量捕獲率提高了6.20%、軌跡覆蓋率提高了2.76%、缺失軌跡離散度提高了139%，能夠有效提升軌跡檢測(cè)力度和軌跡重構(gòu)可靠性，在車輛個(gè)體出行檢測(cè)任務(wù)中發(fā)揮更好的效益。在新增布設(shè)下，分別對(duì)新增1-6個(gè)卡口進(jìn)行求解，得到了新增位置及最優(yōu)解。在未來，還可以拓展模型的應(yīng)用場(chǎng)景，調(diào)用不同的指標(biāo)，制定可兼容多功能的卡口布設(shè)優(yōu)化方案，以達(dá)到更佳的布設(shè)效果?；蛘邔⒖谂c其他檢測(cè)器相結(jié)合，考慮多種類檢測(cè)器的布設(shè)優(yōu)化。