包含中間地址的導(dǎo)航路徑算法

成劍波 鄭玉甫*

（蘭州交通大學(xué)電子與信息工程學(xué)院，甘肅 蘭州 730070）

迪杰斯特拉算法（Dijkstra）由荷蘭計算機科學(xué)家迪杰斯特拉[1]提出的，其目的是解決有權(quán)圖中最短路徑的問題。算法的核心是從起點開始，采用貪心算法的策略，每次遍歷距離起點最近且未訪問過的頂點的鄰接節(jié)點，直到擴展到終點為止[2]。Dijkstra 算法對最短路徑的研究有很多。對于真實道路的問題，黃書力等[3]提出利用指定的中間節(jié)點集，分別取得連通3 個子集的局部最短路徑，從而形成全局待選最短路徑，最后通過篩選得到目標路徑。該算法只考慮了節(jié)點間最短路徑規(guī)劃，未考慮到實際的道路狀況。馮豪杰等[4]提出引入道路多限制因子計算最優(yōu)路徑，將道路設(shè)計的標定參數(shù)作為限制因子而非動態(tài)的道路情況，其實驗結(jié)果針對實際道路時數(shù)據(jù)將存在偏差。以上采用的是傳統(tǒng)Dijkstra 算法，考慮了時間、速度等因素，只針對確定起始點、終點或中間點的路徑規(guī)劃，存在一定的局限性。目前針對用戶的使用習(xí)慣，比如行駛途中需要就餐的問題，更多的是停車重新規(guī)劃路線，這為駕駛安全帶來隱患與不便[5]。因此本研究在此基礎(chǔ)上考慮了將路徑中的一點作為中間點進行規(guī)劃，提出包含中間地址的導(dǎo)航路徑算法，用戶在設(shè)定導(dǎo)航路線時的預(yù)估時間若包含了就餐時間，則為用戶確定路徑區(qū)間內(nèi)符合條件的餐廳作為中間地址，生成起始地、中間地址和目的地的導(dǎo)航路徑。

1 改進Dijkstra 算法

傳統(tǒng)Dijkstra 算法是通過遍歷所有的點來比較找出最近的點，存在較高的時間成本。因此引入優(yōu)先隊列來對Dijkstra 算法進行優(yōu)化，堆優(yōu)化的主要思想是使用一個優(yōu)先隊列來代替最近距離的查找，這樣可以大幅度節(jié)約時間成本[6]。將優(yōu)先隊列定義為最小堆，把起始點的距離初始為0 加入該優(yōu)先隊列中，從起始點開始擴展，更新所有到達的點距離起始點最近的距離。如果起始點到z 點的距離比起始點先到ver 點再從ver 點到zj點的距離大，更新dist[o,zi]，使得dist[o,zi]到起始點的距離最短，并將該點到起始點的距離以及該點的編號(0,dist[o,zj])存入優(yōu)先隊列中，表示該點是確定的最短距離。改進Dijkstra 算法只能求得最短路徑，在路徑導(dǎo)航中還要考慮速度等因素。為此引入速度模型，主要表現(xiàn)在同一路徑不同時間段的速度不同，以還原真實路徑情況。具體描述：G 為有權(quán)無向圖，集合Z 為節(jié)點集，集合N 為節(jié)點間線段集，則對應(yīng)的N 中所有線段的距離矩陣F={f}，fij表示線段f(i,j)的距離，表達式為

其中inf 為極大值，表示不互通；lij表示節(jié)點間的長度值。為了實現(xiàn)不同時間段的車輛速度，導(dǎo)入歷史綜合數(shù)據(jù)生成同一時刻的歷史速度矩陣。按照180min 一組對應(yīng)一個速度矩陣，以0 點開始，每180min 劃分一組，共8組:T1～T8。設(shè)線段f(i,j)在每一組[Tk-1,Tk)的速度為Vkij，k 為T1～T8的8 個時間段。線段f(i,j)不同時間段的行駛時間tkij為

