基于電子收費數據的車輛軌跡匹配

康愛忠， 李玉， 韓文淵， 傅馨嶠， 趙建東*

(1.中電建冀交高速公路投資發展有限公司， 石家莊 050000； 2.北京交通大學交通運輸學院， 北京 100044)

隨著高速公路撤銷省界收費站，采取電子收費(electronic toll collection，ETC)收費趨勢的發展，高速公路布設了大量的ETC門架系統，并將門架采集的數據為高速公路運營管理提供支撐[1]。門架可能存在讀寫數據有缺失或者錯誤的現象，導致車輛行駛經過的ETC門架信息的數據不完全，出現車輛路徑的缺失。此時，需對有部分缺失的信息進行路徑提取和擬合，實現車輛完整路徑的獲取，從而對車輛全程進行計算收費。

多義性路徑識別即通過特定的識別系統將車輛的行駛路徑匹配到實際地圖上，并按照識別后的路徑作為收取費用的依據。基于無線射頻識別(radio frequency identification，RFID)技術的多義性路徑識別系統，通過安裝路邊識別設備，更換多義性路徑識別卡，能夠準確識別路網中每輛車輛在自由流狀態下的實際行駛路徑。施俊靚[2]從多義性路徑識別系統的構成切入，分析云計算虛擬化技術的應用，提出了利用云計算虛擬化的技術解決系統建設中現存的多路徑識別漏洞問題，為路徑識別系統的完善過程提供基礎。目前，中國主要應用的多義性路徑識別解決方案是基于5.8 G的多義性路徑識別技術和基于433 MHz的多義性路徑識別技術設計的。吳海東等[3]主要從輻射覆蓋范圍，無差別標識技術等方面對5.8 G路徑標識基站的關鍵性技術進行了詳細的分析。許永存等[4]分析了5.8 G射頻識別技術原理及其應用特點，以及路徑識別系統的主要設備和標識思路，提出了5.8 G統一多路徑識別系統的應用方案。在設計算法求得車輛完整路徑方面，Amith等[5]提出了一種新的戶外環境導航算法，允許機器人沿著規劃的路徑從一個靜態節點移動到另一個節點。在具有多個路徑的混合道路網絡中進行路徑規劃，利用機器人在配置好的地圖上完成導航，證明了駕駛員輔助系統的有效性。易小泉[6]運用Floyd算法結合真實的路網進行抽象處理，通過繪制有向圖并構建二維矩陣，從而規劃出租車通行的最優路徑，并綜合了路網擁堵程度、乘客緊急程度、出租車需求量、天氣環境等多方面因素，實現合理規劃。

通過相關文獻及其研究成果可以看出，目前針對路徑還原的所需信息和可用信息以及高速公路收費系統和監控系統的信息采集和應用，還沒有規范和標準；現有的許多路徑識別系統、收費系統和監控系統都沒有經過長時間的驗證并大規模應用，在路徑擬合的速度和準確性等方面還存在問題。

綜上，完善和提升多義性路徑識別系統的精確度對高速公路的運行收費管理的重要性日益突出。現對河北省高速公路從南宮收費站至新元收費站的車輛行駛ETC門架數據進行分析和預處理，使用Floyd 算法得到車輛行駛的完整路徑，完成多場景下車輛軌跡的地圖匹配，以實現車輛完整路徑的計費。

1 路徑匹配系統需求分析

1.1 河北省ETC聯網收費系統

河北省取消省級高速公路收費站也是對原有收費制度的改革。取消原有省界公路主要的收費設施，在省界附近設立虛擬收費站。同時，在高速公路沿線路段設置了ETC門架系統。高速公路收費系統主要由架構系統、業務類系統、數據處理系統等組成。其中架構系統主要有清算費用中心系統、ETC門架系統、ETC車道、MTC車道、ETC/MTC車道組成的收費系統等；業務類系統主要有信息上傳系統、監測控制系統、客服服務系統、安全控制系統等；數據處理系統主要有車輛交易數據處理系統、車輛核查數據系統、車輛牌照數據識別系統等[7]。

1.2 ETC門架系統

設置ETC門架系統的原則如下。

(1)在高速公路主線位置上、高速公路出入口互通處設ETC門架。

(2)ETC門架應設置在視野范圍好的區域，防止被遮擋。高速公路到門架的直線距離應大于50 m。

