基于改進Dijkstra算法的醫院智慧停車路徑規劃研究

汪厚俊， 鄭明飛

(1.南京卓歐信息技術有限公司， 江蘇， 南京 210000； 2.南京市婦幼保健院， 江蘇， 南京 210000)

0 引言

隨著現代信息化的發展，物聯網技術廣泛應用于各大領域。但受行業限制，部分行業的物聯網技術應用程度較低，尤其是在醫院停車場智慧管理方面，物聯網技術沒有得到有效應用，導致用戶無法全面獲取停車場車位相關信息。此外，由于醫院停車場內沒有提供相應的車位推薦和行駛路徑指引服務，無法使用戶實現高效、快速停車。因此，基于物聯網技術的停車場車位推薦和行駛路徑指引對于醫院智慧停車管理十分重要。目前，基于物聯網技術的路徑規劃算法主要包括A*算法和蟻群算法算，如李世國等[1]、宋宇等[2]結合改進A*算法與無人機飛行特點，對無人機飛行路徑進行規劃，獲得飛行時間少、路徑長度短的無人機航路，縮短了傳統路徑規劃方法的時間。但該算法容易陷入局部最優，且其啟發函數難以確定，難以應用于實際醫院停車管理路徑規劃中。馬小銘等[3]、龔銘凡等[4]基于改進蟻群算法，通過引入各路徑段與起始點和目標點連線的夾角信息，獲得了一種具有高搜索效率和質量的路徑規劃方法。但該方法存在計算量大的問題，不適用于醫院智慧停車的行駛路徑和最優車位規劃。近年來，隨著Dijkstra算法在復雜圖論中的應用，研究通過改進該算法得到一種容易實現且簡單易懂路徑規劃方法，并將其用于與醫院智慧停車管理最優車位的行駛路徑規劃，實現了醫院智慧停車管理。

1 智慧停車路徑規劃問題描述

智慧停車服務的本質，就是在停車場內為駕駛員提供有效的路徑規劃。目前，為提高停車場的服務水平，部分停車場引入停車服務系統對高峰期的停車進行引導，以免造成停車場出現局部擁堵的情況。而對未引入停車服務的停車場，傳統的方法是駕駛員采用目光瞭望的方法尋找車位。如駕駛員沒找到合適的車位泊車，會繼續搜索下一個空閑車位。這樣的停車方式不僅耗費時間長，還會出現無用交通，增加停車場內高峰期的交通壓力，也影響駕駛員的心情。具體搜尋流程如圖1所示。

圖1 傳統目光瞭望搜索車位流程

為解決這種無效泊車問題，如當駕駛員進入停車場時就進行車輛停車路徑規劃，根據停車場中車位空閑數量，計算出一個路徑最短的停車位，這樣不僅可減少駕駛員的泊車時間，還可減少尾氣排放。具體的智能引導流程如圖2所示。

圖2 智能停車服務流程

從圖1、圖2可以看出，對有車輛引導的停車場，駕駛員停車具有很強的目的性，即在場內有空余車位的情況下，找到最近的車位，避免無效的車位搜索。所以智能停車路徑規劃的本質，就是在空閑車位的情況下，給駕駛員找到一條最短的停車路徑，讓駕駛員在最短時間停車，避免造成高峰期的停車擁堵問題。

2 基于Dijkstra算法的停車路徑規劃

2.1 Dijkstra算法簡介

Dijkstra算法是用于計算最短路徑的經典算法，主要用于解決有權圖中最短路徑規劃問題和網絡內部路由問題，現常用于輔助解決較為復雜的圖論問題[5]。Dijkstra算法包括永久標號和臨時標號2種方式，通過貪心思想在全局范圍內搜索最優解，其搜索過程如圖1所示。首先，確定起始源節點為圓心，采用同心圓的方式向周圍搜索，直至所有節點全部位于同心圓所在的搜索域內。Dijkstra算法搜索域即算法的搜索范圍，如圖3中最外層的實線圓包含的范圍。

圖3 Dijkstra算法搜索區域

2.2 傳統Dijkstra算法在停車路徑規劃的描述

