王美玲，程 林

北京理工大學(xué)自動(dòng)化學(xué)院，北京100081

1 引 言

浮動(dòng)車系統(tǒng)是伴隨著ITS新技術(shù)應(yīng)用而在近幾年發(fā)展起來(lái)的新型交通流信息采集技術(shù)。一般使用大量的出租車或公交車作為浮動(dòng)車，通過已安裝的GPS車載裝置和無(wú)線通信設(shè)備，將車輛信息（如時(shí)間、速度、坐標(biāo)、方向等參數(shù)）實(shí)時(shí)地傳送到浮動(dòng)車信息中心。浮動(dòng)車輸出的動(dòng)態(tài)實(shí)時(shí)交通信息不僅能為相關(guān)部門提供道路交通實(shí)況，而且可作為道路建設(shè)規(guī)劃、擁堵緩解等各項(xiàng)工作中定量數(shù)據(jù)分析的基礎(chǔ)［1－4］。

地圖匹配技術(shù)是浮動(dòng)車數(shù)據(jù)處理的關(guān)鍵技術(shù)之一，只有判斷出車輛在哪條道路上行駛，才能將GPS數(shù)據(jù)轉(zhuǎn)化為道路的交通狀態(tài)［5－7］。

浮動(dòng)車系統(tǒng)具有數(shù)據(jù)量大，實(shí)時(shí)性要求高和采樣點(diǎn)間隔比較大等特點(diǎn)。浮動(dòng)車地圖匹配在應(yīng)用于現(xiàn)代城市復(fù)雜路網(wǎng)時(shí)主要面對(duì)3大關(guān)鍵技術(shù)難點(diǎn)［8－9］：① 數(shù)據(jù)需要實(shí)時(shí)處理，數(shù)據(jù)量較大，因此對(duì)系統(tǒng)的計(jì)算速度要求較高；② 數(shù)據(jù)間隔一般較大，導(dǎo)致定位點(diǎn)信息之間的相關(guān)性比較差；③ 現(xiàn)代城市路網(wǎng)密集且結(jié)構(gòu)復(fù)雜，因此對(duì)系統(tǒng)的匹配容錯(cuò)率要求較高。

文獻(xiàn)［10—11］所述的傳統(tǒng)導(dǎo)航地圖匹配算法，由于GPS采樣點(diǎn)的間隔僅為1s，因此比較容易獲得準(zhǔn)確的軌跡曲線作為匹配樣本，能夠?qū)崿F(xiàn)基于軌跡曲線的線到線的地圖匹配。然而，以北京市為例，每輛浮動(dòng)車每分鐘上傳一個(gè)GPS點(diǎn)數(shù)據(jù)，前后兩點(diǎn)間的相關(guān)性差決定了浮動(dòng)車系統(tǒng)無(wú)法采用線到線的地圖匹配方法；此外，浮動(dòng)車系統(tǒng)的數(shù)據(jù)量大，反映在單個(gè)GPS定位點(diǎn)上，其匹配時(shí)間遠(yuǎn)少于1s。可見，傳統(tǒng)的導(dǎo)航地圖匹配算法不能直接應(yīng)用于浮動(dòng)車系統(tǒng)。

浮動(dòng)車實(shí)時(shí)路況處理技術(shù)在我國(guó)各大城市還處于示范階段，目前參與北京市浮動(dòng)車系統(tǒng)的車輛約35 000輛，每輛車如果每分鐘上傳一個(gè)GPS數(shù)據(jù)，那么數(shù)據(jù)處理中心每天接收到的數(shù)據(jù)量就有5000余萬(wàn)條。隨著浮動(dòng)車數(shù)量的日益增多，文獻(xiàn)［1—9］所述的浮動(dòng)車地圖匹配算法已難以滿足當(dāng)前應(yīng)用環(huán)境下準(zhǔn)確性與實(shí)時(shí)性的要求?？梢?，提高浮動(dòng)車地圖匹配的準(zhǔn)確性與實(shí)時(shí)性，是需要進(jìn)一步研究的課題。

