基于動(dòng)態(tài)規(guī)劃算法的軌跡地圖匹配軟件設(shè)計(jì)與實(shí)現(xiàn)

姜雪原

摘要：針對(duì)智能交通領(lǐng)域中動(dòng)態(tài)軌跡點(diǎn)的地圖匹配問(wèn)題，提出并設(shè)計(jì)了一種基于動(dòng)態(tài)規(guī)劃算法的軌跡匹配軟件，并在路網(wǎng)拓?fù)錁?gòu)建、最短路徑計(jì)算方面進(jìn)行改進(jìn)優(yōu)化，提升了軟件工作性能。工程應(yīng)用表明，該軟件具有較好的計(jì)算精度和效率。

關(guān)鍵詞：地圖匹配；GPS軌跡；路網(wǎng)拓?fù)?/p>

中圖分類(lèi)號(hào)：P208 文獻(xiàn)標(biāo)識(shí)碼：A DOI：10.3969/j.issn.1003-6970.2015.05.023

0 引言

智能交通系統(tǒng)（ITS）應(yīng)用越來(lái)越廣泛，常見(jiàn)的包括車(chē)輛導(dǎo)航、交通流量分析、位置服務(wù)（LBS）等。能夠提供位置信息的傳感器主要是安裝在車(chē)輛、手機(jī)等移動(dòng)終端上的GPS設(shè)備。連續(xù)的GPS采樣點(diǎn)就形成了運(yùn)動(dòng)軌跡，由于GPS的采樣精度和頻率、建筑物遮擋等原因，使得軌跡無(wú)法直接與道路網(wǎng)絡(luò)（簡(jiǎn)稱(chēng)“路網(wǎng)”）重合，存在一定誤差。通過(guò)一定算法使得軌跡與數(shù)字地圖中的相應(yīng)道路重合的過(guò)程稱(chēng)為“軌跡匹配”。軌跡匹配的實(shí)現(xiàn)能夠?yàn)檐?chē)輛導(dǎo)航、交通流量實(shí)時(shí)分析、公交線(xiàn)網(wǎng)分析等應(yīng)用提供較大支撐能力。

1 相關(guān)研究

軌跡地圖匹配軟件的核心模塊就是軌跡匹配算法。在軌跡匹配的相關(guān)算法資料中，主要分為局部匹配和全局匹配兩類(lèi)。局部匹配適合于解決在線(xiàn)實(shí)時(shí)應(yīng)用問(wèn)題，全局匹配適合于解決離線(xiàn)應(yīng)用問(wèn)題。

局部匹配算法主要是利用當(dāng)前GPS軌跡點(diǎn)與候選道路幾何關(guān)系及前后相鄰軌跡點(diǎn)的關(guān)聯(lián)信息來(lái)進(jìn)行匹配的。文獻(xiàn)[4]采用軌跡點(diǎn)與道路的方向權(quán)重、軌跡點(diǎn)到道路的距離權(quán)重、歷史信息權(quán)重的綜合來(lái)完成軌跡匹配。然而由于局部匹配算法僅采用區(qū)域范圍內(nèi)的軌跡點(diǎn)信息，所以?xún)H適合于高采樣頻率軌跡的實(shí)時(shí)地圖匹配情況。特別是由于沒(méi)有全面考慮到道路拓?fù)潢P(guān)系，在復(fù)雜路網(wǎng)情況下，容易導(dǎo)致誤匹配。

全局匹配算法主要是利用道路拓?fù)渚W(wǎng)絡(luò)來(lái)匹配整個(gè)GPS軌跡。文獻(xiàn)[5]使用Frechet距離作為權(quán)重來(lái)構(gòu)建拓?fù)渚W(wǎng)絡(luò)圖，采用最短路徑算法得到匹配道路。文獻(xiàn)[6]使用曲線(xiàn)相似度計(jì)算來(lái)進(jìn)行軌跡匹配。然而，全局匹配算法比較明顯問(wèn)題就是算法實(shí)現(xiàn)復(fù)雜、計(jì)算量大，有一定應(yīng)用的局限性。

