面向車輛個體出行檢測的卡口布設優化模型

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

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

2.廣東省智能交通系統重點實驗室，廣東 深圳 518107

3.廣東省交通環境智能監測與治理工程技術研究中心，廣東 深圳 518107

4.廣東工貿職業技術學院，廣東 廣州 510510

城市交通大腦旨在利用實時全量的交通數據全局優化城市交通資源，實現城市運轉效能的根本提升（謝一明，2022）。在車輛個體身份感知方面，相比于其他傳統的交通傳感器，交通卡口能夠結合圖像處理技術，實現細粒度更高的車輛識別，但受成本等因素限制很難實現路網全覆蓋，需要制定科學合理的選址方案，以滿足檢測需求。

大量學者對傳統檢測器的布設進行了優化。何勝學等（2016）提出了一種圖論算法，以流量檢測為目標優化定量線圈的布局。Hu et al.（2009）提出了一種基于路段來表示路網結構的方法，通過檢測器布設能夠在穩態條件下準確估計所有鏈路流量。Xu et al.（2016）和Salari et al.（2019）引入檢測器故障或其他不確定因素，通過最小化先驗路徑流量不確定性，優化檢測器布設。Yang et al.（1991）首次提出“最大可能相對誤差”的概念，利用檢測數據分析估計OD 矩陣的可信度。劉明等（1993）對該方法做了進一步研究。楊曉光等（2011）依據不同的OD 矩陣估計模型進行布點優化。Hao et al.（2022）利用協方差衡量不同時期OD需求的相關性，通過最小化OD 需求估計的不確定性來優化多類型交通檢測器的布設。Kim et al.（2011）基于微觀交通仿真，研究檢測器布設位置對旅行時間估計的影響。Danczy et al.（Danczy et al.，2011;Danczy et al.，2016）通過最小化旅行時間估算誤差來優化交通檢測器布設方案。Jenelius et al.（2018）研究了在城市路網背景下，利用AⅤⅠ檢測器、浮動車等移動檢測器對旅行時間進行檢測估計。

近年來，也有部分學者研究了視頻監控點的選點規劃。劉暢（2015）提出“全范圍無盲區，交互構成封閉”的攝像機布設原則，以實現流量出入監測和重點區域監測等目的。逯峰等（2016）使用機器學習挖掘卡口布設與時空要素的關系，針對未來的路網空間進行了卡口布設優化。2017 年，He et al.（2018）首次在車輛交通和攝像頭位置之間建立聯系，以實現更好的安全監控。沈凌等（2021）針對橋梁覆蓋率、重要場所出入口覆蓋率和關鍵性節點覆蓋率等指標，研究了城市道路監控設備布設方案評價方法。

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

1 問題描述

本文以有向路網為研究對象，如圖1所示。在當前卡口布設下，車輛veh1和veh2均存在軌跡缺失。面向個體出行檢測優化卡口布設，就是要在卡口數量約束下布設卡口實現車輛軌跡重構可靠度最高。首先，對基本信息和相關概念做出闡述。文中所涉及的符號及其含義如表1所示。

表1 符號及含義Table 1 Symbols and Meanings

圖1 示例路網Fig.1 Road network example

1.1 卡口分類

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

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

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

1.2 基于卡口檢測序列的軌跡重構

1.2.1 可行路徑集考慮到經濟、省時等因素，大多數司機在兩點間出行時，往往優先選擇距離最短路徑或較短路徑，此類路徑稱為可行路徑?？尚新窂蕉x為：在有向路網G=(V，E)中，規定起點F的最短路權為L(F) = 0，其他節點設為∞，遍歷相鄰節點，參照Dijkstra 算法，利用路段長度標記每個節點的最短路權L.設有路徑rF，T=(… -- …)，只要滿足其中任一路段∈E，均有L(i) =L(j)，則定義rF，T為由起點F到訖點T的一條可行路徑（鄒志云，1997）。任意兩點間的所有可行路徑即構成了兩點間的可行路徑集。

