基于改進(jìn)Dijkstra的應(yīng)急指揮車(chē)及時(shí)救援的最短路徑算法的研究

王先全 周錫祥 余浩源 李浩 王向雨

摘要：隨著人們自駕出游的頻率逐步提高，城市交通擁擠堵塞的情況時(shí)常出現(xiàn)，給應(yīng)急指揮車(chē)的救援帶來(lái)諸多不便，為使應(yīng)急指揮車(chē)能夠機(jī)動(dòng)靈活地深入城市各個(gè)角落，及時(shí)有效解決各類(lèi)突發(fā)事故，通過(guò)ArcMap以城市交通道路為源構(gòu)建了網(wǎng)絡(luò)數(shù)據(jù)集，將城市交通道路網(wǎng)抽象為圖的結(jié)構(gòu)，使用鄰接表以及二叉排序樹(shù)結(jié)構(gòu)對(duì)傳統(tǒng)Dijkstra算法進(jìn)行了改進(jìn)，并基于改進(jìn)后的Dijkstra算法，采用ArcGIS Engine、Visual Studio等工具開(kāi)發(fā)了應(yīng)急指揮車(chē)最短路徑規(guī)劃軟件，實(shí)現(xiàn)了應(yīng)急指揮車(chē)最短路徑的規(guī)劃。

關(guān)鍵詞：城市交通;應(yīng)急指揮車(chē);鄰接表;二叉排序樹(shù);Dijkstra

中圖分類(lèi)號(hào)：U412? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2021）14-0001-03

Abstract： As people gradually increase the frequency， drive travel city traffic jam often appear， to bring inconvenience， emergency command vehicle rescue emergency command vehicle can be flexible in order to make into all corners of the city， the timely and effective to solve all kinds of accidents， by ArcMap for urban traffic source network data set is constructed， the urban traffic road network abstraction for figure structure， using adjacency list and binary sort tree structure of the traditional Dijkstra algorithm is optimized， and the Dijkstra algorithm based on the optimized， The shortest path planning software of emergency command vehicle is developed by using ArcGIS Engine， Visual Studio and other tools， and the shortest path planning of emergency command vehicle is realized.

Key words： the urban traffic; emergency command vehicle; adjacency list; binary sort tree; Dijkstra

1 背景

為了處理自然災(zāi)害、火災(zāi)、安全生產(chǎn)等各種事故，政府相關(guān)部門(mén)必須裝備應(yīng)急指揮車(chē)[1]。應(yīng)急指揮車(chē)是處置各突發(fā)事件的現(xiàn)場(chǎng)機(jī)動(dòng)指揮中心，能夠機(jī)動(dòng)靈活地深入城市各個(gè)角落，及時(shí)有效地解決各類(lèi)突發(fā)事件[2]。應(yīng)急指揮車(chē)在第一時(shí)間到達(dá)事發(fā)地點(diǎn)，需要規(guī)劃出一條最短路徑。最短路徑不僅指距離最短，還通常引申到費(fèi)用、時(shí)間等度量，相應(yīng)地，最短路徑問(wèn)題便轉(zhuǎn)變?yōu)樽畹唾M(fèi)用問(wèn)題、最短時(shí)間問(wèn)題[3]。本文研究的是最短時(shí)間問(wèn)題。影響時(shí)間的因素很多，需要綜合考慮距離、道路交叉點(diǎn)數(shù)、路況、交通擁擠程度等因素，為應(yīng)急指揮車(chē)規(guī)劃出一條耗時(shí)最少的路徑。本文優(yōu)化了Dijkstra算法，采用ArcGIS Engine、Visual Studio等工具開(kāi)發(fā)應(yīng)急指揮車(chē)最短路徑規(guī)劃軟件，實(shí)現(xiàn)了基于Dijkstra算法優(yōu)化的應(yīng)急指揮車(chē)的最短路徑的規(guī)劃。

2 建立網(wǎng)絡(luò)模型

