基于Dijkstra算法的車位引導路徑

彭悅

【摘要】? ? 隨著計算機和地理信息科學的發展，GIS（地理信息系統）的應用領域越來越廣.最短路徑分析是GIS地理網絡分析功能中的一個關鍵性的問題.計算最短路徑的經典算法之一就是Dijkstra算法.傳統的Dijkstra算法是將所有可能路徑都加進去，計算量較大、效率低。本文在分析停車場內部結構的基礎上，運用廣義DEA模型結合影響駕駛員泊車心理的制約因素，進行有效性分析，采用改進的Dijkstra算法來優化、引導數據模型找出最優泊車路徑。

【關鍵字】? ? Dijkstra算法? ? 路徑規劃? ? 廣義DEA模型

一、緒論

1.1研究背景

由國家統計局公布的信息，1997年至2016年的20年間，私人汽車擁有量已由358.36萬輛增長為16330.20萬輛。據行內人士預測，在2020年中國私人汽車擁有量將達到2億輛。“一位難求”的現象越發普遍，這給停車場管理及其管理系統帶來新的挑戰。目前的智能化停車場管理系統是通過計算機、網絡設備、車道管理設備共同搭建的一套管理系統。系統包括車輛人員身份識別、車輛資料管理、車輛出入情況、位置跟蹤和收費管理等。為解決以上問題，有效利用時間，車位引導系統顯得尤為重要。

1.2研究意義

車位引導最短路徑規劃，實質上是通過引導駕駛員在最短時間內到達距離目的地最近的空車位。對Dijkstra算法的技術可行性、區域適應性和實施可能性進行最優化選擇。力求時間消耗最少的情況下，找到最優空車位。研究Dijkstra優化算法是提高效率的最佳方法，探求駕駛員泊車心理制約因素對車位引導系統的影響，抑制“粗放型”治理模式，追求“多快好省”的引導方案，以實現邊際效益的最大化。

二、名詞解釋及模型假設

2.1名詞解釋

（1）Dijkstra算法：是從一個頂點到其余各頂點的最短路徑算法，解決的是有向圖中最短路徑問題。迪杰斯特拉算法主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。

（2）遺傳算法：遺傳算法是從代表問題可能潛在的解集的一個種群開始的，而一個種群則由經過基因編碼的一定數目的個體組成。按照適者生存和優勝劣汰的原理，逐漸演化產生出越來越好的近似解。種群像自然進化一樣的后生代種群比前代更加適應于環境，末代種群中的最優個體經過解碼，可以作為問題近似最優解。

（3）A*算法：A*算法是一種靜態路網中求解最短路徑最有效的直接搜索方法。估價值與實際值越接近，估價函數取得就越好。

2.2模型假設

（1）假設每個停車場分布均勻不影響評估結果。

（2）假設每個停車場地勢無顯著差異且對評估結果無影響。

（3）假設各個區域存在微小差異，故不影響評估結果。

（4）假設各個決策單元之間相互獨立。

三、廣義DEA模型的建立與求解

3.1.3廣義DEA有效性含義分析

為了進一步確認每個決策單元較優秀的樣本單元更高效，或是與之持平，亦或是不如它，同時，也為了確認具體差距和量化后的排名，下文建立了滿足生產可能集公理的條件下的樣本單元確定可能集T（1），以及樣本可能集T（1）的有效面L，同時，確立前沿有效面L∩T（1），經由G-BCC模型將樣本單元和被評價單元代入，得出對應取值，以做出比較。

3.2模型的求解

通過調查發現駕駛員在停車過程中存在短暫的決策過程，停車位置的選擇主要受到以下因素的影響：目的地位置、停車區域位置、步行距離、行駛路線時間以及車位信息。將此信息作為偏好投入指標。將路線、車位信息作為產出。

四、Dijkstra算法與其他主流算法的比較

4.1搜索速度比較

以16、32、43、62、78五個節點為例分別采用Dijkstra算法、A*算法、遺傳算法進行路徑規劃，他們各自花費的時間如表4-1所示。

由上表可看出：當節點個數比較少時，三種算法所花費的時間差不多，當節點個數比較多時，A*算法最快，Dijkstra算法最慢，而且這種差距將隨節點數量的增加而變得更明顯。對于實際地圖而言，由于節點與道路的數量一般都很的大，Dijkstra算法在搜索速度方面弱勢明顯。

4.2搜索成功率比較

對上述五個節點分別采用三種算法進行路徑規劃，三者各自搜索到最短路徑的情況如表4-2所示.

由表4-2可以看出：當節點個數和弧數量比較多時，Dijkstra算法是一種遍歷算法，每次能保證100%搜索到最短路徑，遺傳算法搜索到最短路徑的成功率比Dijkstra算法低一些， 算法最低，且這種差距在節點數和弧數量越大時更加明顯。

五、Dijkstra算法的優缺點

（1）從全局出發，算法穩定性強，理論上最完備，實際應用廣泛。

（2）該算法具有魯棒性，全局搜索可行解的能力強。

（3）易于其他方法相結合來改善算法。

（4）只適用于非負權值網絡的最短路問題。

參? 考? 文? 獻

[1]李宗正，張民，張煒，秦玉蓮，刁少文.基于停車時間最短的車位引導系統設計[J].工業控制計算機，2017

[2]蔡佳.基于Dijkstra算法的停車場車位引導系統[J].電子技術與軟件工程，2014