2 路網(wǎng)構(gòu)建

道路網(wǎng)絡(luò)的精度和屬性結(jié)構(gòu)直接關(guān)系到地圖匹配算法的性能。為此，本文首先給出Super－Map GIS平臺(tái)下的路網(wǎng)構(gòu)建方法。

2.1 拓?fù)涮幚?/h3>

以經(jīng)過配準(zhǔn)后的柵格地圖為背景，通過以直線代替曲線的方式創(chuàng)建道路中心線，將曲線道路分解為若干直線段；對(duì)于異面道路，合理設(shè)置非打斷線參數(shù)，以真實(shí)再現(xiàn)立體交通；完成拓?fù)涮幚恚?2］。

將路網(wǎng)中的假節(jié)點(diǎn)稱為形狀點(diǎn)，圖1給出拓?fù)涮幚砗蟮牟糠值缆肪W(wǎng)絡(luò)。

圖1 部分道路網(wǎng)絡(luò)Fig.1 Part of road network

2.2 屬性編輯

地圖匹配算法將利用道路網(wǎng)絡(luò)的如下屬性：

（1）路段編號(hào)SmID；

（2）路段起點(diǎn)SmFNode；

（3）路段終點(diǎn)SmTNode；

（4）路段正向阻力SmResistanceA；

（5）路段反向阻力SmResistanceB；

（6）路段長(zhǎng)度SmLength；

（7）路段方向類別Head。

其中，（4）、（5）、（7）為需要編輯與創(chuàng)建的字段。在SuperMap Deskpro中道路網(wǎng)絡(luò)的部分屬性如圖2所示。

圖2 SuperMap Deskpro中路網(wǎng)屬性Fig.2 Attribute of road network in SuperMap Deskpro

其中，Head為新建字段，字段值“1”表示雙向道路，將SmResistanceA與SmResistanceB均設(shè)置為0；字段值“2”表示單向道路，且方向?yàn)槠瘘c(diǎn)F→終點(diǎn)T，將SmResistanceA與SmResistanceB分別設(shè)置為0和∞（由10 000表示）；字段值“3”表示單向道路，且方向?yàn)榻K點(diǎn)T→起點(diǎn)F，將SmResistanceA與SmResistanceB分別設(shè)置為∞（由10 000表示）和0。

3 地圖匹配算法

基于浮動(dòng)車數(shù)據(jù)的地圖匹配算法流程如圖3所示。

圖3 地圖匹配算法流程Fig.3 Process of map matching algorithm

在地圖匹配前，首先進(jìn)行浮動(dòng)車GPS數(shù)據(jù)的預(yù)處理，剔除存在漂移錯(cuò)誤以及記錄為空載、駐車及停運(yùn)的數(shù)據(jù)，以求真實(shí)反映當(dāng)前路況；然后進(jìn)行坐標(biāo)變換，與電子路網(wǎng)地圖采用的坐標(biāo)系一致。

3.1 基于網(wǎng)格的候選路段確定

按照一定的步長(zhǎng)l（本文取70m），將導(dǎo)航電子地圖道路網(wǎng)絡(luò)從上到下、從左到右網(wǎng)格化分塊，將道路網(wǎng)絡(luò)分為M×N個(gè)相同的網(wǎng)格，記為Grid （i），（i＝0，1，…，MN－1），記道路網(wǎng)絡(luò)左下角的坐標(biāo)為O （X0，Y0），如圖4所示。

圖4 道路網(wǎng)絡(luò)的網(wǎng)格分塊Fig.4 Grid block of road network

設(shè)某定位點(diǎn)坐標(biāo)為（x，y） ，則其所在的網(wǎng)格為Grid （［（Y0＋Ml －y）／l ］N＋［（x－X0）／l］）。