城市交通主要由眾多的街道相連、相交而構(gòu)成，并且組成錯(cuò)綜復(fù)雜、縱橫交錯(cuò)的城市交通道路網(wǎng)[4]。本文通過(guò)ArcGIS的網(wǎng)絡(luò)數(shù)據(jù)集工具在道路的每個(gè)交叉口處進(jìn)行打斷處理，整個(gè)交通道路網(wǎng)便由交叉路口以及路段構(gòu)成，將交通網(wǎng)中道路的交叉點(diǎn)抽象為圖中的結(jié)點(diǎn)，路段抽象為圖中的弧段[5]，以此建立如圖1所示的城市交通道路網(wǎng)絡(luò)模型。

式中：[ RN]表示城市交通道路網(wǎng)絡(luò);N表示網(wǎng)絡(luò)中的結(jié)點(diǎn)集合;R表示網(wǎng)絡(luò)中的路段集合，其元素為有序?qū)（x，y）]，[（x，y）]表示結(jié)點(diǎn)[x]與結(jié)點(diǎn)[y]之間存在一條有向通路，[ lxy]表示結(jié)點(diǎn)[x]與結(jié)點(diǎn)[y]之間的路段的加權(quán)長(zhǎng)度[7]。路段的加權(quán)長(zhǎng)度是綜合考慮多個(gè)因素后求解所得到的長(zhǎng)度，包括路徑長(zhǎng)度，路況、交通擁擠程度等因素。

3 傳統(tǒng)Dijkstra算法

3.1 Dijkstra算法描述

Dijkstra算法是在1959年由荷蘭計(jì)算機(jī)科學(xué)家E.W.Dijkstra提出的圖論中求最短路徑的常用算法[8]。它適用于單源的最短路徑規(guī)劃問(wèn)題，即求出圖中一點(diǎn)到其余任一頂點(diǎn)的最短路徑[9]。它的主要思想為：將圖中所有結(jié)點(diǎn)分為兩組，第一組為已求出到起始點(diǎn)的最短路徑的結(jié)點(diǎn)集合，用Y表示，初始時(shí)Y中僅有起始點(diǎn)一個(gè)元素，之后每求得一條某頂點(diǎn)到起始點(diǎn)的最短路徑，就將該頂點(diǎn)加入Y集合，直到目標(biāo)點(diǎn)或者圖中所有結(jié)點(diǎn)加入Y中，算法便結(jié)束了;第二組為其余未確定最短路徑的結(jié)點(diǎn)集合，用S表示，按照最短路徑長(zhǎng)度的遞增次序依次把S中的結(jié)點(diǎn)加入Y集合，在加入的過(guò)程中，總保持從起始點(diǎn)到Y(jié)集合各結(jié)點(diǎn)的最短路徑長(zhǎng)度不大于從起始點(diǎn)到S集合任何結(jié)點(diǎn)的最短路徑長(zhǎng)度[10]。

3.2 Dijkstra算法實(shí)現(xiàn)步驟

算法中需要用到四個(gè)輔助數(shù)組來(lái)存放數(shù)據(jù)，第一個(gè)為布爾類(lèi)型的Status[]數(shù)組，同來(lái)保存結(jié)點(diǎn)的當(dāng)前狀態(tài)，若為T(mén)URE，則表示該結(jié)點(diǎn)已經(jīng)加入Y集合中，若為FALSE，則表示該結(jié)點(diǎn)還屬于S集合，第二個(gè)為浮點(diǎn)類(lèi)型的Dis[]數(shù)組，用來(lái)存放圖中各個(gè)結(jié)點(diǎn)到起始點(diǎn)的加權(quán)長(zhǎng)度，第三個(gè)為整數(shù)類(lèi)型的Path[]數(shù)組，用來(lái)存儲(chǔ)最短路徑上該結(jié)點(diǎn)前一個(gè)結(jié)點(diǎn)的序號(hào)，以上三個(gè)數(shù)組的大小均等于結(jié)點(diǎn)的數(shù)量，第四個(gè)數(shù)組是一個(gè)浮點(diǎn)類(lèi)型的二維數(shù)組，命名為Matrix，作用與鄰接矩陣相同，用來(lái)保存各個(gè)結(jié)點(diǎn)到其余結(jié)點(diǎn)的加權(quán)長(zhǎng)度，若兩結(jié)點(diǎn)之間不存在有向通路，則存入數(shù)組的值為無(wú)窮大∞，表示兩結(jié)點(diǎn)不相連，該二維數(shù)組的行數(shù)和列數(shù)均為結(jié)點(diǎn)的數(shù)量。圖2所示為Dijkstra算法的實(shí)現(xiàn)過(guò)程。

