【正文】 濟(jì)青高速公路一直是山東最繁忙的高速公路，但也成為山東最為擁擠的高速公路，山東省的車禍大約一半發(fā)生濟(jì)青高速上，追尾事件時(shí)有發(fā)生，因此我國(guó)交通部決定開通濟(jì)青南線，但是南線并未起到分流作用，北線依舊車滿為患，雖有過將北線拓寬的提議并得到各方的同意，但由于牽涉面較廣，何時(shí)拓寬并沒有確切的時(shí)間。 青島理工大學(xué)畢業(yè)設(shè)計(jì)（論文） 3 基于 GPS的不停車收費(fèi)系統(tǒng)地圖匹配方法 32 圖 32 地圖匹配的程序框圖 青島理工大學(xué)畢業(yè)設(shè)計(jì)（論文） 3 基于 GPS的不停車收費(fèi)系統(tǒng)地圖匹配方法 33 濟(jì)青 高速公路 （現(xiàn)為 國(guó)家高速公路網(wǎng)規(guī)劃 的一條東西橫向線，編號(hào) G20 青銀高速公路 ，是 青島 — 銀川 高速公路的東段）是 中國(guó) 高速公路 15年 15 項(xiàng)最具影響力重大工程候選項(xiàng)目之一。 上述流程中費(fèi)用計(jì)算是按里程收費(fèi)的計(jì)算方法 ,對(duì)于按路段出入口收費(fèi)的情況下 ,只需在收費(fèi)路段出口處 ,將記錄的入口 ID和出口 ID在費(fèi)率表中匹配 ,即可得到入口到出口整條路段的通行費(fèi)用 Fee（ all）。 如果 ),()1(_)(_ vuS e g me n tjF e eN o d ejF e eN o d e i?? ）和（ ； 如果 iSegment （ type） =1； 置 fee_status=0。 2）當(dāng) fee_status 為 1 時(shí) ,進(jìn)入收費(fèi)路段后接著判斷是否通過節(jié)點(diǎn)號(hào) ,判斷該節(jié)點(diǎn)Node_Fee（ j）和上個(gè)收費(fèi)節(jié)點(diǎn) Node_Fee（ j1）是否存在鄰接關(guān)系 ,如果存在 ,車輛當(dāng)前行駛在這個(gè)收費(fèi)路段上 ,進(jìn)行計(jì)費(fèi) ,最后判斷該收費(fèi)路段是出口 等于 1,之后設(shè)置fee_status=0,車輛離開收費(fèi)路段 ,收費(fèi)結(jié)束 ,返回步驟 2。記錄入口路段 ID： )()()()( iF e elS e g me n ta llF e ea llF e e i ???計(jì)費(fèi) 返回步驟 2。否則返回前面，繼續(xù)判斷。和車輛已經(jīng)行駛在收費(fèi)路段上即 fee_status=1 的情況。 當(dāng) 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 ????當(dāng) 。 步驟 2 接收 GPS 定位信息 ,坐標(biāo)值 ),( yxGi ,速度 v,接收頻率為 1 次 /秒 。 fee_status — 當(dāng)前路段收費(fèi)標(biāo)志值 1：行駛在收費(fèi)路段；當(dāng)前路段收費(fèi)標(biāo)志值0：沒有行駛在收費(fèi)路段； search_scope — GPS 位置點(diǎn)：初始搜索范圍值； bound — 實(shí)際變化的搜索范圍； iV — 當(dāng)前 i位置的行駛速度； 青島理工大學(xué)畢業(yè)設(shè)計(jì)（論文） 3 基于 GPS的不停車收費(fèi)系統(tǒng)地圖匹配方法 30 ),( yxGi — GPS 位置 i的坐 標(biāo)； ),( yxNodei — 任意搜索到的節(jié)點(diǎn) i 的位置坐標(biāo)； ),( yxNodefeei — 收費(fèi)路段 i上的節(jié)點(diǎn)位置坐標(biāo)； ),( vuSegmenti — 收費(fèi)路段 i,左節(jié)點(diǎn)號(hào)為 u,右節(jié)點(diǎn)號(hào)為 v； )(typeSegmenti — i收費(fèi)路段類型，入口值為 0，出口值為 1； )(lengthSegmenti — i 收費(fèi)路段長(zhǎng)度 /km； Fee（ all） — 總通行費(fèi)用 /元； Node_Fee（ j） — 收費(fèi)路段上 的節(jié)點(diǎn)號(hào)； Fee（ i） —— 收費(fèi)路段費(fèi)率 /（元 /km）； 設(shè)定收費(fèi)標(biāo)志值 fee_status 區(qū)分當(dāng)前車輛是否在收費(fèi)路段上： fee_status=0 —— 不在收費(fèi)道路上；標(biāo)志值 fee_status=1 —— 在收費(fèi)道路上。 衛(wèi)星收費(fèi)地圖匹配算法描述 下面是搜索范圍方法的詳細(xì)描述。 當(dāng)速度 V＜ 36km/h，搜索范圍不變，為基本值， bound=search_scope。在車速高于 36km/h，搜索范圍需要?jiǎng)討B(tài)隨車速的變化。假如 GPS 定位誤差為 20m，道路為兩車道組成，每車道 ，路側(cè)間隙為各為 ，則搜索范圍為： alnmsc o p ese a c h ????? 2_ （ 31） 其中 m 表示 GPS 定位誤差， n 表示車道數(shù)， l 表示車道寬度， a表示路側(cè)間隙 以濟(jì)青高速公路為例，假設(shè) GPS 的定位誤差為 18，該高速公路為雙向四車道，路寬 ，路側(cè)間隙為 則 search_scope=18+4 +2 = （ 2）動(dòng)態(tài)搜索匹配范圍值的確定 搜索范圍可根據(jù)車速在一定范圍內(nèi)自動(dòng)調(diào)節(jié)。二是搜索范圍必須完全覆蓋關(guān)鍵點(diǎn)所在道路同向所有車道。匹配范圍分為兩個(gè)部分，基本值和變化值，實(shí)際搜索范圍為兩者之和。因此匹配范圍的選取和車速有一定的關(guān)系。選取過大會(huì)造成誤判且加大計(jì)算量。 搜索匹配范圍是車輛行駛時(shí)，以車輛 GPS 定位點(diǎn)為中心點(diǎn)，一個(gè)值為半徑的區(qū)域內(nèi)在收費(fèi)電子地圖上搜索關(guān)鍵點(diǎn)進(jìn)行匹配。隨車速增加 ,判斷范圍增大 ,車速減小 ,判斷范圍減小。高速公路雙向路段的橫向距離通常大大小于 50m。車輛在高速公路行駛的特點(diǎn) ,快速 120km/h,而 GPS 定位數(shù)據(jù)以 1 次 /秒的頻率接收。這樣才能保證所有節(jié)點(diǎn)都不會(huì)遺漏。本文采用根據(jù)車輛行駛速度動(dòng)態(tài)收 本文采用根據(jù)車輛行駛速度動(dòng)態(tài)調(diào)整搜索范圍的方法。 GPS 數(shù)據(jù)接收頻率 1 次 /秒，如果車速過快，搜索范圍會(huì)跳過路段上的一些節(jié)點(diǎn)，造成漏點(diǎn)。搜索范圍的選取非常重要，范圍過大，容易造成誤判，且加大計(jì)算量，如近距離平行的主輔路 ,使輔路行駛的車輛誤收費(fèi)。 基于 GPS 的不停車收費(fèi)系統(tǒng)的地圖匹配方法 地圖匹配中搜索范圍的確定 在電子地圖的精度和 GPS 定位精度在目 前的技術(shù)水平下難以有較大提升的條件下，對(duì)匹配方法進(jìn)行優(yōu)化是能否成功實(shí)現(xiàn)衛(wèi)星收費(fèi)的關(guān)鍵環(huán)節(jié)。 胖客戶端收費(fèi)地圖數(shù)據(jù) 的定義要考慮增加收費(fèi)類型表和費(fèi)率表，根據(jù)收費(fèi)類型，查詢費(fèi)率表內(nèi)相關(guān)費(fèi)率，基本表包括：路段編號(hào)，路段名稱，路段長(zhǎng)度，路段左節(jié)點(diǎn)坐標(biāo)，路段右節(jié)點(diǎn)坐標(biāo)，路段類型，收費(fèi)類型。 收費(fèi)系統(tǒng)中費(fèi)率計(jì)算分 2 種情況，瘦客戶端計(jì)費(fèi)和胖客戶端計(jì)費(fèi)，瘦客戶端計(jì)費(fèi)是將費(fèi)率計(jì)算放在后臺(tái)完成，胖客戶端計(jì)費(fèi)將費(fèi)率計(jì)算前段完成，從而減少后臺(tái)的計(jì)算壓力， 2 種費(fèi)率計(jì)算方式下，車載端存儲(chǔ)的信息也不一樣。 地圖信息的精簡(jiǎn)包括下面兩個(gè)方面： 電子地圖可通過精簡(jiǎn)地圖數(shù)據(jù)進(jìn)行壓縮，去除不必要的形狀連接點(diǎn)， 保留路段的拓?fù)浣Y(jié)構(gòu)，這樣可大大的減少數(shù)據(jù)量，節(jié)省數(shù)據(jù)存儲(chǔ)空間和減少程序計(jì)算量。由于考慮到車載系統(tǒng)受成本限制，其硬件資源非常有限，因此要求在滿足收費(fèi)功能要求的條件下盡量縮小 存儲(chǔ)地圖的數(shù)據(jù)量， 即車載設(shè)備只存儲(chǔ)必要的用于收費(fèi)的基礎(chǔ)信息，大量的時(shí)效性數(shù)據(jù)的查詢和計(jì)算量較大的操作都放到后臺(tái)服務(wù)器上進(jìn)行，因而需要對(duì)電子地圖數(shù)據(jù)進(jìn)行裁剪，以便節(jié)省車載單元內(nèi)存資源，提高運(yùn)行效率。 圖 31黃島到濟(jì)南行程路段定義圖 圖中各關(guān)鍵點(diǎn)的名稱、屬性及對(duì)應(yīng)的屬性值如下表 31 所示。在此段高速公路收費(fèi)道路中，對(duì)道路中的收費(fèi)關(guān)鍵點(diǎn)和進(jìn)出口路段作如下定義。 圖 31是以黃島 到濟(jì)南的行程各路段定義簡(jiǎn)圖。路段識(shí)別屬性值：出入口的識(shí)別是收費(fèi)路段識(shí)別最重要的部分，出入口識(shí)別靠設(shè)置路段識(shí)別屬性值來實(shí)現(xiàn)，路段識(shí)別屬性值定義為 3種，收費(fèi)路段入口識(shí)別屬性值為 0；收費(fèi)路段出口識(shí)別屬性值為 1；中間路段識(shí)別屬性值為 2。 收費(fèi)關(guān)鍵點(diǎn)和收費(fèi)路段屬性值的定義 關(guān)鍵點(diǎn)屬性值的定義是為了區(qū)分出入口關(guān)鍵點(diǎn)，不能用來區(qū)分 判斷出入口，對(duì)于車輛進(jìn)出收費(fèi)道路起到輔助識(shí)別作用，入口關(guān)鍵點(diǎn)屬性值為 0；出口關(guān)鍵點(diǎn)屬性值為1；經(jīng)過點(diǎn)屬性值為 2。入口路段是從主線站入口開始沿道 路方向 在入口和下一個(gè)經(jīng)過點(diǎn)的中間位置附近的道路上添加一個(gè)新的經(jīng)過點(diǎn)，新經(jīng)過點(diǎn)一端連接主路入口、另一端連接下一經(jīng)過點(diǎn)，從入口到新經(jīng)過點(diǎn)形成主路入口路段；同理出口路段是從主線站出口開始沿道路相反方向，在出口和上一經(jīng)過點(diǎn)的中間位置附近添加新經(jīng)過點(diǎn)，形成主路出口路段。 入口點(diǎn)是車輛經(jīng)該點(diǎn)進(jìn)入收費(fèi)道路的點(diǎn)，和高速公路入口收費(fèi)站對(duì)應(yīng)；出口點(diǎn)是車輛經(jīng)該點(diǎn)離開收費(fèi)道路的點(diǎn)，和高速公路出口收費(fèi)站對(duì)應(yīng)；經(jīng)過點(diǎn)，對(duì)于匝道收費(fèi)站而言，是匝道和主路的交匯點(diǎn)，該點(diǎn)同時(shí)屬于主路和匝道；由此定義入口點(diǎn)和經(jīng)入口匝道與主路交匯的經(jīng)過點(diǎn)組成的路段為入口路段；出口點(diǎn)和經(jīng)出口匝道與主路交匯形成的經(jīng)過點(diǎn)組成的路段為出口路段；經(jīng)過點(diǎn)與經(jīng)過點(diǎn)連接組成的路段為經(jīng)過路段，多個(gè)相連接的經(jīng)過路段組成主路路段。通過對(duì)現(xiàn)有高速公路布局和收費(fèi)情況的分析，我們定義 3 種類型的關(guān)鍵點(diǎn)和 3種類型的路段。 收費(fèi)電子地圖根據(jù)存放位置的不同分為兩部分：一是存儲(chǔ)于車載單元中，對(duì)這部分的要求是盡可能的精簡(jiǎn)屬性信息，以節(jié)約成本； 二是存儲(chǔ)在管理中心數(shù)據(jù)庫中，此部分中包括了 GPS 定位收費(fèi)所需要的詳細(xì)全面的地理信息、包括路段編號(hào)、路段名稱、路段長(zhǎng)度、路段類型、限速、有節(jié)點(diǎn)編號(hào)、左節(jié)點(diǎn)編號(hào)、高速公路名稱、高速公路公司代碼、收費(fèi)類型等。 基于 GPS 的收 費(fèi)地圖的定義 衛(wèi)星收費(fèi)電子地圖不同于一般車載導(dǎo)航所用地圖，這是一種專門用于道路收費(fèi)的具有特定定義的地圖，該地圖包含收費(fèi)路段的地理位置信息、形狀數(shù)據(jù)信息、拓?fù)潢P(guān)系數(shù)據(jù)信息和屬性信息等。因此單純依靠 GPS 定位和提高地圖精度，很難區(qū)分上下行兩個(gè)距離很近的點(diǎn)，因而對(duì)兩條道路匹配混亂，導(dǎo)致收費(fèi)路徑的錯(cuò)誤判斷。而只有在兩者都達(dá)到一定精度條件下才能進(jìn)行準(zhǔn)確無誤的匹配。程序在接收到 GPS 定位數(shù)據(jù)信息后，先做譯碼處理，在提取位置、方向、速度及其他一些環(huán)境數(shù)據(jù)信息，最后將車輛位置信息和收費(fèi)地圖上路段通過一定的匹配方法進(jìn)行精確地匹配，從而可以清晰區(qū)分收費(fèi)路段和非收費(fèi)路段，達(dá)到較準(zhǔn)確地收費(fèi)效果。也是下文所要展開研究的問題。毫無疑問，沒有地圖匹配的協(xié)助，這將是個(gè)不可能完成的青島理工大學(xué)畢業(yè)設(shè)計(jì)（論文） 2 地圖匹配技術(shù) 23 任務(wù)。雖然基于圖像識(shí)別的車道保持技術(shù)已經(jīng)相當(dāng)成熟，但是由于惡劣天氣對(duì)該系統(tǒng)的嚴(yán)重影響使得重新考慮一種新的 方法成為一種必要。例如，地圖匹配可以應(yīng)用于車輛巡航控制（ Vehicle Cruise Control）系統(tǒng)中，具有地圖匹配模塊的系統(tǒng)可以根據(jù)電子地圖所表現(xiàn)的路網(wǎng)中道路的曲率和拐點(diǎn)來自動(dòng)的調(diào)整車輛的巡航速度。 1. 在車輛定位導(dǎo)航系統(tǒng)中的應(yīng)用 地圖匹配可以為車輛定位導(dǎo)航系統(tǒng)提供準(zhǔn)確的位置信息，便于在地圖上正確地顯示車輛位置，向司機(jī)提供準(zhǔn)確的行駛指令，并提供給司機(jī)從起點(diǎn)到目的地的最短路線，或最短行駛時(shí)間的路線，并為司機(jī)提供路線周圍大型建筑物如銀行、商店、加油站、旅館等位置信息為用戶的，還為用戶提供道路的擁堵情況，方便用戶及時(shí)調(diào)整 路線，避免浪費(fèi)時(shí)間和改善交通擁堵情況。 基于以上這些情況，地圖匹配算法的研究應(yīng)該朝著多手段綜合運(yùn)用，相互補(bǔ)充、相互完善、精確化方向發(fā)展，對(duì)算法本身的準(zhǔn)確性應(yīng)該有一個(gè)檢驗(yàn)機(jī)制，以最大程度保證算法的可靠性。兩條道路如果僅僅是物理上連通是不夠的，車輛是否能夠從一條道路運(yùn)動(dòng)到另一條道路還要遵守交通規(guī)則。 基于拓?fù)潢P(guān)系的算法對(duì)電子地圖的精確度依賴性太高，而且該算法僅僅建立了結(jié)點(diǎn)與結(jié)點(diǎn)、結(jié)點(diǎn)與道路、道路與道路之間的拓?fù)潢P(guān)系。 地圖匹配方法分析 最短距離投影法邏輯簡(jiǎn)單、速度快、實(shí)時(shí)性好、所需內(nèi)存空間少，但它沒有考慮GPS數(shù)據(jù)接收中的各種情況及道路的地形特征，通常作為一種基本方法，與其他匹配方法結(jié)合能得到較好的效果。 圖 26 道路拓?fù)潢P(guān)系 基于拓?fù)潢P(guān)系的算法通過對(duì)前一次匹配結(jié)果和車輛前進(jìn)方向的分析，利用道路層的網(wǎng)絡(luò)拓?fù)潢P(guān)系，來確定當(dāng)前車輛的匹配位置。 由于受車輛速度的限制，在一定的時(shí)間內(nèi)，車輛只能駛經(jīng)有限的路段上。在一段時(shí)間內(nèi)，車輛行駛的區(qū)域是有限的，而且這個(gè)區(qū)域的道路也是有限的，因此在區(qū)域中建立的道路實(shí)體對(duì)也是有限的。 基于拓?fù)潢P(guān)系的匹配算法是在道路層網(wǎng)絡(luò)拓?fù)潢P(guān)系的數(shù)據(jù)基礎(chǔ)上進(jìn)行的，是利用歷史軌跡對(duì)地圖數(shù)據(jù)庫的道路信息進(jìn)行實(shí)時(shí)的模式識(shí)別的一種方式。 4） 多邊形嵌套關(guān)系的生成，建立多邊 形嵌套關(guān)系樹，即找出多邊形包含的“島嶼”，建立多邊形與多邊形之間的關(guān)系。 2） 結(jié)點(diǎn)匹配：建立點(diǎn)、弧段關(guān)聯(lián)關(guān)系。 4） 面：由若干弧線相連的封閉曲線圍成的區(qū)域稱為面，面以弧線的形式表示，但通過代碼與弧線區(qū)別，且其內(nèi)部填充方式可以設(shè)置。 2） 形狀點(diǎn) ：表示線、面經(jīng)過的點(diǎn)，不具拓?fù)湫再|(zhì)。具有拓?fù)湫畔⒌氖噶繑?shù)據(jù)是網(wǎng)絡(luò)分析必要的數(shù)據(jù)來源。 基于拓?fù)潢P(guān)系的算法 拓?fù)淇臻g關(guān)系是一種對(duì)空間結(jié)構(gòu)進(jìn)行明確定義的數(shù)學(xué)方法。誤差橢圓的定義如圖 25所示。通過改變 0?? 的值來調(diào)整誤差橢圓的大小，獲得不同的可信度。基于誤差模型，根據(jù)接收的 GPS定位數(shù)據(jù)建立緩沖區(qū)。 概率統(tǒng)計(jì)算法 基于概率統(tǒng)計(jì)的地圖匹配同樣是一種基礎(chǔ)的匹配方法。該方法根據(jù)道路屬性，預(yù)先設(shè)置一個(gè)匹配閾值，在數(shù)字地圖數(shù)據(jù)庫中的所有或部分路段中，計(jì)算當(dāng)前獲取的 GPS數(shù)據(jù)與各道路路段之間的距離以及 GPS數(shù)據(jù)在該道路路段上的最短距離點(diǎn)，將在閾值范圍內(nèi)各路段的匹配距離進(jìn)行比較，得到一條距離最短的路段，則該道路為 GPS點(diǎn)的匹配路段，該最短距離點(diǎn)為 GPS點(diǎn)的 匹配點(diǎn)。下面對(duì)其中