使用隱馬爾科夫（HMM）等概率統(tǒng)計(jì)算法，以及多假設(shè)技術(shù)（MHT）來(lái)解決軌跡匹配問(wèn)題也是對(duì)匹配算法的重要補(bǔ)充。

本文工作主要是基于動(dòng)態(tài)規(guī)劃的全局匹配算法，設(shè)計(jì)并實(shí)現(xiàn)了一套軟件來(lái)解決離線(xiàn)軌跡匹配的問(wèn)題。

2 軟件構(gòu)成與功能

軌跡地圖匹配軟件主要由路網(wǎng)拓?fù)滠浖偷貓D匹配軟件兩部分組成。

路網(wǎng)拓?fù)滠浖闹饕δ苁腔趯?dǎo)航電子地圖數(shù)據(jù)構(gòu)建道路拓?fù)渚W(wǎng)絡(luò)，為地圖匹配軟件提供路網(wǎng)拓?fù)浣Y(jié)構(gòu)。

主要的工作流程如圖l所示，首先讀取電子地圖數(shù)據(jù)，并可對(duì)數(shù)據(jù)進(jìn)行修改和編輯，然后加載全部路網(wǎng)數(shù)據(jù)，并對(duì)路網(wǎng)數(shù)據(jù)進(jìn)行預(yù)處理（驗(yàn)證數(shù)據(jù)和格式的有效性），基于預(yù)處理后數(shù)據(jù)構(gòu)建路網(wǎng)拓?fù)?，最后?duì)拓?fù)浣Y(jié)構(gòu)進(jìn)行驗(yàn)證，并發(fā)布為路網(wǎng)數(shù)據(jù)。

地圖匹配軟件的主要功能是基于路網(wǎng)拓?fù)鋽?shù)據(jù)完成對(duì)軌跡數(shù)據(jù)的地圖匹配，支持單軌跡匹配及多軌跡批量匹配，并可對(duì)匹配結(jié)果進(jìn)行展示和編輯。

主要工作流程如圖2所示，首先加載軌跡數(shù)據(jù)文件并進(jìn)行初始化，然后對(duì)軌跡數(shù)據(jù)進(jìn)行檢查和重采樣，基于匹配算法進(jìn)行軌跡匹配，可基于地圖實(shí)現(xiàn)結(jié)果展示及編輯，最后進(jìn)行匹配結(jié)果的發(fā)布。

3 關(guān)鍵技術(shù)及算法設(shè)計(jì)

3.1 路網(wǎng)拓?fù)錁?gòu)建

路網(wǎng)拓?fù)錁?gòu)建主要是利用電子地圖中的節(jié)點(diǎn)和線(xiàn)數(shù)據(jù)構(gòu)建拓?fù)浣Y(jié)構(gòu)圖，如圖3所示。路網(wǎng)拓?fù)錁?gòu)建是軌跡匹配前的必要工作，路網(wǎng)拓?fù)涞馁|(zhì)量也對(duì)地圖匹配的效率和準(zhǔn)確性至關(guān)重要。

路網(wǎng)拓?fù)錁?gòu)建的主要步驟包括：數(shù)據(jù)預(yù)處理、數(shù)據(jù)校驗(yàn)、拓?fù)浣?、拓?fù)潋?yàn)證。

數(shù)據(jù)預(yù)處理是根據(jù)道路等級(jí)、可通行等屬性對(duì)道路進(jìn)行過(guò)濾，以減少道路數(shù)量，提升查詢(xún)和搜索效率。

數(shù)據(jù)校驗(yàn)主要進(jìn)行剔除未與道路連接的節(jié)點(diǎn)、邊界道路補(bǔ)點(diǎn)、以及圖幅拼接問(wèn)題，從而保證路網(wǎng)數(shù)據(jù)的完整性和一致性。