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

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

關鍵詞：城市交通;應急指揮車;鄰接表;二叉排序樹;Dijkstra

中圖分類號：U412? ? ? 文獻標識碼：A

文章編號：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 背景

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

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

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

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

3 傳統(tǒng)Dijkstra算法

3.1 Dijkstra算法描述

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

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

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

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

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

3）通過循環(huán)查詢Dis[]數(shù)組，找到S集合中距離Y集合結點加權長度最短的結點k。

4）將結點k加入Y集合。

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

6）重復步驟3）-5），直到將目標結點或者圖中所有結點加入Y集合，才結束算法。

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

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

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

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

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

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

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

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

4 Dijkstra算法優(yōu)化

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

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

用鄰接表的方式來存儲，空間復雜度為o（N+e），空間需求相對于道路網(wǎng)的結點數(shù)量來說是線性增加的。相比于鄰接矩陣的空間復雜度o（N2），采用鄰接表的方式很大程度減少了所占用的計算機存儲空間。

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

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

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

2）求取Y集合的最后一個元素的鄰接結點，將鄰接結點的加權長度加入二叉排序樹中進行排序操作。

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

4）判斷L是否為目標點，如果是，算法搜索結束，如果不是，則重復步驟2）-3），直到搜索到目標點為止。

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

5 實例分析

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

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

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

6 結束語

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

參考文獻：

[1] 梁曉輝，慕永輝，吳北華，等.關于路徑規(guī)劃的相關算法綜述[J].價值工程，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] 趙青，朱樂天.基于ArcGIS的最短路徑算法在城市交通中的應用[J].航空計算技術，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].中國新通信，2019，21（3）：162-163.

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

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

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

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

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

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