1.2.2 缺失軌跡重構原理基于車輛個體的單次出行卡口檢測序列，將車輛每次出行時空軌跡通過卡口設備和路網關聯關系映射到路網，可以得到卡口檢測下的部分出行軌跡。進一步，對缺失部分進行重構，根據相鄰兩次卡口檢測序列間的缺失情況，將其分為兩種情況：（1）缺失部分只含一條可行路徑；（2）缺失部分含多條可行路徑。對于情況（1），可以利用唯一的可行路徑直接補全缺失部分，定義為一次重構。對于情況（2），則需要在多條可行路徑中確定一條最優軌跡，作為重構軌跡，定義為二次重構。在現階段的研究中，不少學者利用卡口檢測數據進行軌跡重構，主要方法包括：不基于交通流模型的方法、基于交通流模型的方法、混合模型方法（邢皓等，2019）。其中，不基于交通流模型的方法忽略擁堵和排隊等交通動態模式，只利用時間、速度等數值計算方法對缺失的軌跡進行重構。在進行軌跡點還原的過程中，通常會針對兩條確切軌跡之間軌跡缺失的部分，確定一組備選軌跡集。然后，引入路段數量、轉彎次數、理論速度等決策屬性，計算各備選方案與最優方案的接近程度，最終選取最接近的備選軌跡作為最優軌跡（楊帥等，2016）。

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

對初始決策矩陣進行標準化，得到標準化決策矩陣

設置權重向量

對屬性值賦權，備選軌跡加權屬性值為

根據卡口序列記錄的實際過車時間，計算理論軌跡屬性值，最接近的備選軌跡即為最優軌跡。因此，基于本文提出的缺失軌跡一次重構和二次重構原理，能夠創建相應指標以構建優化模型。

2 優化模型構建

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

2.1 流量捕獲率約束

基于卡口布設矩陣和路段流量矩陣計算流量捕獲率大小，即卡口可覆蓋的流量占路網總流量的比例，以衡量卡口對于路網在途車輛的檢測情況。即

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

即當路段布設至少一個卡口時，該路段流量可被捕獲，否則不被捕獲。

2.2 軌跡覆蓋率約束

對軌跡缺失部分進行一次重構，具有較高的可靠度。本文定義軌跡覆蓋率，以衡量卡口設備對車輛軌跡檢測的完整性。假設某OD 量為XOD，其間有多條可行路徑POD={p1p2…pi…}，流量占比為FOD=[f1f2…fi… ] ，單條可行路徑的軌跡覆蓋率為一次重構后的局部檢測軌跡權值占完整軌跡權值的比率ci， 記COD=[c1c2…ci… ].參考MⅠⅠACR 法（Feng et al.，2019），本文基于靜態拓撲結構和動態GPS 數據對路段關鍵程度進行量化，軌跡權值即軌跡途徑路段關鍵程度之和?；诖?，OD 間所有軌跡的平均覆蓋率為

整個路網所有OD對之間的軌跡覆蓋率均值

其中sum表示路網中OD對數量。

2.3 缺失軌跡離散度優化

基于缺失軌跡二次重構的原理，用缺失軌跡離散度衡量二次重構的可靠性。對于確切軌跡A、B 間備選軌跡的加權屬性值SAB=?！T=[sAB1sAB2…sABm]T，用方差衡量備選軌跡集MPAB的離散度。有

面向出行軌跡重構最優，本文以最大化路網缺失軌跡離散度SD為優化目標，優化模型如下：

其中ΔQ、ΔP表示新增布設矩陣。式（12）-（14）依次對卡口數量、監測流量、覆蓋軌跡進行了約束，從而保證一定程度的軌跡監測；在此基礎上對缺失軌跡離散度進行優化，實現了更有效可靠的軌跡重構與檢測。

3 求解算法

考慮到實際路網的規模大小，優化模型的求解為NP-hard 問題，難以采用傳統的精確算法進行求解。因此，本文采用粒子群算法（PSO，particle swarm optimization）求解模型近似最優解。PSO算法通過群體中個體之間的協作和信息共享來尋找最優解，具體流程如圖2所示。

圖2 粒子群算法流程圖Fig.2 Flow chart of particle swarm optimization