采用傳統Dijkstra 算法規劃停車場泊位路徑規劃時，其基本的思路為令路網模型中，源節點為y，目標節點為m，Si表示y到m的最短路徑權值，Vi表示y到m前一個節點，(Si，Vi)表示路網模型中的節點，則Dijkstra算法具體搜索步驟如下：

① 設置最短路徑源節點Sd為0，Vd=?，標記k=y。假設其余節點未標記，則Si=∞，Vj未知；

③ 當路網模型中所有節點全部標記，結束算法。

2.3 Dijkstra算法改進

標準Dijkstra算法通過依次遞增的方法實現了所有節點的搜素，但由于其搜索方向不確定且搜索范圍在搜索過程中不斷擴大，降低了搜索效率。因此，為實現醫院智慧停車管理車輛最短路徑規劃，研究對Dijkstra算法進行了搜索范圍和搜索方向2個的優化[6]。

2.3.1 搜索范圍優化

通過上述對Dijkstra算法的分析可知，該算法在整個搜索過程中沒有考慮起始節點和目標節點的位置，故其搜索的范圍較大，增加了算法的計算難度。因此，為避免因搜索范圍過大帶來計算問題，研究在Dijkstra算法中加入位置關系，采用雙向搜索方法縮小其搜索范圍。但由于雙向搜索在路網模型中，其搜索目標節點和其他節點的成功率相同，因此為進一步縮小搜索范圍，研究提出扇形優化的方法，如圖4所示，其近似表示為以源節點為圓心的層層圓弧，通過減少搜索過程中的無用節點，實現縮小搜索范圍。

圖4 改進Dijkstra算法搜索區域

2.3.2 搜索方向優化

研究通過引入約束函數，采用源節點和目標節點正反2個方向交替進行搜索的方式對Dijkstra算法搜索方向的優化。通過采用約束函數，可快速適應實時信息變化引起的權值變化，減少無效節點的搜索，進而提高車輛路徑引導服務的搜索速率。約束函數表達式如式(1)。

Q(n)min=q(n)+a(n)

(1)

式中，q(n)表示起始或目標節點到搜索終止區域節點的最優路徑權值，a(n)表示搜索區域內的節點數目。

2.4 基于改進Dijkstra的停車路徑規劃模型構建

根據區域劃分方法的劃分標準，定義道路交叉點和車位節點為iD ，采用改進Dijkstra算法引導醫院停車場內車輛尋找最優車位的路徑基本思路是：當車輛進入醫院停車場時，車輛引導服務首先在起始入口根據采集到的車輛信息判斷該車輛是否有預約車位，然后根據車輛信息、車位信息和場內道路信息，采用改進Dijkstra算法確認最優車位，最后實現停車智慧管理[7-8]。具體步驟如下。

① 確定路網匯總源節點y與目標節點m，設置源節點坐標為yi=(yXi,yYi)，目標區域節點坐標為mi=(mXi,mYi)，車位道路節點坐標為di=(dXi,dYi)。由歐式距離公式(2)可計算出目標區域車位的道路節點與源節點距離[9]。

(2)

篩選出目標區域車位道路節點與源節點距離的最大值ndistmax，則改進Dijkstra算法扇形優化的軸線即為ndistmax構成的直線。

ndistmax=max{|yi,mi|}

(3)

為確定扇形搜索角度，研究建立如圖5所示的數學模型。

圖5 扇形搜索求解數學模型

② 初始化正向和反向搜索節點集合E1和E2以及終止區域節點集合L。

③ 根據三角公式確定扇形搜索角度a。

④ 分別從起始節點和目標節點2個方向進行搜索，當E1、E2集合滿足L=E1∩E2≠?時，停止搜索。

⑤ 在集合中查找t，通過計算獲取最小ym=yt+tm值。最后根據E1、E2集合確定源節點和目標節點的最優路徑。

3 仿真實驗

3.1 參數設置

(3)

(4)

3.2 算法性能比較