1）初始化四個(gè)輔助數(shù)組，循環(huán)給數(shù)組賦初始值，將城市交通道路網(wǎng)中的道路的加權(quán)長(zhǎng)度裝入Matrix數(shù)組。

2）得到起點(diǎn)的序號(hào)j，令Status[j]=TRUE，將起點(diǎn)的狀態(tài)由未標(biāo)記狀態(tài)修改為已標(biāo)記狀態(tài)。

3）通過(guò)循環(huán)查詢(xún)Dis[]數(shù)組，找到S集合中距離Y集合結(jié)點(diǎn)加權(quán)長(zhǎng)度最短的結(jié)點(diǎn)k。

4）將結(jié)點(diǎn)k加入Y集合。

5）更新結(jié)點(diǎn)k狀態(tài)修改后各數(shù)組的值。

6）重復(fù)步驟3）-5），直到將目標(biāo)結(jié)點(diǎn)或者圖中所有結(jié)點(diǎn)加入Y集合，才結(jié)束算法。

7）通過(guò)循環(huán)查找Path[]數(shù)組，便能夠獲得該最短路徑經(jīng)過(guò)的所有結(jié)點(diǎn)的序號(hào)，如此便成功規(guī)劃出最短路徑。

為方便理解，以圖3所示的路徑結(jié)點(diǎn)網(wǎng)絡(luò)為例，規(guī)劃結(jié)點(diǎn)A到結(jié)點(diǎn)E的最短路徑，其步驟為：

1）將起始點(diǎn)A加入Y集合，計(jì)算Y集合到T集合中各點(diǎn)（B、C、D、E）的距離，將值儲(chǔ)存到Dis[]數(shù)組和Path[]數(shù)組中，如表1所示，并通過(guò)Dis[]數(shù)組找到最鄰近點(diǎn)B。

2）將結(jié)點(diǎn)B加入Y集合，重新計(jì)算距離，更新Dis[]數(shù)組和Path[]數(shù)組的值，如表2所示，并從S集合中找到最鄰近點(diǎn)D。

3）將結(jié)點(diǎn)D加入Y集合，得到如表3所示的Dis[]數(shù)組和Path[]數(shù)組的值，查找Dis[]數(shù)組，找到最鄰近點(diǎn)C。

4）將C加入Y集合，再次更新Dis[]數(shù)組和Path[]數(shù)組的值，如表4所示，找到最鄰近點(diǎn)E。

5）將目標(biāo)點(diǎn)E加入Y集合，通過(guò)循環(huán)查找Path[]數(shù)組，便能得到從A到E的最短路徑：A→B→D→C→E。

傳統(tǒng)的Dijkstra算法雖然能成功實(shí)現(xiàn)最短路徑的規(guī)劃，但不論是時(shí)間復(fù)雜度，還是空間復(fù)雜度，都是o（N2）（N表示結(jié)點(diǎn)數(shù)量），隨著結(jié)點(diǎn)數(shù)量的增加，占用的計(jì)算機(jī)存儲(chǔ)空間和算法運(yùn)行時(shí)間都成指數(shù)形勢(shì)的增長(zhǎng)，故需要在傳統(tǒng)的Dijkstra基礎(chǔ)上進(jìn)行優(yōu)化。

4 Dijkstra算法優(yōu)化

4.1 存儲(chǔ)方式優(yōu)化