對(duì)于每一個(gè)網(wǎng)格 Grid （i），將其擴(kuò)展為邊長(zhǎng)為2l的網(wǎng)格 Grid′（i），如圖5中虛線所示，記錄在網(wǎng)格 Grid′（i）之內(nèi)（如路段AB、BC、AE、BD、DF、DE）及與網(wǎng)格 Grid′（i）相交（如路段AH、EG）的路段編號(hào)，將各路段作為落入網(wǎng)格G rid （i）內(nèi)的GPS定位點(diǎn)的候選路段。

圖5 候選路段的確定Fig.5 Candidate road determination

3.2 基于權(quán)重的定位點(diǎn)匹配

算法為每條候選路段計(jì)算權(quán)重，包括距離權(quán)重WD、航向權(quán)重WH及可達(dá)性權(quán)重WR，并計(jì)算每條候選路段的權(quán)重總和W，以此確定匹配路段和匹配點(diǎn)。

3.2.1 距離權(quán)重

距離權(quán)重表示為［13］

式中，DW表示距離權(quán)重系數(shù)D表示定位點(diǎn)到候選路段的距離，當(dāng)定位點(diǎn)到候選路段的垂足不在候選路段上時(shí)，分別計(jì)算定位點(diǎn)到候選路段起點(diǎn)F和終點(diǎn)T的距離，并選擇較小值，如圖6所示，定位點(diǎn)P到候選路段BD和EF的距離分別為PH和PE的長(zhǎng)；DTH為距離閾值，本文將DTH設(shè)置為25m。

圖6 定位點(diǎn)到候選路段的距離Fig.6 Distance between the GPS point and the candidate road

因此，當(dāng)0≤D≤2DH時(shí)，f（D ）取值在1到－1間，并隨D的增加而線性減小。當(dāng)D＞2DH時(shí)，將f（D ）設(shè)置為－1。

3.2.2 航向權(quán)重

航向權(quán)重表示為

式中，HW表示航向權(quán)重系數(shù)；f（Δθ ）＝cos（Δθ），Δθ表示車輛航向與路段方向的夾角。設(shè)θ表示GPS接收機(jī)輸出的車輛航向，范圍是［0，2π），正北方向?yàn)?；θ0表示道路傾角，范圍是［0，π），正北方向?yàn)?；（xf，yf）和（xt，yt）分別表示候選路段起點(diǎn)F與終點(diǎn)T的坐標(biāo)。則當(dāng)xf＝xt時(shí)，θ0＝0；否則，θ0＝π／2－arctan ［（yt－yf）／（xt－xf）］。Δθ的取值如表1所示。

表1 Δθ的取值Tab.1 The value ofΔθ

續(xù)表1

3.2.3 可達(dá)性權(quán)重

可達(dá)性權(quán)重表示為

式中，RW表示可達(dá)性權(quán)重系數(shù)；將候選路段上距當(dāng)前定位點(diǎn)最近的點(diǎn)（垂直投影點(diǎn)、起點(diǎn)或終點(diǎn)）稱為該候選路段的虛擬匹配點(diǎn)，如果上一匹配點(diǎn)到該候選路段虛擬匹配點(diǎn)的最短距離不大于浮動(dòng)車在該時(shí)間間隔內(nèi)能夠行駛的最大距離（取1200m），X取1，否則?。?。

最短路徑的求解采用Dijkstra算法［12，14－16］，以上一匹配點(diǎn)和當(dāng)前虛擬匹配點(diǎn)所在網(wǎng)格為對(duì)角網(wǎng)格，并將兩對(duì)角網(wǎng)格構(gòu)成的矩形區(qū)域作為Dijkstra算法的搜索區(qū)域。在解算過程中，各路段權(quán)值為路段長(zhǎng)度與阻力之和［12，14］，即

正向權(quán)值為

反向權(quán)值為