本算法在求得最短路徑后能計算出相應(yīng)的所需時間，根據(jù)不同時間段所得的路徑時間也不同。若所求最短路徑有多條線路，在獲取多條預(yù)選路徑后，引入權(quán)重判決來選取最優(yōu)路徑。依據(jù)時間值、長度和收費這些參數(shù)來進行權(quán)重比對，從而選擇一個最優(yōu)的路徑區(qū)間作為第一路徑區(qū)間。計算多條預(yù)選路徑中每條路徑的權(quán)重值公式為

其中，Qi表示第i 條路徑的權(quán)重值，i 為多條預(yù)選路徑的編號，Di表示第i 條路徑的時間值，Li表示第i 條路徑的距離值，Si表示第i 條路徑的收費值（如高速收費金額），Xi表示第i 條路徑對應(yīng)的預(yù)設(shè)路徑區(qū)間中在設(shè)定范圍內(nèi)餐廳的數(shù)量，D 表示多條路徑的時間平均值，X 表示多條路徑的距離平均值，S 表示多條路徑的收費平均值，X 表示多條路徑對應(yīng)的預(yù)設(shè)路徑區(qū)間中在設(shè)定范圍內(nèi)餐廳的數(shù)量平均值。

2 路徑導(dǎo)航建模

2.1 數(shù)據(jù)預(yù)處理

將道路數(shù)據(jù)中節(jié)點和邊的數(shù)據(jù)以鄰接矩陣的形式進行存儲。圖1 為鄰接矩陣P，用于存儲各節(jié)點之間的距離值。對于鄰接矩陣的元素，1 表示節(jié)點i 可以連通節(jié)點j；inf 為計算機所允許的極大值，表示節(jié)點i 與節(jié)點j 不互通。

圖1 鄰接矩陣

2.2 速度矩陣模型

2.2.1 車速數(shù)據(jù)獲取和處理

高德地圖的交通詳情數(shù)據(jù)為實時數(shù)據(jù)，通過請求動態(tài)爬取頁面獲得每日不同時間點的速度值，并儲存在相應(yīng)文件中。根據(jù)需求篩選出所需路段的數(shù)據(jù)及其對應(yīng)時間段，整理成當(dāng)日所需路段不同時間段的平均速度列表，數(shù)據(jù)格式見表1。

表1 整理后的歷史速度表

2.2.2 速度矩陣模型

將7 日的數(shù)據(jù)從0 點開始按180min 一組求平均得到歷史速度，節(jié)點和邊的速度數(shù)據(jù)以速度模型矩陣進行存儲，其中k 表示劃分的8 個時間段，vk(i,j)表示節(jié)點i 至節(jié)點j 在k 時段的速度值。圖2 為k=4 的部分速度值。

圖2 不同時間段的速度矩陣

3 包含中間地址的導(dǎo)航路徑算法

為了接近真實環(huán)境，生成的路網(wǎng)拓撲模型與真實環(huán)境比例為1:8，設(shè)zi={z1,z2,z3,……z55}為55 個道路節(jié)點集合，xi={x101,x102,z103……,x299}為隨機道路撒點餐廳。道路網(wǎng)拓撲模型引入速度模型后，在節(jié)點間的線路上添加了不同時段的速度值。可以通過速度計算出不同時間段的所用時間。表2 為節(jié)點1 至節(jié)點11 之間的路徑數(shù)據(jù)圖，其中第4 列至第11 列為各時間段對應(yīng)的速度。

表2 路徑數(shù)據(jù)圖

3.1 模擬單一路徑區(qū)間

輸入起始點和終點，生成起始點到終點的最短路徑。根據(jù)時間需求，確定就餐的第一路徑區(qū)間，并列出該區(qū)間內(nèi)的餐廳點位，選擇算法后在原有路徑中添加中間點重新計算從起始點到中間地址、從中間地址到終點的最短路徑以及路徑時間。圖3 為單一路徑區(qū)間，選擇時間段，設(shè)定起始點為1，終點為50。生成最短路徑后，根據(jù)設(shè)定的時間，在該路徑從起始點起708 至748 的距離作為就餐的第一路徑區(qū)間，隨機選取103 點作為餐廳中間地址，生成起始點為1，終點為50，中間途經(jīng)103 的最短路徑。在確定就餐的第一路徑區(qū)間后，默認選擇餐廳點位作為中間地址的時間為2s。表3 為確定中間地址前后的路徑規(guī)劃點和相應(yīng)時間。

