基于道路連通性和最短路徑的綜合地圖匹配算法

崔松林,馮軍煥

(西南交通大學(xué) 信息科學(xué)與技術(shù)學(xué)院,四川 成都 611756)

0 引 言

在智能交通領(lǐng)域中,一般通過實(shí)時收集浮動車的運(yùn)行信息,如經(jīng)度、緯度、速度、方向和定位時間等關(guān)鍵參數(shù),并結(jié)合道路路網(wǎng)信息進(jìn)行動態(tài)實(shí)時的交通大數(shù)據(jù)分析,從而了解道路的交通流量,堵塞狀況,為車輛調(diào)度、車輛實(shí)時導(dǎo)航、道路規(guī)劃建設(shè)等提供決策依據(jù)[1-2]。

地圖匹配的本質(zhì)是根據(jù)車輛GPS定位點(diǎn)匹配出電子地圖中相對應(yīng)的道路,通過讀取車輛GPS定位信息,匹配出車輛所行駛的道路信息,從而分析道路的交通狀況[3-4]。地圖匹配的一般步驟為:1) 確定候選道路集; 2) 確定匹配道路; 3) 把待匹配點(diǎn)投影到匹配道路上,投影點(diǎn)即為最終匹配點(diǎn)[5]。

現(xiàn)有的地圖匹配算法有要素加權(quán)法[6]、路網(wǎng)拓?fù)浞╗7-8]、網(wǎng)格劃分法[9-10]等。要素加權(quán)法的特點(diǎn)是每次匹配的候選道路集為整個路網(wǎng)中的道路,依次計(jì)算每條道路的匹配度,匹配度最優(yōu)的道路作為匹配道路,計(jì)算量大、速度慢。基于路網(wǎng)拓?fù)潢P(guān)系的匹配算法具有一定的匹配精度,但是首次匹配仍然需要遍歷整個路網(wǎng),并且在信號丟失的情況下,候選道路集僅僅考慮與上一匹配道路鄰接的道路,不免會出錯。網(wǎng)格劃分法一定程度上減少了候選道路的數(shù)據(jù)量,但是網(wǎng)格的位置及大小無法動態(tài)調(diào)整,選取候選道路集時,判斷情況過多,具有一定的局限性。還有一些其他算法[11-13],原理復(fù)雜,難于實(shí)現(xiàn),很難投入實(shí)際應(yīng)用。

本文在充分分析上述算法的基礎(chǔ)……