如圖7所示，定位點(diǎn)P1已經(jīng)匹配到路段AB上的P點(diǎn)，對(duì)于當(dāng)前定位點(diǎn)P2，點(diǎn)E和F分別為其候選路段AD和CD的虛擬匹配點(diǎn)，其中路段CD為單向道路。點(diǎn)P到E和F的最短路徑分別為P－A－E和P－B－C－F，而路徑P－B－C－F的距離大于浮動(dòng)車在該時(shí)間間隔內(nèi)能夠行駛的最大距離，因此，候選路段AD較CD具有更高的可達(dá)性權(quán)重。

圖7 可達(dá)性權(quán)重Fig.7 Reachability weight

3.2.4 權(quán)重總和

權(quán)重總和表示為

算法為每條候選路段計(jì)算權(quán)重總和W，選出具有最高和次高權(quán)重和的兩候選路段，比較兩權(quán)重，如果相差大于1%，則將具有最高權(quán)重和的候選路段作為匹配路段，將該候選路段的虛擬匹配點(diǎn)作為匹配點(diǎn)。

反之，如果兩權(quán)重和相差在1%之內(nèi)，視為模糊情況，將當(dāng)前定位點(diǎn)匹配到兩候選路段的上游節(jié)點(diǎn)，即上一匹配點(diǎn)到兩候選路段虛擬匹配點(diǎn)的最短路徑所經(jīng)過的最后一個(gè)相同節(jié)點(diǎn)。如圖8所示，點(diǎn)P是已經(jīng)匹配到路段AB上的匹配點(diǎn)，對(duì)當(dāng)前定位點(diǎn)Q，候選路段EF與DG分別具有最高和次高的權(quán)重和，點(diǎn)M與N分別為其虛擬匹配點(diǎn)。點(diǎn)P到M與N的最短路徑分別為P－B－C－D－E－M和P－BC－D－N，由于兩權(quán)重和相差在1%內(nèi)，因此將定位點(diǎn)Q匹配到路段EF和DG的上游節(jié)點(diǎn)，即D點(diǎn)。

圖8 上游節(jié)點(diǎn)匹配Fig.8 Upstream node matching

3.3 基于最短路徑的行駛軌跡選擇

由于浮動(dòng)車系統(tǒng)上傳數(shù)據(jù)的時(shí)間間隔較大，同一輛車前后兩點(diǎn)很可能相距幾個(gè)路段。因此，算法對(duì)某一定位點(diǎn)結(jié)束匹配之后，在充分考慮路網(wǎng)拓?fù)潢P(guān)系的前提下，選擇當(dāng)前匹配點(diǎn)與上一匹配點(diǎn)間的最短路徑作為車輛的行駛軌跡，這與大多數(shù)熟悉路網(wǎng)的司機(jī)在一般情況下會(huì)選擇最近的道路到達(dá)目的地的實(shí)際情況相符。最短路徑的求解同3.2.3節(jié)所述方法，路段權(quán)值設(shè)置同式（4）和式（5）。

4 算法驗(yàn)證

將本文算法應(yīng)用于北京市道路網(wǎng)絡(luò)，距離、航向與可達(dá)性權(quán)重系數(shù)DW、HW與RW均設(shè)置為1／3。圖9給出同一輛浮動(dòng)車連續(xù)3個(gè)定位點(diǎn)的正確匹配結(jié)果；圖10和表2分別給出了其中第2個(gè)定位點(diǎn)的匹配情況，在表2中，ID表示候選路段編號(hào)，R表示上一匹配點(diǎn)到當(dāng)前定位點(diǎn)候選路段虛擬匹配點(diǎn)的距離；圖11給出傳統(tǒng)算法直接將具有最高權(quán)重的候選路段作為匹配路段時(shí)的錯(cuò)誤匹配結(jié)果。

圖9 正確地圖匹配結(jié)果Fig.9 The correct map matching result