(3)ETC門架設備容易被相同頻率設備的電磁波干擾，因此不應將5.8 GHz的設備設置在ETC門架附近，避免對門架產生干擾。

(4)相鄰門架之間距離不應小于30 m，且距離不能太遠。

(5)ETC門架的高不應小于6 m。安裝有車牌識別系統的門架應在頂部安裝[8]。

ETC門架系統主要由以下設備組成：車道控制器、RSU、車牌圖像識別設備、高清攝像機、通信設備、供電設備、交換機、網絡安全設備、站級服務器、防雷接地設施、補光燈等。ETC門架系統由上、下行雙方向部分組成[9]。

1.2.1 省界ETC 門架系統

設置在省界上的ETC門架系統有上下兩個方向。每個門架都配有冗余設置的關鍵設備。當主設備發生故障時，應立即啟動備用設備。省界ETC 門架系統如圖1所示[10]。

1.2.2 路段ETC門架系統

設置在非省界上的ETC門架系統有上下兩個方向。每個門架都配有冗余設置的關鍵設備。當主設備發生故障時，應立即啟動備用設備。路段ETC門架系統如圖2所示[10]。

圖2 路段ETC門架布局Fig.2 Layout of the ETC door frame at road section

2 收費系統數據處理

2.1 收費數據特征

高速公路收費系統數據特點主要集中在數據量大、格式復雜和數據冗余較大3個方面。基于河北省高速公路從南宮收費站至新元收費站的車輛行駛ETC門架數據，在分析數據特征后，提取與本研究相關的字段信息，包括車型、交易時間、途徑門架名稱、門架編號、車牌號。

2.2 數據預處理

數據處理的過程主要包括數據清洗和聚集。重復扣費、超時等情況需要進行數據的清洗；根據ETC系統對車牌識別采集到的信息進行聚集。進行數據的預處理，首先需要處理異常數據[11]。在對河北高速公路收費數據進行分析與研究后，確定異常數據類型分別是冗余數據、缺失數據、噪聲數據。

2.2.1 冗余數據

同一車輛同一時間的數據應是唯一的，由于采集或保存過程發生錯誤導致出現多條數據相同的信息，即為冗余數據。

2.2.2 缺失數據

數據缺失現象主要是記錄中出入口站編號、出入口站日期/時間、車型、車種、軸數等字段缺失。與冗余現象產生的情況相類似，可能因為相關設備出現故障、信號傳輸中斷或倒卡逃費行為。當缺失數據不易被系統監測到時，可能會導致大量數據缺失，沒有被系統記錄到[12]。

2.2.3 噪聲數據

高速公路收費數據中噪聲數據通常指不符合常理的損壞的數據，如入口站時間晚于出口站日期/時間、出入站時間不在數據調取的范圍內、出入站編號有誤[13]，即無法對應實際收費站、出入站編號相同，即車輛從同一收費站進出、車型、車種無法識別，即顯示為“0”。其中出入站相同情況可能為換卡逃費或逃費行為以及系統內部錯誤。噪聲數據通常被認為是會影響研究結果的沒有意義的數據。由于系統故障或程序混亂會造成數據的產生。

故需針對以上異常數據做刪除處理。

3 路徑匹配算法研究

3.1 路徑匹配的原則

在所給數據中篩選出一輛車所經過的門架信息數據，并將路徑情況分為經過門架信息數據完整和經過門架信息數據缺失，其中經過門架信息缺失又分為在叉路口處缺失和不在岔路口處缺失。由于實際車輛行駛過程中，基本上所有的車主都會選擇距離最短的路線，從經濟方面考慮，既能節省通行時間，也能減少油費以及過路費等。因此當途經門架數據缺失，即路徑不連續、不能拼接時，便按照兩點間的最短距離所反映的路徑作為車輛路徑匹配的處理。

3.2 最優路徑算法選擇

在路徑還原的應用中，常用的最優路徑選擇算法有Floyd算法、Dijkstra算法、逐次逼近算法。Dijkstra算法和逐次逼近算法雖然能得出最短路徑的最優解，但由于計算時遍歷的節點較多，效率較低，因此選取Floyd算法來尋找最優路徑。

3.2.1 Floyd算法

Floyd算法又稱插點法，是一種基于動態規劃思想的最短路徑算法。可以求解網絡中任意兩個節點之間的最短路徑。最短路徑的標記方法也各不相同，通常標記的最短路徑需要反向查找[14]。為加速求解最短路徑過程中的迭代。

