包含中間地址的導航路徑算法

成劍波 鄭玉甫*

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

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

1 改進Dijkstra 算法

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

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

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

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

2 路徑導航建模

2.1 數據預處理

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

圖1 鄰接矩陣

2.2 速度矩陣模型

2.2.1 車速數據獲取和處理

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

表1 整理后的歷史速度表

2.2.2 速度矩陣模型

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

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

3 包含中間地址的導航路徑算法

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

表2 路徑數據圖

3.1 模擬單一路徑區間

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

圖3 單一路徑區間

表3 單一路徑規劃點和相應時間

3.2 模擬多條路徑區間

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

圖4 多條路徑區間

表4 為3 條路徑的權重值比較，其中總距離相同，在設定的時間段內的用時不同，區間內餐廳數量不同，由權重值比較得出第3 條路徑權重值最小。

表4 3 條路徑的權重值比較

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

表5 多條路徑規劃點和相應時間

3.3 算法性能

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

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

4 結論

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