楊 莉，周志富

(山西大同大學(xué)工學(xué)院，山西大同037003)

最優(yōu)路徑查詢的研究與實(shí)現(xiàn)

楊 莉，周志富

(山西大同大學(xué)工學(xué)院，山西大同037003)

車輛導(dǎo)航正成為現(xiàn)代交通的一種服務(wù)趨勢，而其中重要的、必不可少的一部分就是最優(yōu)路徑的查詢.對最優(yōu)路徑查詢的原理、數(shù)據(jù)組織、數(shù)據(jù)結(jié)構(gòu)和查詢算法進(jìn)行了研究，然后利用實(shí)驗(yàn)數(shù)據(jù)，實(shí)現(xiàn)了最優(yōu)路徑查詢功能，證實(shí)了實(shí)現(xiàn)最優(yōu)路徑查詢的方法是有效的.

最優(yōu)路徑查詢 ARC-NODE結(jié)構(gòu) 啟發(fā)式算法

隨著城市道路系統(tǒng)日益增加及復(fù)雜，自駕車的數(shù)量和困難也隨之增加，車輛導(dǎo)航成為一種重要的服務(wù)手段，因而導(dǎo)航地圖日漸成為現(xiàn)代交通中的一個(gè)重要部分，而其中最優(yōu)路徑查詢功能又是其核心，因此，研究最優(yōu)路徑查詢的實(shí)現(xiàn)對于車輛導(dǎo)航具有重要的現(xiàn)實(shí)意義，同時(shí)該產(chǎn)業(yè)也具有巨大的經(jīng)濟(jì)前景.

目前，國外在導(dǎo)航方面做得已經(jīng)比較成熟，相比之下，我國還有一定的差距，不論是數(shù)據(jù)庫建立還是實(shí)際應(yīng)用研究都還不夠，市場上的專門公司也較少，產(chǎn)品僅處于推廣階段.

1 最優(yōu)路徑查詢原理

最優(yōu)路徑查詢，如距離最短或時(shí)間最短或費(fèi)用最低的路徑查詢是車載導(dǎo)航系統(tǒng)中常見的一種查詢方式.一般是通過輸入目的地而得到想要的最優(yōu)路線，車輛在導(dǎo)航系統(tǒng)的輔助下，能夠盡快到達(dá)目的地.該查詢最終落實(shí)到對地圖數(shù)據(jù)庫的檢索，即根據(jù)給定條件確定相應(yīng)地物集合的數(shù)據(jù)庫邏輯地址.對于最優(yōu)路徑查詢來說主要就是對道路信息數(shù)據(jù)的檢索，車輛在行進(jìn)中，借助GPS衛(wèi)星提供的定位數(shù)據(jù)，將車輛現(xiàn)在的位置反映到導(dǎo)航地圖中，一旦指定了目的地后，系統(tǒng)在后臺進(jìn)行包含這兩個(gè)特殊位置的圖搜索，即將復(fù)雜的道路網(wǎng)轉(zhuǎn)換為數(shù)學(xué)意義上的圖，這樣就可借助圖搜索算法找到一條滿足用戶要求的最優(yōu)路徑，車輛借助衛(wèi)星導(dǎo)航系統(tǒng)和慣性導(dǎo)航儀就可以較快地到達(dá)目的地.其中搜索數(shù)據(jù)庫的過程中需要將結(jié)果的數(shù)據(jù)庫坐標(biāo)轉(zhuǎn)化為用戶坐標(biāo)，提交給用戶[1].該過程涉及到坐標(biāo)系統(tǒng)的轉(zhuǎn)換，圖搜索算法的高效運(yùn)行和地圖匹配等問題，但核心是圖搜索算法的高效運(yùn)行.

2 數(shù)據(jù)的組織

在美國，NavTech為許多主要城市區(qū)域提供可用的導(dǎo)航數(shù)據(jù)庫.數(shù)據(jù)庫中的信息包括道路網(wǎng)幾何形狀、道路等級、道路特征 (如方向性)、轉(zhuǎn)彎和限制、制圖和地理政治邊界、感興趣的點(diǎn)、路標(biāo)和服務(wù)設(shè)施[2].這對我們建立最優(yōu)路徑查詢用的數(shù)據(jù)庫具有很好的參考價(jià)值.