表示圖最簡(jiǎn)單的方法就是使用二維數(shù)組，稱(chēng)為鄰接矩陣表示法，對(duì)于任意兩個(gè)結(jié)點(diǎn)[x]，[y]，若[x]與[y]之間存在通路，則置Matrix[x][y]的值為路段[（x，y）]的加權(quán)長(zhǎng)度，若[x]與[y]之間不存在通路，則置Matrix[x][y]的值為無(wú)窮大∞。雖然采用鄰接矩陣的表示方法易于編程且容易實(shí)現(xiàn)，但是該方法的空間復(fù)雜度為o（N2），空間需求會(huì)隨著結(jié)點(diǎn)數(shù)量的增多而成指數(shù)形勢(shì)的增長(zhǎng)，且會(huì)浪費(fèi)大量的空間來(lái)存儲(chǔ)不相鄰結(jié)點(diǎn)的無(wú)用加權(quán)長(zhǎng)度∞。比鄰接矩陣更好的存儲(chǔ)方式是鄰接表，鄰接表是一個(gè)二維容器，第一維存儲(chǔ)結(jié)點(diǎn)序號(hào)，第二維存儲(chǔ)該結(jié)點(diǎn)所對(duì)應(yīng)的路段集，如果路段有加權(quán)值，附加的信息同樣也可以保存到鄰接表中。如對(duì)應(yīng)前文圖3所示的路徑結(jié)點(diǎn)網(wǎng)絡(luò)，若分別用鄰接矩陣和鄰接表的方式來(lái)存儲(chǔ)，得到的結(jié)果如圖4和圖5所示。

用鄰接表的方式來(lái)存儲(chǔ)，空間復(fù)雜度為o（N+e），空間需求相對(duì)于道路網(wǎng)的結(jié)點(diǎn)數(shù)量來(lái)說(shuō)是線(xiàn)性增加的。相比于鄰接矩陣的空間復(fù)雜度o（N2），采用鄰接表的方式很大程度減少了所占用的計(jì)算機(jī)存儲(chǔ)空間。

4.2 基于二叉排序樹(shù)的優(yōu)化

采用鄰接表的方式減少的是空間復(fù)雜度，Dijkstra算法的時(shí)間復(fù)雜度仍為o（N2），每次查找下一個(gè)符合要求的結(jié)點(diǎn)都需要對(duì)所有的中間結(jié)點(diǎn)進(jìn)行一次遍歷，額外計(jì)算量較大，針對(duì)該問(wèn)題，引入了數(shù)據(jù)結(jié)構(gòu)中的二叉排序樹(shù)結(jié)構(gòu)，提前對(duì)中間結(jié)點(diǎn)進(jìn)行一次從小到大的排序操作。圖6表示的是典型的二叉排序樹(shù)，引入二叉排序樹(shù)后的Dijkstra算法的實(shí)現(xiàn)流程如圖7所示。

1）初始化數(shù)組，將起點(diǎn)加入Y集合。

2）求取Y集合的最后一個(gè)元素的鄰接結(jié)點(diǎn)，將鄰接結(jié)點(diǎn)的加權(quán)長(zhǎng)度加入二叉排序樹(shù)中進(jìn)行排序操作。

3）根據(jù)二叉排序樹(shù)的定義，最小權(quán)值將出現(xiàn)在樹(shù)的最左側(cè)，選取加權(quán)長(zhǎng)度值最小的點(diǎn)L，將其加入Y集合。

4）判斷L是否為目標(biāo)點(diǎn)，如果是，算法搜索結(jié)束，如果不是，則重復(fù)步驟2）-3），直到搜索到目標(biāo)點(diǎn)為止。

使用二叉排序樹(shù)優(yōu)化后的算法在查找下一個(gè)符合要求的結(jié)點(diǎn)時(shí)所消耗的時(shí)間大大減少，其時(shí)間復(fù)雜度為o（nlogn）。

5 實(shí)例分析

本文采用ArcGIS Engine、Visual Studio等工具開(kāi)發(fā)了應(yīng)急指揮車(chē)路徑規(guī)劃軟件。選取重慶市的道路網(wǎng)絡(luò)作為研究數(shù)據(jù)，將省道、鐵道、市區(qū)主干道等矢量要素添加到地理數(shù)據(jù)庫(kù)中，通過(guò)ArcGIS的網(wǎng)絡(luò)數(shù)據(jù)集工具得到了前文圖1所示的重慶交通道路網(wǎng)絡(luò)圖，并將優(yōu)化后的Dijkstra算法嵌入到軟件中，規(guī)劃出了應(yīng)急指揮車(chē)的最短路徑，如圖8所示。

