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

彭悅

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

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

一、緒論

1.1研究背景

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

1.2研究意義

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

二、名詞解釋及模型假設

2.1名詞解釋

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

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

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

2.2模型假設

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

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

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

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

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

3.1.3廣義DEA有效性含義分析

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

3.2模型的求解

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

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

4.1搜索速度比較

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

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

4.2搜索成功率比較

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

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

五、Dijkstra算法的優(yōu)缺點

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

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

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

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

參? 考? 文? 獻

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

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