圖10 第2個(gè)定位點(diǎn)的匹配結(jié)果Fig.10 Matching result of the second GPS point

表2 第2個(gè)定位點(diǎn)的候選路段Tab.2 Candidate roads of the second GPS point

由此可見，本文設(shè)計(jì)的算法能夠正確計(jì)算候選路段的各項(xiàng)權(quán)重，有效排除不可能的候選路段；同時(shí)，候選路段11和176分別具有最高與次高的權(quán)重，且相差1%之內(nèi)，176為車輛實(shí)際經(jīng)過的路段，算法將定位點(diǎn)匹配到兩路段的上游節(jié)點(diǎn)，而如圖11所示，如果直接選擇最高權(quán)重的候選路段作為匹配路段，將造成連續(xù)的匹配錯(cuò)誤。浮動(dòng)車地圖匹配的最終目的是為城市路況模型提供車輛行駛軌跡，模糊情況下的上游節(jié)點(diǎn)匹配雖然帶來(lái)較大的單點(diǎn)匹配誤差，但卻避免由于單點(diǎn)匹配錯(cuò)誤而造成的連續(xù)匹配失敗。

圖11 錯(cuò)誤地圖匹配結(jié)果Fig.11 The wrong map matching result

此外，采用NovAtel FlexPak－G2GPS接收機(jī)接收同一輛浮動(dòng)車在不同時(shí)間段內(nèi)行駛于多條路線時(shí)的定位數(shù)據(jù)。利用此數(shù)據(jù)，將本文算法運(yùn)行于2.53GHz CPU、2G內(nèi)存的計(jì)算機(jī)上進(jìn)行驗(yàn)證。經(jīng)統(tǒng)計(jì)，算法的平均正確匹配率為96.55%，單點(diǎn)的平均匹配時(shí)間為0.931ms。

對(duì)于現(xiàn)有實(shí)時(shí)運(yùn)轉(zhuǎn)的浮動(dòng)車地圖匹配算法，正確匹配率平均在95%左右，單點(diǎn)匹配時(shí)間在幾毫秒至幾十毫秒之間。可見，本文算法在保證較高準(zhǔn)確率的基礎(chǔ)上，極大地提高匹配效率，能夠滿足目前北京市浮動(dòng)車系統(tǒng)地圖匹配的準(zhǔn)確性要求及每分鐘35 000點(diǎn)的計(jì)算速度要求。

5 結(jié) 論

針對(duì)現(xiàn)有浮動(dòng)車地圖匹配算法應(yīng)用于城市復(fù)雜路網(wǎng)時(shí)面臨的關(guān)鍵技術(shù)難點(diǎn)，對(duì)浮動(dòng)車地圖匹配展開研究，主要包括以下方面：

（1）給出道路網(wǎng)絡(luò)的構(gòu)建方法，充分考慮道路網(wǎng)絡(luò)的空間分布特性，使構(gòu)建的網(wǎng)絡(luò)區(qū)別于普通平面網(wǎng)絡(luò)。合理編輯屬性表結(jié)構(gòu)，有效降低了地圖匹配算法的計(jì)算復(fù)雜度。

（2）基于網(wǎng)格的候選路段確定，根據(jù)GPS定位點(diǎn)所在網(wǎng)格，直接得到其候選路段，極大地提高了算法的運(yùn)行效率。將各網(wǎng)格擴(kuò)展為原來(lái)邊長(zhǎng)的2倍，將新網(wǎng)格所包含的路段作為候選路段，能夠保證正確路段在候選路段之中，克服潛在的匹配錯(cuò)誤。

（3）基于距離、航向和可達(dá)性權(quán)重的定位點(diǎn)匹配，距離的計(jì)算，考慮投影點(diǎn)與候選路段的位置關(guān)系，準(zhǔn)確得到虛擬匹配點(diǎn)。根據(jù)道路屬性，給出車輛航向與路段方向夾角的各種可能?？蛇_(dá)性權(quán)重的引入使車輛處于單向道路、立體交通道路時(shí)保證地圖匹配的精度。模糊情況下的節(jié)點(diǎn)匹配，適于城市路網(wǎng)結(jié)構(gòu)復(fù)雜、主輔路并行和交叉口繁多的特點(diǎn)，避免連續(xù)匹配失敗。