給定圖G及其邊(i，j)的權wij(1≤i≤n；1≤j≤n)。

步驟1初始化距離矩陣W(0)和路由矩陣R(0)。

(1)

(2)

步驟2已求得W(k-1)和R(k-1)，依據下面的迭代求W(k)和R(k)。

(3)

(4)

步驟3若k≤n，重復步驟2；若k>n，終止。

3.2.2 Floyd加速算法

步驟1初始化距離矩陣W(0)和路由矩陣R(0)。

(5)

(6)

(7)

步驟3若W(k+1=W(k))迭代終止；否則返回步驟2。Floyd算法流程如圖3所示。

圖3 Floyd算法流程Fig.3 Flow chart of Floyd

3.2.3 Floyd算法的應用

Floyd算法的核心是利用局部最優解計算全局最優解，該算法可分為兩個階段:尋找最短路徑長度，記錄尋找路徑長度的路徑，即可以得到還原后的路徑[16]。

3.3 路徑匹配情況分類

3.3.1 經過門架信息數據完整

根據ETC門架數據，選取一輛車經過的路徑，并在程序中輸入該車輛經過的門架編號：path=[1,2,3,4,5,6,7,8,9,18]。程序運行后，輸出結果為[1,2,3,4,5,6,7,8,9,18]，即車輛路徑經過的門架編號依次為1,2,3,4,5,6,7,8,9,18。最后將結果得到的門架編號匹配到地圖上，可以看出程序輸出結果中的門架就是車輛實際路程經過的門架，由此完成了數據完整情況下車輛軌跡匹配，如圖4所示。

圖4 門架信息完整時車輛軌跡匹配結果Fig.4 Vehicle trajectory matching results when door frame information is complete

3.3.2 經過門架信息數據缺失

1)數據不在互通處缺失

根據ETC門架數據，選取一輛車路徑信息并輸入其經過的門架編號：path=[1,10,11,14,15,16,9,18]。將該車經過的門架匹配到地圖上，如圖5所示。初步斷定編號為12、13的門架數據為缺失數據，在圖5中用黑色門架符號標出。12號和13號為數據缺失門架，兩門架在同一路段上，不在路段互通處，此種情況歸類為數據不在互通處缺失的情況。

圖5 門架數據缺失時車輛軌跡的地圖匹配Fig.5 Map matching of vehicle tracks when missing door frame data

程序運行后，輸出結果為[1,10,11,12,13,14,15,16,9,18]，即車輛路徑經過的門架編號依次為1,10,11,12,13,14,15,16,9,18。將結果得到的門架編號匹配到地圖上，如圖6所示，程序輸出結果中的門架就是車輛實際路程經過的門架，即圖6中紅色門架所在的路徑為車輛行駛軌跡地圖匹配后的路徑。編號為12、13的門架為數據缺失的門架，此時完成了數據不在互通前后缺失時的情況下車輛軌跡匹配。

圖6 門架數據缺失時車輛軌跡的地圖匹配Fig.6 Matching results of vehicle tracks when door information is not at interoperability

2)數據在路段互通處缺失

當兩個門架不在同一路段內時，而且數據在兩個路段之間缺失，將此種情況歸類為數據在路段互通處缺失，具體解釋如下。

如圖7所示，設車輛從RA門架行駛到RD門架，路段1的出口門架為C1、C2；路段2的入口門架為R1、R2；RA至路段出口的直達路徑為RA-C1、RA-C2；路段2的入口至RD有2條路徑R1-RD、R2-RD；C1、C2至R1、R2有4條直達路徑信息：C1-R1、C1-R2、C2-R1、C2-R2。

計算過程如下：①查詢信息表，獲取RA門架的路段為 L1，RD門架的路段為 L2；②查詢路段節點表，獲取路段L1的出口門架分別為C1、C2，路段L2的入口門架為R1、R2；③查詢路段L1的直達路徑信息表，獲取L1至路段出口的直達路徑RA-C1、RA-C2；④查詢路段L2的直達路徑信息表，獲取路段入口至RD的直達路徑為R1-MD，R2-MD；⑤查詢路段間直達路徑表，獲取C1、C2 至 R1、R2的直達路徑信息C1-R1，C1-R2，C2-R1，C2-R2；⑥將3個結果組合，獲得4個直達路徑RA-C1-R1-RD、RA-C1-R2-RD、RA-C2-R1-RD、RA-C2-R2-RD；⑦選取擬合里程最少的路徑作為計費路徑。