4 算例分析

4.1 案例路網

以廣州市海珠區某局部區域路網為例，路網拓撲見圖3。過濾孤立點、孤立路段等要素，經過預處理后的路網共有44 個節點，124 條有向路段，當前已布設17 個交通檢測卡口，包括7 個轉向檢測卡口和10 個路段檢測卡口；遵循經驗，其布設主要分布于外圍主干路，缺少對次干路、支路的軌跡檢測（圖4）。在當前實際卡口布設方案下，整體路網的流量捕獲率為12.89%，軌跡覆蓋率為74.00%，缺失軌跡離散度為0.036。

圖3 研究區域局部路網Fig.3 Local road network in the study area

圖4 當前布設下的檢測軌跡與缺失軌跡Fig.4 The monitored trajectory and missing trajectory at present

4.2 無基礎卡口的全新布設

將案例路網看作無基礎卡口的全新路網，采用PSO 算法求解優化模型。以當前布設方案相關指標為閾值，設置模型參數Nmax= 17，Vmin= 12%，COVmin= 70%，T= 500，求解得到的卡口布設優化方案如圖5 所示，對路網的檢測情況如圖6 所示。結果表明，與當前布設相比，優化方案更多地兼顧了次干路、支路級布設規模，提升了卡口設備檢測細粒度。路網整體指標如表2所示。對比路網整體指標，可以發現：優化方案整體路網流量捕獲率為19.09%，軌跡覆蓋率為76.76%，缺失軌跡離散度為0.086。與當前實際布設方案相比，優化方案在流量捕獲率方面提升了6.20%，軌跡覆蓋率提升了2.76%，缺失軌跡離散度提升了139%。與傳統的兩類布設方案相比，優化方案在軌跡檢測方面均表現出更優的效果。

表2 路網整體指標對比Table 2 Comparison of overall road network indicators

圖5 卡口布設優化結果Fig.5 Bayonet layout optimization results

圖6 優化布設下的檢測軌跡與缺失軌跡Fig.6 The monitored trajectory and missing trajectory after optimizition

在廣州市2021年8月29日的車輛GPS數據中，隨機選取研究區域內的100條車輛出行軌跡，對比優化前后卡口布設方案的軌跡覆蓋率（見圖7 和表3）、軌跡重構準確率情況（見圖8 和表4）。結果表明，優化方案在加強軌跡檢測和車輛個體出行軌跡重構方面取得了更優的效果。同時，受限于卡口設備數量，仍有個別軌跡檢測率和軌跡重構準確率較低，需通過增加卡口數量進一步完善。

表3 隨機100條軌跡的軌跡覆蓋率區間對比Table 3 Comparison of track coverage interval of 100 random tracks

表4 隨機100條軌跡的軌跡重構準確率區間Table 4 Accuracy intervals of track reconstruction for 100 random tracks

圖7 隨機100條軌跡的軌跡覆蓋率Fig.7 Track coverage of 100 random tracks

圖8 隨機100條軌跡的軌跡重構準確率Fig.8 Track reconstruction accuracy of random 100 tracks

4.3 有基礎卡口的新增布設

以當前卡口布設為基礎（即Q0、P0已知），新增卡口以實現最優檢測目標。模型約束條件同上，Vmin= 12%，COVmin= 70%，以缺失軌跡離散度為優化目標，依次新增1-6個卡口進行模型求解。新增5 個卡口的位置和新增卡口布設優化結果如圖9和表5 所示。結果表明：隨著新增卡口數量的增多，各指標均表現出上升狀態。以N= 5 為例，在江南大道、紫丹大街、寶業路、懷德大道新增路口卡口，在紫金大街新增路段卡口，可以獲得最優的效果，相應位置如圖9 所示。在此新增方案下，流量捕獲率為16.07%，軌跡覆蓋率為74.91%，缺失軌跡離散度達到0.12。

表5 新增卡口布設優化結果Table 5 Added bayonet layout optimization results

圖9 新增5個卡口位置示意圖Fig.9 Position of five bayonets added

5 結 論

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