（4）基于最短路徑的行駛軌跡選擇，適于浮動(dòng)車數(shù)據(jù)采樣間隔大的特點(diǎn)，對(duì)Dijkstra算法搜索區(qū)域的合理限制，有效保證路徑選擇的實(shí)時(shí)性。

由于不同的權(quán)重系數(shù)會(huì)給匹配結(jié)果帶來(lái)一定的影響，車輛在兩匹配點(diǎn)間的行駛軌跡并不是在任何情況下都是兩點(diǎn)間的最短路徑，因此，為進(jìn)一步提高算法的準(zhǔn)確性，根據(jù)車輛的行駛狀態(tài)和所處的路網(wǎng)環(huán)境合理調(diào)整權(quán)重系數(shù)，以及考慮更多的因素確定車輛在兩匹配點(diǎn)間的行駛軌跡，是下一步的研究方向。

［1］ LIU Pei.Study on Map－matching Algorithm Based on Probe Car［D］.Beijing：Beijing Jiaotong University，2007.（劉培.基于浮動(dòng)車數(shù)據(jù)的地圖匹配算法研究 ［D］.北京：北京交通大學(xué)，2007.）

［2］ YIN Xiangyong，JIA Shunping.Synthesized Map Matching Algorithm for Floating Cars Processing Center［J］.Computer Engineering and Applications，2008，44（36）：881－884.（尹相勇，賈順平.基于MapObjects的浮動(dòng)車中心地圖匹配綜合算法開發(fā)［J］.計(jì)算機(jī)工程與應(yīng)用，2008，44（36）：881－884.）

［3］ ZHU Tongyu，GUO Shengmin.A Study on Floating Car Based Information Processing Technology［J］.Journal of Image and Graphics，2009，14（7）：1230－1237.（諸彤宇，郭勝敏.浮動(dòng)車信息處理技術(shù)研究 ［J］.中國(guó)圖象圖形學(xué)報(bào)，2009，14（7）：1230－1237.）

［4］ ZHANG Wei，XU Jianmin，LIN Mianfeng.Map Matching Algorithm of Large Scale Probe Vehicle Data［J］.Journal of Transportation Systems Engineering and Information Technology，2007，7（2）：40－45.（章威，徐建閩，林綿峰.基于大規(guī)模浮動(dòng)車數(shù)據(jù)的地圖匹配算法 ［J］.交通運(yùn)輸系統(tǒng)工程與信息，2007，7（2）：40－45.）

［5］ WANG Dongzhu，DONG Jiming，LI Yameng，et al.Mapmatching Method Based on Zero－speed Points in Floating Car Data［J］.Journal of Transport Information and Safety，2009，27（6）：38－42.（王東柱，董繼明，李亞檬，等.浮動(dòng)車數(shù)據(jù)中零速度點(diǎn)數(shù)據(jù)地圖匹配方法 ［J］.交通信息與安全，2009，27（6）：38－42.）

［6］ XUE Ming，LV Weifeng，ZHU Tongyu.Study on Key Technology of Floating Car Information Processing System［J］.Control and Automation，2006，22（11）：244－246.（薛明，呂衛(wèi)鋒，諸彤宇.浮動(dòng)車信息處理系統(tǒng)關(guān)鍵技術(shù)的研究［J］.微計(jì)算機(jī)信息，2006，22（11）：244－246.）