圖7 簡易路徑圖Fig.7 Simple path map

根據ETC門架數據，選取一輛車經過的路徑，并根據路徑信息輸入經過的門架編號，為path= [1,3,9,18]。將該車經過的門架匹配到地圖上，中間途徑的門架數據為缺失數據，如圖8所示，用黑色門架符號標出數據缺失的門架。由于車輛從1號門架行駛到了3號門架及從3號門架行駛到了9號門架，中途路徑數據上不可知。從1號到3號門架中間有兩處互通，從3號到9號門架中間有兩處互通，因此將此種情況歸類為數據在互通處缺失的情況。

程序運行后，輸出結果為[1,2,3,4,5,6,7,8,9,18]，即車輛路徑經過的門架編號依次為1,2,3,4,5,6,7,8,9,18。將程序輸出結果得到的門架編號匹配到地圖上，程序輸出結果中的門架就是車輛實際行駛經過的門架，如圖9所示，紅色門架所在的路徑為車輛行駛軌跡地圖匹配后的路徑。編號為2,4,5,6,7,8的門架為數據缺失的門架，此時完成了數據在互通前后缺失時的情況下車輛軌跡匹配。

3)大量數據缺失

根據ETC門架數據，選取一輛車經過的路徑，并根據路徑信息輸入經過的門架編號：path=[1, 18]。并將該車經過的門架匹配到地圖上，此時只知道其起點和終點經過的門架，中間的門架數據缺失，并不知道這輛車走了哪條路徑。如圖10所示，數據缺失門架在下圖中用黑色的門架符號標出。中間路徑有四處互通處，并不知道車輛在互通處的行駛情況，因此歸類為大量數據缺失。此時出現了多義性路徑問題，需要進行車輛軌跡的識別。

圖8 門架數據在互通前后缺失時車輛軌跡的地圖匹配Fig.8 Map matching of vehicle tracks when gate data is missing before and after interoperability

程序運行后，輸出結果為[1,2,11,12,13,14,15,16,9,18]，即車輛路徑經過的門架編號依次為1,2,11,12,13,14,15,16,9,18。將程序輸出結果得到的門架編號匹配到地圖上，程序輸出結果中的門架就是車輛實際行駛經過的門架，如圖11所示，紅色門架所在的路徑為車輛行駛軌跡地圖匹配后的路徑。編號為2，11，12，13，14，15，16，9的門架為數據缺失的門架；編號為3，4，5，6，7，8，10，14，15，17為不經過的門架，即圖11中標示出的黑色門架。此時完成了數據在大量缺失的情況下車輛的軌跡匹配，由此得出了多義性路徑問題下車輛經過的門架結果。

圖9 車輛軌跡匹配結果Fig.9 Vehicle trajectory matching results

圖10 門架信息大量缺失Fig.10 Lack of information on door frames

圖11 門架信息大量缺失時車輛軌跡匹配結果Fig.11 Vehicle track matching results when a lot of door information is missing

4 結論

(1)通過獲取到的ETC門架數據發現，數據內部通常具有缺失數據、冗余數據、噪聲數據等需要進行預處理的異常數據。因此未來可以提高交通數據獲取的精度，異常數據減少，那么路徑匹配識別會更加精確，車輛計費也會更加精準。

(2)在大數據智能化的背景下，采集交通信息的智能化水平也在不斷上升，因此得到的交通數據種類也愈來愈多。由于各類交通檢測器的檢測原理以及放置位置的多樣性，檢測的條件并不一致，得到的交通數據也呈現出多源化。

(3)目前雖然已經初步實現了根據已有的ETC數據進行車輛完整路徑的匹配，但考慮的不是特別全面。如果能將多源數據結合起來實現車輛軌跡的匹配識別，在識別多義性車輛路徑時，通過收費系統、監控系統等多種系統的數據進行融合，綜合分析處理數據，可以得到更全面、互補的信息，那么可以大大地提高路徑匹配的準確性。

(4)未來也可以在以下幾方面進行研究：研究電子車牌識別等多種識別模式的使用情境，并如何廣泛應用；利用地理信息系統建立路網綜合的信息系統，達到高效收費運營管理的目的；利用ETC門架測速，提高高速公路行駛的安全性。