成劍波 鄭玉甫*

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

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

1 改進(jìn)Dijkstra 算法

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

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

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

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

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

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

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

圖1 鄰接矩陣

2.2 速度矩陣模型

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

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

表1 整理后的歷史速度表

2.2.2 速度矩陣模型

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

圖2 不同時(shí)間段的速度矩陣

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

為了接近真實(shí)環(huán)境，生成的路網(wǎng)拓?fù)淠Ｐ团c真實(shí)環(huán)境比例為1:8，設(shè)zi={z1,z2,z3,……z55}為55 個(gè)道路節(jié)點(diǎn)集合，xi={x101,x102,z103……,x299}為隨機(jī)道路撒點(diǎn)餐廳。道路網(wǎng)拓?fù)淠Ｐ鸵胨俣饶Ｐ秃?，在?jié)點(diǎn)間的線路上添加了不同時(shí)段的速度值?？梢酝ㄟ^速度計(jì)算出不同時(shí)間段的所用時(shí)間。表2 為節(jié)點(diǎn)1 至節(jié)點(diǎn)11 之間的路徑數(shù)據(jù)圖，其中第4 列至第11 列為各時(shí)間段對(duì)應(yīng)的速度。

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

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

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

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

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

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

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

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

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

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

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

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

3.3 算法性能

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

圖5 改進(jìn)Dijkstra 算法在不同規(guī)模的運(yùn)行時(shí)間

4 結(jié)論

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