根據式(3)、式(4)可計算得到標準Dijkstra算法和改進Dijkstra算法的起始節點與終止節點的歐式距離關系以及有效搜索區域，如圖6所示。由圖6可知，隨起始點與目標節點距離增大，改進Dijkstra算法的搜索有效范圍明顯優于標準Dijkstra算法的搜索有效范圍，其遍布的無用區域相比標準Dijkstra算法大幅度減少，說明改進Dijkstra算法可有效縮小搜索范圍。

圖6 不同算法搜索范圍比較

在搜索時間仿真實驗中，研究在同樣的仿真條件下，采用兩種算法計算其搜索時間，并繪制其歐式距離與運行時間的對比圖，如圖7所示。由圖可知，改進Dijkstra算法平均運行時間明顯低于標準Dijkstra算法，且隨起始節點到目標節點距離增加，其優勢更加明顯，說明改進Dijkstra算法可有效縮短路徑規劃搜索時間。

圖7 不同算法平均運行時間對比

3.3 實例驗證

為驗證本研究提出的Dijkstra算法性能，研究現場采集某市醫院停車場某一區域進行了車輛和車位信息采集，如圖8所示。圖中包括車位狀態信息、道路車輛信息等。

圖8 某時刻醫院停車場車位分布圖

(1) 決策屬性確定

醫院智慧停車管理系統分配駕駛員車位主要由行車時間、停車難度、步行距離3個因素決定，因此，本研究選取上述3個因素為最有車位推導的決策屬性。

(2) 獲取停車場內車輛及車位信息

利用改進Dijkstra算法獲取實時醫院停車場內車輛與車位信息，確定停車場內有效車位為a1、b2、c3、e4、e5、g6、h7、h8、h9、k10、k11、k12；移動車輛分布在d1-d2、d3-d4、d5-d6、d7-d8、d4-d9、d10-d11、d8-d13、d13-d14段。

(3) 計算道路與車位決策屬性值

根據道路邊權構造方法[10]，計算醫院停車場內路段道路屬性，結果如表1所示。

表1 醫院停車場道路屬性信息

根據以上權值信息，通過鄰接矩陣公式，建立式(5)的醫院停車場鄰接矩陣dij。

(5)

根據停車場內車輛實時位置信息及車位難度賦值，可計算得到有效車位的屬性信息，如表2所示。

表2 有效車位屬性表

根據有效車位有效屬性，采用改進Dijkstra算法在MATLAB軟件中進行仿真，即可得到車位屬性中的行駛路徑。如k10車位，其行駛路徑如圖9所示。由圖可知，k10車位的行駛路徑為d1-d5-d10-d11-d12。當車輛到達k10車位后，車位指示燈顯示開放。

圖9 k10車位行駛路徑示例

(4) 最優車位路徑有效性分析

為驗證提出的改進Dijkstra算法推導出最優車位行駛路徑的有效性，研究對比傳統最短路徑算法，選取同一時刻醫院停車場內車輛和車位信息，并使用MATLAB計算得到不同算法最佳車位與最優路徑，如圖10所示。由圖10可知，改進Dijkstra算法求解的車位為h7，車位到入口距離為40 m，行駛路線為s-d1-d5-d10-h7，用時19 s；傳統最短路徑算法求解的車位為b2，車位到入口距離為36 m，行駛路線為s-d1-d2-b2，用時61 s。由此可得，本研究提出的改進Dijkstra算法雖行駛距離略高于傳統最短路徑算法行駛距離，但大幅度降低了行駛時間，有效避免了因行駛時間過長造成的醫院停車場內擁堵情況，說明改進Dijkstra算法推導的最優車位有效規避了停車場內流量大的問題，同時可滿足駕駛員快速完成停車，進而有利于停車場管理人員對場內車位及車輛的管理，實現醫院智慧停車管理。

(a) 改進前

(b) 改進后圖10 改進Dijkstra算法前后的最優路徑

4 總結

綜上所述，本研究提出改進Dijkstra算法預先推導得到醫院停車場內最優車位及行駛路線，實現用戶高效、快速的場內停車，且相較于傳統最短路徑算法計算的最短路徑，該方案有效規避了因停車場內各區域流量不同造成的擁堵問題，更能滿足用戶實際需求及醫院智慧停車的管理。