在繁雜交叉路口、事故現(xiàn)場(chǎng)、醫(yī)院、商圈等位置節(jié)點(diǎn)車(chē)流量大，交通擁擠，規(guī)劃路徑時(shí)需添加障礙點(diǎn)，有效避開(kāi)交通擁擠的位置節(jié)點(diǎn)，得到如圖9所示的最短路徑。

在車(chē)輛行駛速度理想的狀態(tài)下，假定經(jīng)過(guò)一個(gè)交叉路口平均等待30s，圖8的最短路徑長(zhǎng)為4619.8m，經(jīng)過(guò)13個(gè)交叉路口，所用時(shí)間為13.4min，圖9的路線(xiàn)長(zhǎng)為4718.5m，經(jīng)過(guò)11個(gè)交叉路口，消耗12.6min。圖9的路線(xiàn)有效地避開(kāi)了交通擁擠路段，雖然相比圖8行駛了更長(zhǎng)的距離，但是卻消耗了更少的時(shí)間。

6 結(jié)束語(yǔ)

本文使用鄰接表以及二叉排序樹(shù)對(duì)Dijkstra算法進(jìn)行了優(yōu)化，節(jié)省了計(jì)算機(jī)的存儲(chǔ)空間，減少了算法的執(zhí)行時(shí)間，提高了算法的運(yùn)行效率，并將優(yōu)化后的算法應(yīng)用于應(yīng)急指揮車(chē)路徑規(guī)劃軟件中，實(shí)現(xiàn)了應(yīng)急指揮車(chē)最短路徑的規(guī)劃。在城市交通中，不僅僅要考慮到起始點(diǎn)與目標(biāo)點(diǎn)之間的路段長(zhǎng)度，還要考慮路段的路況、路障、交通的擁擠程度等因素，只有綜合考慮更多的交通因素，使構(gòu)建的城市交通模型更接近實(shí)際生活中的城市交通網(wǎng)絡(luò)，得到的最短路徑才能更準(zhǔn)確，更符合實(shí)際需求。

參考文獻(xiàn)：

[1] 梁曉輝，慕永輝，吳北華，等.關(guān)于路徑規(guī)劃的相關(guān)算法綜述[J].價(jià)值工程，2020，39（3）：295-299.

[2] Tamatjita E N，Mahastama A W.Shortest path with dynamic weight implementation using Dijkstra's algorithm[J].ComTech：Computer，Mathematics and Engineering Applications，2016，7（3）：161.

[3] 趙青，朱樂(lè)天.基于ArcGIS的最短路徑算法在城市交通中的應(yīng)用[J].航空計(jì)算技術(shù)，2014，44（2）：14-17.

[4] Abhishek Goyal，Prateek Mogha，Rishabh Luthra，et al.Path finding：A* or Dijkstra's[J].International Journal in IT & Engineering，2014，2（1）：1-15.

[5] 黃杭.淺談Dijkstra算法與Floyd算法[J].中國(guó)新通信，2019，21（3）：162-163.

[6]逄淑玲，王曉升.Dijkstra算法的并行實(shí)現(xiàn)[J].微型機(jī)與應(yīng)用，2017，36（9）：25-27.

[7] 吳紅波，王英杰，楊肖肖.基于Dijkstra算法優(yōu)化的城市交通路徑分析[J].北京交通大學(xué)學(xué)報(bào)，2019，43（4）：116-121，130.

[8] 王特起，謝亞琴.基于Dijkstra算法的校園導(dǎo)航系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J].通信技術(shù)，2019，52（8）：1937-1943.

[9] 張本俊，周海嬌，劉淑琴.改進(jìn)Dijkstra算法在公共交通出行的研究[J].物聯(lián)網(wǎng)技術(shù)，2018，8（11）：45-48.

[10] 王旭，劉毅，李國(guó)燕.基于改進(jìn)Dijkstra算法的移動(dòng)機(jī)器人路徑規(guī)劃[J].天津城建大學(xué)學(xué)報(bào)，2018，24（5）：378-381，386.

【通聯(lián)編輯：謝媛媛】