基于電子收費(fèi)數(shù)據(jù)的車輛軌跡匹配

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

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

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

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

通過相關(guān)文獻(xiàn)及其研究成果可以看出，目前針對路徑還原的所需信息和可用信息以及高速公路收費(fèi)系統(tǒng)和監(jiān)控系統(tǒng)的信息采集和應(yīng)用，還沒有規(guī)范和標(biāo)準(zhǔn)；現(xiàn)有的許多路徑識別系統(tǒng)、收費(fèi)系統(tǒng)和監(jiān)控系統(tǒng)都沒有經(jīng)過長時間的驗(yàn)證并大規(guī)模應(yīng)用，在路徑擬合的速度和準(zhǔn)確性等方面還存在問題。

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

1 路徑匹配系統(tǒng)需求分析

1.1 河北省ETC聯(lián)網(wǎng)收費(fèi)系統(tǒng)

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

1.2 ETC門架系統(tǒng)

設(shè)置ETC門架系統(tǒng)的原則如下。

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

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

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

(4)相鄰門架之間距離不應(yīng)小于30 m，且距離不能太遠(yuǎn)。

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

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

1.2.1 省界ETC 門架系統(tǒng)

設(shè)置在省界上的ETC門架系統(tǒng)有上下兩個方向。每個門架都配有冗余設(shè)置的關(guān)鍵設(shè)備。當(dāng)主設(shè)備發(fā)生故障時，應(yīng)立即啟動備用設(shè)備。省界ETC 門架系統(tǒng)如圖1所示[10]。

1.2.2 路段ETC門架系統(tǒng)

設(shè)置在非省界上的ETC門架系統(tǒng)有上下兩個方向。每個門架都配有冗余設(shè)置的關(guān)鍵設(shè)備。當(dāng)主設(shè)備發(fā)生故障時，應(yīng)立即啟動備用設(shè)備。路段ETC門架系統(tǒng)如圖2所示[10]。

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

2 收費(fèi)系統(tǒng)數(shù)據(jù)處理

2.1 收費(fèi)數(shù)據(jù)特征

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

2.2 數(shù)據(jù)預(yù)處理

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

2.2.1 冗余數(shù)據(jù)

同一車輛同一時間的數(shù)據(jù)應(yīng)是唯一的，由于采集或保存過程發(fā)生錯誤導(dǎo)致出現(xiàn)多條數(shù)據(jù)相同的信息，即為冗余數(shù)據(jù)。

2.2.2 缺失數(shù)據(jù)

數(shù)據(jù)缺失現(xiàn)象主要是記錄中出入口站編號、出入口站日期/時間、車型、車種、軸數(shù)等字段缺失。與冗余現(xiàn)象產(chǎn)生的情況相類似，可能因?yàn)橄嚓P(guān)設(shè)備出現(xiàn)故障、信號傳輸中斷或倒卡逃費(fèi)行為。當(dāng)缺失數(shù)據(jù)不易被系統(tǒng)監(jiān)測到時，可能會導(dǎo)致大量數(shù)據(jù)缺失，沒有被系統(tǒng)記錄到[12]。

2.2.3 噪聲數(shù)據(jù)

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

故需針對以上異常數(shù)據(jù)做刪除處理。

3 路徑匹配算法研究

3.1 路徑匹配的原則

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

3.2 最優(yōu)路徑算法選擇

在路徑還原的應(yīng)用中，常用的最優(yōu)路徑選擇算法有Floyd算法、Dijkstra算法、逐次逼近算法。Dijkstra算法和逐次逼近算法雖然能得出最短路徑的最優(yōu)解，但由于計(jì)算時遍歷的節(jié)點(diǎn)較多，效率較低，因此選取Floyd算法來尋找最優(yōu)路徑。

3.2.1 Floyd算法

Floyd算法又稱插點(diǎn)法，是一種基于動態(tài)規(guī)劃思想的最短路徑算法。可以求解網(wǎng)絡(luò)中任意兩個節(jié)點(diǎn)之間的最短路徑。最短路徑的標(biāo)記方法也各不相同，通常標(biāo)記的最短路徑需要反向查找[14]。為加速求解最短路徑過程中的迭代。

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

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

(1)

(2)

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

(3)

(4)

步驟3若k≤n，重復(fù)步驟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算法的應(yīng)用

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

3.3 路徑匹配情況分類

3.3.1 經(jīng)過門架信息數(shù)據(jù)完整

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

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

3.3.2 經(jīng)過門架信息數(shù)據(jù)缺失

1)數(shù)據(jù)不在互通處缺失

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

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

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

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

2)數(shù)據(jù)在路段互通處缺失

當(dāng)兩個門架不在同一路段內(nèi)時，而且數(shù)據(jù)在兩個路段之間缺失，將此種情況歸類為數(shù)據(jù)在路段互通處缺失，具體解釋如下。

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

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

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

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

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

3)大量數(shù)據(jù)缺失

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

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

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

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

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

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

4 結(jié)論

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

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

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

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