圖3 單一路徑區(qū)間

表3 單一路徑規(guī)劃點和相應(yīng)時間

3.2 模擬多條路徑區(qū)間

多條路徑區(qū)間是生成最短距離相同的多條路徑。引入速度模型后，路徑在不同時間的速度不同，時間存在差異。根據(jù)時間需求，確定每條線路對應(yīng)的第一路徑區(qū)間，并計算出每條路徑的時間和區(qū)間內(nèi)餐廳數(shù)量，根據(jù)權(quán)重值比較選擇權(quán)重值最小的作為最優(yōu)路徑，選擇算法后在最優(yōu)路徑中添加中間點重新計算從起始點到中間地址、從中間地址到終點的最短路徑和路徑時間。圖4 為多條路徑區(qū)間，選擇T5 時間段,設(shè)定起始點為1，終點為46，生成3 條距離相同的最短路徑，根據(jù)設(shè)定的時間得到每條路徑的第一路徑區(qū)間，并列出區(qū)間內(nèi)的餐廳點位。

圖4 多條路徑區(qū)間

表4 為3 條路徑的權(quán)重值比較，其中總距離相同，在設(shè)定的時間段內(nèi)的用時不同，區(qū)間內(nèi)餐廳數(shù)量不同，由權(quán)重值比較得出第3 條路徑權(quán)重值最小。

表4 3 條路徑的權(quán)重值比較

表5 為確定中間地址前后的路徑規(guī)劃點和時間。選取第3 條路徑中的307 作為餐廳中間地址，生成起始點為1，終點為46，中間途經(jīng)307 的最短路徑。同單一路徑區(qū)間，在確認中間地址時的時間默認為2s。

表5 多條路徑規(guī)劃點和相應(yīng)時間

3.3 算法性能

時間復(fù)雜度是評價算法的性能指標。在一個算法中語句執(zhí)行次數(shù)記為T(n)，n 為問題的規(guī)模，當(dāng)n 不斷變化時，T(n)也會不斷變化。順序遍歷集合的傳統(tǒng)Dijkstra 算法的時間復(fù)雜度為O (n2)；使用優(yōu)先隊列的堆優(yōu)化Dijkstra 算法的時間復(fù)雜度為O(mlogn)，其中m 為邊數(shù)，n為節(jié)點個數(shù)。輸入的節(jié)點規(guī)模從1 至200 的運行時間見圖5。隨著數(shù)據(jù)規(guī)模的遞增，改進的堆優(yōu)化Dijkstra 算法與Dijkstra 算法相比，耗時更低。這也印證了堆優(yōu)化Dijkstra 算法的時間復(fù)雜度優(yōu)于Dijkstra 算法的時間復(fù)雜度，證明了算法的有效性。

圖5 改進Dijkstra 算法在不同規(guī)模的運行時間

4 結(jié)論

堆優(yōu)化改進Dijkstra 算法實現(xiàn)了包含中間地址的路徑導(dǎo)航方法，考慮到真實情況，在Matlab 中建立道路網(wǎng)拓撲模型，并引入速度模型，在生成最短路徑的同時生成所用時間，并驗證算法能有效降低時間復(fù)雜度。該方法能實現(xiàn)在原有路徑導(dǎo)航中根據(jù)需求添加中間點生成包含中間地址的導(dǎo)航路徑，能有效提高路徑導(dǎo)航的使用效率，為駕駛帶來極大的安全性。此外，該方法有著廣泛的應(yīng)用前景，如充電站，引入更多的參數(shù)能夠?qū)崿F(xiàn)長途多次充電時間與距離的最優(yōu)解，因此還需進一步探索。