數(shù)據(jù)結(jié)構(gòu)方面，ARC-NODE結(jié)構(gòu)能表示完整的矢量弧段-結(jié)點(diǎn)拓?fù)潢P(guān)系，每個(gè)地物用一個(gè)編碼標(biāo)識置于選定的位置，地物的屬性存儲于關(guān)系表中，它非常適合路網(wǎng)的表示，我們可以將路網(wǎng)抽象為點(diǎn)和線組成的網(wǎng)，將一條路分割為幾段，每段表示為一條線，線間接點(diǎn)及道路交叉口可用點(diǎn)表示，而這些點(diǎn)和線的屬性信息可以存儲在關(guān)系表中，反映連通性和方向性，這樣即儲存了主要的交通信息，又表示出了路段間的拓?fù)潢P(guān)系，將復(fù)雜的道路網(wǎng)表示成數(shù)學(xué)意義上的一個(gè)圖，該圖可以是有向的，還可以是被賦權(quán)的，從而作為車輛導(dǎo)航系統(tǒng)核心技術(shù)確定某兩地間的最優(yōu)行駛路線問題便可以轉(zhuǎn)化為在賦權(quán)圖上求兩點(diǎn)間的最短路徑問題[3].

3 最優(yōu)路徑查詢算法

傳統(tǒng)Dijstra[4]算法是一種按路徑長度遞增的順序產(chǎn)生最短路徑的方法,是尋找最短路徑的傳統(tǒng)方法.它把所有結(jié)點(diǎn)分成兩組，OPEN表存儲已經(jīng)產(chǎn)生但還沒擴(kuò)展的結(jié)點(diǎn)，CLOSED表存儲已經(jīng)擴(kuò)展的結(jié)點(diǎn) (最短路徑點(diǎn))，按最短路徑長度遞增的順序，逐個(gè)把OPEN表的結(jié)點(diǎn)加到CLOSED表中，直到從圖中第一個(gè)結(jié)點(diǎn)出發(fā)可以到達(dá)的所有結(jié)點(diǎn)都已經(jīng)包括在CLOSED表中，在該過程中，總保持從第一個(gè)結(jié)點(diǎn)到CLOSED表各結(jié)點(diǎn)的最短路徑都不大于從第一個(gè)結(jié)點(diǎn)到OPEN表的任何結(jié)點(diǎn)的最短路徑長度.此外，每個(gè)結(jié)點(diǎn)對應(yīng)一個(gè)距離值，CLOSED表的結(jié)點(diǎn)對應(yīng)的距離就是從第一個(gè)結(jié)點(diǎn)到此結(jié)點(diǎn)的只包括CLOSED表的結(jié)點(diǎn)為中間結(jié)點(diǎn)的最短路徑長度，OPEN表的結(jié)點(diǎn)對應(yīng)的距離值是從第一個(gè)結(jié)點(diǎn)到此結(jié)點(diǎn)的只包括CLOSED表的結(jié)點(diǎn)為中間結(jié)點(diǎn)的最短路徑長度.該算法能得到最短路徑的最優(yōu)解，但由于它遍歷的結(jié)點(diǎn)很多，所以效率低.不能滿足導(dǎo)航快速反饋的要求，一種解決方法是采用啟發(fā)式算法A*提高其效率，即提供一個(gè)結(jié)點(diǎn)距離目標(biāo)點(diǎn)有多遠(yuǎn)的估計(jì)，以使搜索算法優(yōu)先考慮最有希望的結(jié)點(diǎn).對每個(gè)結(jié)點(diǎn)定義一個(gè)估價(jià)函數(shù)，A*[5]算法優(yōu)先搜索具有最小估價(jià)函數(shù)值的結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)的估價(jià)函數(shù)值為從原點(diǎn)到當(dāng)前結(jié)點(diǎn)的實(shí)際距離與當(dāng)前結(jié)點(diǎn)到目標(biāo)結(jié)點(diǎn)的最短距離之和.

實(shí)際中最優(yōu)路徑還可以是時(shí)間最短或費(fèi)用最低的路徑，操作起來和搜索距離最短路徑是原理一樣，只是各個(gè)結(jié)點(diǎn)上的距離變成時(shí)間或費(fèi)用.

4 實(shí)驗(yàn)

