【導(dǎo)讀】定該收費系統(tǒng)能否成功實現(xiàn)精確收費。本文概述了各種常用的地圖匹配算法，并就各。行定義，并提出了一種新的專門用于收費的地圖匹配算法。此算法被證實是具有可行

　　

【正文】 交 經(jīng)過點 2 5 馬站立交 經(jīng)過點 2 6 濟南北收費站入口 入口口關(guān)鍵點 0 7 濟南北收費站出口 出口關(guān)鍵關(guān)鍵點 1 1 11 9 8 2 6 青銀高速 5 沈海高速 4 青蘭高速 3 2 10 12 青島理工大學畢業(yè)設(shè)計（論文） 3 基于 GPS的不停車收費系統(tǒng)地圖匹配方法 27 8 匝道 經(jīng)過點 2 9 濟南北收費站 出口路段 1 10 管家樓收費站 入口路段 0 11 濟青高速 非收費路段 無 12 中間路段 中間路段 2 地圖精簡 收費的準確性取決于能否準確判斷出是否行駛在收費路段上，這就 要求收費電子地圖必須保持高的地圖精度。由于考慮到車載系統(tǒng)受成本限制，其硬件資源非常有限，因此要求在滿足收費功能要求的條件下盡量縮小 存儲地圖的數(shù)據(jù)量， 即車載設(shè)備只存儲必要的用于收費的基礎(chǔ)信息，大量的時效性數(shù)據(jù)的查詢和計算量較大的操作都放到后臺服務(wù)器上進行，因而需要對電子地圖數(shù)據(jù)進行裁剪，以便節(jié)省車載單元內(nèi)存資源，提高運行效率。同時其數(shù)據(jù)結(jié)構(gòu)也必須更加符合嵌入式設(shè)備顯示、運算和分析的要求。 地圖信息的精簡包括下面兩個方面： 電子地圖可通過精簡地圖數(shù)據(jù)進行壓縮，去除不必要的形狀連接點， 保留路段的拓撲結(jié)構(gòu)，這樣可大大的減少數(shù)據(jù)量，節(jié)省數(shù)據(jù)存儲空間和減少程序計算量。 電子地圖屬性信息的精簡就是首先確認收費地圖所必需的信息，去除不必要的其他信息。 收費系統(tǒng)中費率計算分 2 種情況，瘦客戶端計費和胖客戶端計費，瘦客戶端計費是將費率計算放在后臺完成，胖客戶端計費將費率計算前段完成，從而減少后臺的計算壓力， 2 種費率計算方式下，車載端存儲的信息也不一樣。瘦客戶端收費地圖保密與地圖匹配相關(guān)的數(shù)據(jù)信息包括：路段編號，路段做節(jié)點坐標，路段有節(jié)點坐標，路段類型。 胖客戶端收費地圖數(shù)據(jù) 的定義要考慮增加收費類型表和費率表，根據(jù)收費類型，查詢費率表內(nèi)相關(guān)費率，基本表包括：路段編號，路段名稱，路段長度，路段左節(jié)點坐標，路段右節(jié)點坐標，路段類型，收費類型。 基于 GPS 的不停車收費系統(tǒng)所用費率計算方式是瘦客戶端計費，車載設(shè)備只存儲青島理工大學畢業(yè)設(shè)計（論文） 3 基于 GPS的不停車收費系統(tǒng)地圖匹配方法 28 必要的用于收費的基礎(chǔ)信息，大量的時效性數(shù)據(jù)的查詢和計算量較大的操作都放到后臺服務(wù)器上進行，這樣可以減少車載設(shè)備成本并且可以減少程序計算量，提高效率。 基于 GPS 的不停車收費系統(tǒng)的地圖匹配方法 地圖匹配中搜索范圍的確定 在電子地圖的精度和 GPS 定位精度在目 前的技術(shù)水平下難以有較大提升的條件下，對匹配方法進行優(yōu)化是能否成功實現(xiàn)衛(wèi)星收費的關(guān)鍵環(huán)節(jié)。 以 GPS 定位點 G（ x,y）為中心，一個值為半徑的區(qū)域內(nèi)，在收費電子地圖上搜索是否有收費路段存在及收費路段在此范圍內(nèi)，如果有收費路段存在，則進行判斷。搜索范圍的選取非常重要，范圍過大，容易造成誤判，且加大計算量，如近距離平行的主輔路 ,使輔路行駛的車輛誤收費。如果搜索范圍過小，收費路段點丟失。 GPS 數(shù)據(jù)接收頻率 1 次 /秒，如果車速過快，搜索范圍會跳過路段上的一些節(jié)點，造成漏點。影響匹配準確性。本文采用根據(jù)車輛行駛速度動態(tài)收 本文采用根據(jù)車輛行駛速度動態(tài)調(diào)整搜索范圍的方法。搜索范圍的選取應(yīng)考慮以下兩個原則 : 1）搜索范圍和 GPS 定位精度及地圖精度有關(guān) ,搜尋范圍應(yīng)大于 GPS 定位精度和地圖精度的最大值。這樣才能保證所有節(jié)點都不會遺漏。 2）實際操作搜索范圍可根據(jù)車速在一定范圍內(nèi)自動調(diào)節(jié)。車輛在高速公路行駛的特點 ,快速 120km/h,而 GPS 定位數(shù)據(jù)以 1 次 /秒的頻率接收。為不遺漏對任何路段的節(jié)點進行判斷 ,在這種情況下 ,算法判斷節(jié)點范圍至少為 50m。高速公路雙向路段的橫向距離通常大大小于 50m。由此可見車速和判斷范圍的選取對地圖匹配的準 確性影響很大。隨車速增加 ,判斷范圍增大 ,車速減小 ,判斷范圍減小。這樣既保證在速度慢時匹配的精確 ,又使速度快時不遺漏節(jié)點。 搜索匹配范圍是車輛行駛時，以車輛 GPS 定位點為中心點，一個值為半徑的區(qū)域內(nèi)在收費電子地圖上搜索關(guān)鍵點進行匹配。搜索范圍的選取應(yīng)考慮到 GPS的精度誤差，道路寬度等因素。選取過大會造成誤判且加大計算量。另外，隨著車速的加快，車速每秒行駛的距離大于匹配范圍，跳過關(guān)鍵點，就會造成漏點。因此匹配范圍的選取和車速有一定的關(guān)系。本文提出了在保證基本匹配范圍的條件下，匹配范圍隨車輛行駛速度動態(tài)調(diào)整的方法 。匹配范圍分為兩個部分，基本值和變化值，實際搜索范圍為兩者之和。 （ 1）基本值的確定 青島理工大學畢業(yè)設(shè)計（論文） 3 基于 GPS的不停車收費系統(tǒng)地圖匹配方法 29 搜索范圍基本值的選取應(yīng)考慮以下兩個原則 :一是搜尋范圍應(yīng)大于 GPS 定位精度的最大誤差值，以保證在 GPS 存在誤差條件下不丟點 。二是搜索范圍必須完全覆蓋關(guān)鍵點所在道路同向所有車道。由此可知，基本的搜索范圍為 GPS 誤差值與關(guān)鍵點所在道路寬度之和。假如 GPS 定位誤差為 20m，道路為兩車道組成，每車道 ，路側(cè)間隙為各為 ，則搜索范圍為： alnmsc o p ese a c h ????? 2_ （ 31） 其中 m 表示 GPS 定位誤差， n 表示車道數(shù)， l 表示車道寬度， a表示路側(cè)間隙 以濟青高速公路為例，假設(shè) GPS 的定位誤差為 18，該高速公路為雙向四車道，路寬 ，路側(cè)間隙為 則 search_scope=18+4 +2 = （ 2）動態(tài)搜索匹配范圍值的確定 搜索范圍可根據(jù)車速在一定范圍內(nèi)自動調(diào)節(jié)。經(jīng)過反復(fù)測試，車輛在 36km/h 速度下，搜索基本值能夠滿足匹配要求 。在車速高于 36km/h，搜索范圍需要動態(tài)隨車速的變化。搜索范圍變化值具體 描述如下 :令初始搜索范圍基本值 :search_scope=35m，實際搜索變化值為 bound。 當速度 V＜ 36km/h，搜索范圍不變，為基本值， bound=search_scope。當速度 V≧36km/h，實際搜索范圍 s c o p es e a r c hVbound _3600/1000 ??? （ 32） 所以在 V≧ 36km/h 的情況下，若在時速為 80km/h，上例的實際搜索范圍 bound=V 1000/3600+search_scope=80 1000/3600+35= 通過對系統(tǒng)實際運行情況分析，這種 匹配范圍的定義是比較合理的。 衛(wèi)星收費地圖匹配算法描述 下面是搜索范圍方法的詳細描述。參數(shù)定義如下： i,j — i 為任意路段號； j為任意一節(jié)點號 。 fee_status — 當前路段收費標志值 1：行駛在收費路段；當前路段收費標志值0：沒有行駛在收費路段； search_scope — GPS 位置點：初始搜索范圍值； bound — 實際變化的搜索范圍； iV — 當前 i位置的行駛速度； 青島理工大學畢業(yè)設(shè)計（論文） 3 基于 GPS的不停車收費系統(tǒng)地圖匹配方法 30 ),( yxGi — GPS 位置 i的坐 標； ),( yxNodei — 任意搜索到的節(jié)點 i 的位置坐標； ),( yxNodefeei — 收費路段 i上的節(jié)點位置坐標； ),( vuSegmenti — 收費路段 i,左節(jié)點號為 u,右節(jié)點號為 v； )(typeSegmenti — i收費路段類型，入口值為 0，出口值為 1； )(lengthSegmenti — i 收費路段長度 /km； Fee（ all） — 總通行費用 /元； Node_Fee（ j） — 收費路段上 的節(jié)點號； Fee（ i） —— 收費路段費率 /（元 /km）； 設(shè)定收費標志值 fee_status 區(qū)分當前車輛是否在收費路段上： fee_status=0 —— 不在收費道路上；標志值 fee_status=1 —— 在收費道路上。 下面是匹配方法的詳細描述： 方法 : 步驟 1 初始化 fee_status=0,i=0,j=0,Fee（ all） =0,search_scope= 35m。 步驟 2 接收 GPS 定位信息 ,坐標值 ),( yxGi ,速度 v,接收頻率為 1 次 /秒 。 步驟 3 根據(jù)當前車輛的行駛 速度 v 確定搜索范圍 bound。 當 v36km/h,bound=search_scope； s c o p es e a r c hvb o u n dhkmv _3 6 0 0/1 0 0 0,/36 ????當 。 步驟 4 以 GPS 位置點 ),( yxGi 為中心，搜索范圍 bound 為半徑，在收費地圖上搜索路段數(shù)據(jù)，判斷收費點和收費路段；如果有節(jié)點 Node（ i）在點 ),( yxGi 搜索范圍bound 內(nèi)，首先，判斷 ),( yxNodei 是否是收費路段上的節(jié)點 ),(_ yxfeeNode i ； 再判斷是否是收費路段上的節(jié)點： ；如果 ；如果 ),(_),( ),(),( yxfe eN o d eyxN o d e i boundyxGyxN o d e i i? ?? 進入步驟 5； 步驟 5 如果是收費節(jié)點 ),(_ yxfeeNode i ，這里分兩個情況處理 ,車輛當前未在收青島理工大學畢業(yè)設(shè)計（論文） 3 基于 GPS的不停車收費系統(tǒng)地圖匹配方法 31 費路段上，即 fees_tatus=0。和車輛已經(jīng)行駛在收費路段上即 fee_status=1 的情況。 1）當 fee_status=0 時，判斷該點 Node_feei（ x,y）屬于哪一 個收費路段，接著再判斷是否該收費路段的路段類型是入口路段 0，如果是 ,進入收費道路開始計費過程。否則返回前面，繼續(xù)判斷。 0)( ),(),(_ ? ?t y p eS e g m e n t vuS e g m e n tyxf e eN o d e i ii如果如果 置 fee_status=1。記錄入口路段 ID： )()()()( iF e elS e g me n ta llF e ea llF e e i ???計費 返回步驟 2。 否則 返回步驟 2。 2）當 fee_status 為 1 時 ,進入收費路段后接著判斷是否通過節(jié)點號 ,判斷該節(jié)點Node_Fee（ j）和上個收費節(jié)點 Node_Fee（ j1）是否存在鄰接關(guān)系 ,如果存在 ,車輛當前行駛在這個收費路段上 ,進行計費 ,最后判斷該收費路段是出口 等于 1,之后設(shè)置fee_status=0,車輛離開收費路段 ,收費結(jié)束 ,返回步驟 2。否則返回步驟 2。 如果 ),()1(_)(_ vuS e g me n tjF e eN o d ejF e eN o d e i?? ）和（ ； 如果 iSegment （ type） =1； 置 fee_status=0。記錄路段出口 ID 號； 計費 Fee（ all） =Fee（ all） + iSegment （ L） ? Fee（ i）； 收費結(jié)束 ,返回步驟 2； 否則 計費 Fee（ all） =Fee（ all） + iSegment （ L） ? Fee（ i）； 返回步驟 2； 否則 返回步驟 2； 程序結(jié)束。 上述流程中費用計算是按里程收費的計算方法 ,對于按路段出入口收費的情況下 ,只需在收費路段出口處 ,將記錄的入口 ID和出口 ID在費率表中匹配 ,即可得到入口到出口整條路段的通行費用 Fee（ all）。下圖 32即為上數(shù)算法的程序框圖。 青島理工大學畢業(yè)設(shè)計（論文） 3 基于 GPS的不停車收費系統(tǒng)地圖匹配方法 32 圖 32 地圖匹配的程序框圖 青島理工大學畢業(yè)設(shè)計（論文） 3 基于 GPS的不停車收費系統(tǒng)地圖匹配方法 33 濟青 高速公路 （現(xiàn)為 國家高速公路網(wǎng)規(guī)劃 的一條東西橫向線，編號 G20 青銀高速公路 ，是 青島 — 銀川 高速公路的東段）是 中國 高速公路 15年 15 項最具影響力重大工程候選項目之一。 濟青 高速公路 全長 318 公里，西起 濟南市 大橋路，東至 青島 市北郊的西 袁莊 ，橫貫 山東半島 17 個市、縣（區(qū)）連接 濟南 、 淄博 、 濰坊 、 青 島 等重要工業(yè)城市，穿越 5條國道、 15 條省道。 濟青高速公路一直是山東最繁忙的高速公路，但也成為山東最為擁擠的高速公路，山東省的車禍大約一半發(fā)生濟青高速上，追尾事件時有發(fā)生，因此我國交通部決定開通濟青南線，但是南線并未起到分流作用，北線依舊車滿為患，雖有過將北線拓寬的提議并得到各方的同意，但由于牽涉面較廣，何時拓寬并沒有確切的時間。 濟青高速在各個出入口出收費站一般都有基于 DSRC 的 ETC 車道，雖大大解決了擁擠的程度，但依舊不能很好地解決道路擁堵問題，如果基于