［7］ LIU Yanting，WU Jianping，ZHANG Ge.A Map Matching Algorithm for Public Traffic Control Center Based on Long Space and Limited GPS Data［J］.Journal of Transportation Engineering and Information，2007，5（2）：69－74.（劉彥廷，吳建平，張鴿.基于長(zhǎng)間隔大規(guī)模數(shù)據(jù)的地圖匹配算法研究［J］.交通運(yùn)輸工程與信息學(xué)報(bào)，2007，5（2）：69－74.）

［8］ ZHU Liyun，WEN Huimin，SUN Jianping.Floating Car Based Real－time－traffic－info Collection System in Beijing［J］.Urban Transport of China，2008，6（1）：77－80.（朱麗云，溫慧敏，孫建平.北京市浮動(dòng)車交通狀況信息實(shí)時(shí)計(jì)算系統(tǒng)［J］.城市交通，2008，6（1）：77－80.）

［9］ ZHU Liyun，GUO Jifu，WEN Huimin，et al.A Mapmatching Algorithm of Real－time Floating Car System for Complex City Road Network［J］.Computer and Communications，2007，25（6）：81－84.（朱麗云，郭繼孚，溫慧敏，等.一種適用于復(fù)雜城市路網(wǎng)的浮動(dòng)車實(shí)時(shí)地圖匹配技術(shù)［J］.交通與計(jì)算機(jī)，2007，25（6）：81－84.）

［10］ SU Jie，ZHOU Dongfang，YUE Chunsheng.Real－time Map－matching Algorithm in GPS Navigation System for Vehicles［J］.Acta Geodaetica et Cartographica Sinica，2001，30（3）：252－256.（蘇潔，周東方，岳春生.GPS車輛導(dǎo)航中的實(shí)時(shí)地圖匹配算法［J］.測(cè)繪學(xué)報(bào)，2001，30（3）：252－256.）

［11］ TANG Jinjun，CAO Kai.An Adaptive Trajectory Curves Map－matching Algorithm［J］.Acta Geodaetica et Cartographica Sinica，2008，37（3）：308－315.（唐進(jìn)君，曹凱.一種自適應(yīng)軌跡曲線地圖匹配算法 ［J］.測(cè)繪學(xué)報(bào)，2008，37（3）：308－315.）

［12］ CHENG Lin，WANG Meiling，ZHANG Yi.An Improved Algorithm Based on SuperMap GIS［J］.Journal of Geoinformation Science，2010，12（5）：649－654.（程林，王美玲，張毅.一種基于SuperMap GIS的改進(jìn)Dijkstra算法［J］.地球信息科學(xué)學(xué)報(bào)，2010，12（5）：649－654.）

［13］ VELAGA N R，QUDDUS M A，BRISTOW A L.Developing an Enhanced Weight－based Topological Map－matching Algorithm for Intelligent Transport Systems［J］.Transportation Research Part C—Emerging Technologies，2009，7：672－683.

［14］ CHENG Lin，WANG Meiling.A New Path Planning Algorithm Based on Partitioned Urban Transportation Network［C］∥Proceedings of 2010International Conference on Computer Application and System Modeling（ICCASM 2010）.Taiyuan：IEEE，2010：13－17.

［15］ HAN Gang，JIANG Jie，CHEN Jun，et al.An Arc Based Dijkstra Algorithm for Road Turning Penalty in Vehicle Navigation System［J］.Acta Geodaetica et Cartographica Sinica，2002，31（4）：366－368.（韓剛，蔣捷，陳軍，等.車載導(dǎo)航系統(tǒng)中顧及道路轉(zhuǎn)向限制的弧段Dijkstra算法［J］.測(cè)繪學(xué)報(bào)，2002，31（4）：366－368.）

［16］ LU Feng.Shortest Path Algorithms：Taxonomy and Advance in Research［J］.Acta Geodaetica et Cartographica Sinica，2001，30（3）：269－275.（陸鋒.最短路徑算法：分類體系與研究進(jìn)展［J］.測(cè)繪學(xué)報(bào)，2001，30（3）：269－275.）