獲取某市矢量地圖，確保投影為經(jīng)緯度投影，坐標(biāo)系為WGS84的，符合車載電子地圖服務(wù)系統(tǒng)的要求.保留河流、建筑物、綠地等基礎(chǔ)信息圖層.下面按照前面介紹的數(shù)據(jù)組織策略存儲數(shù)據(jù).

為滿足路徑信息的查詢，采用ARC-NODE結(jié)構(gòu)建立了道路信息數(shù)據(jù)庫，存儲內(nèi)容為：道路類型(首級道路標(biāo)記為1，次級道路標(biāo)記為2)、道路名稱、路段的起始點(diǎn)標(biāo)記、路段的長度、路段起止點(diǎn)的標(biāo)志、估計(jì)的行車時(shí)間 (利用路程除以平均速度得到)這些信息.道路信息表存儲道路圖層中各個(gè)路段結(jié)點(diǎn)的坐標(biāo)和代碼.具體如表1、表2所示.

對組織好的數(shù)據(jù)，應(yīng)用前面介紹的A*算法，實(shí)現(xiàn)了小范圍內(nèi)的距離最短和時(shí)間最短的最優(yōu)路徑查詢，結(jié)果如圖1、圖2所示.圖1中指定起始位置和目的地后，給出最短行車距離為4.79km的路線為：保健街-求真路-建設(shè)路-興勝街-前進(jìn)路-愛國街-中華路-人民大街-八一路-工業(yè)街-東風(fēng)路-東環(huán)路.圖2中指定起始位置和目的地后，給出估計(jì)的行車時(shí)間為5.73 min，具體路線為：保健街-求真路-興勝街-前進(jìn)路-常青街.

對于大范圍、大數(shù)據(jù)量的最優(yōu)路徑查詢時(shí)，對數(shù)據(jù)的組織還會應(yīng)用到分尺度、分區(qū)域、地圖分幅組織及索引等策略，并注意到地圖匹配等問題，鑒于本文的實(shí)驗(yàn)數(shù)據(jù)量小、范圍小，因此沒有進(jìn)行這些方面的研究.

表1 道路關(guān)系表

表2 道路信息表

5 結(jié)論

本文針對導(dǎo)航服務(wù)中的最優(yōu)路徑查詢功能，進(jìn)行了一系列理論研究，后采用ARC-NODE結(jié)構(gòu)、對實(shí)驗(yàn)數(shù)據(jù)進(jìn)行了合理的分層和組織及處理，采用啟發(fā)式Dijstra算法或A*算法，最終實(shí)現(xiàn)了小范圍內(nèi)的最優(yōu)路徑查詢功能.大范圍、大數(shù)據(jù)量的最優(yōu)路徑查詢還有許多問題有待進(jìn)一步研究.

圖1 距離最短路徑查詢

圖2 時(shí)間最短路徑查詢

[1]毋河海.地圖數(shù)據(jù)庫系統(tǒng)[M].北京：測繪出版社,1991.

[2]蔣捷，韓剛，陳軍.導(dǎo)航地理數(shù)據(jù)庫[M].北京:科學(xué)出版社,2003.

[3]楊長保,于銀輝.基于VC++的ARC/INFO集成二次開發(fā)[J].吉林大學(xué)學(xué)報(bào)：科學(xué)信息版,2003,21(2):162-166.

[4]唐策善，立龍澎，黃劉生.數(shù)據(jù)結(jié)構(gòu)-用C語言描述[M].北京：高等教育出版社,2002.

[5]LEE TIAN SZE,TAN KAR ENG.Vehicle navigation and route guidance[D].Nan yang Technological University:School of electrical and electronic engineering,2002.

Abstract:Vehical navigation is becoming a serving trend in modern traffic and the important and the necessary part is the optimal rout query.It did some research on the principle of the optimal rout query,data organization,data structure and query algorithm. Then it realizes the optimal rout query using the experimental data.The result confirms the effectiveness of the method of the optimal rout query realized in the paper.

Key words:The Optimal Rout Query;ARC-NODE structure;Heuristics Algorithm

〔編輯 高?！?/p>

Research and Realization of the Optimal Route Query

YANG Li,ZHOU Zhi-fu
(School of Engineering,Shanxi Datong University,Datong Shanxi,037003)

P28

A

1674-0874(2010)05-0023-03

2010-04-20

楊莉(1983-)，女，河北安國人，碩士，助教，研究方向：地理信息系統(tǒng).