彭悅

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

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

一、緒論

1.1研究背景

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

1.2研究意義

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

二、名詞解釋及模型假設(shè)

2.1名詞解釋

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

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

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

2.2模型假設(shè)

（1）假設(shè)每個(gè)停車場(chǎng)分布均勻不影響評(píng)估結(jié)果。

（2）假設(shè)每個(gè)停車場(chǎng)地勢(shì)無(wú)顯著差異且對(duì)評(píng)估結(jié)果無(wú)影響。

（3）假設(shè)各個(gè)區(qū)域存在微小差異，故不影響評(píng)估結(jié)果。

（4）假設(shè)各個(gè)決策單元之間相互獨(dú)立。

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

3.1.3廣義DEA有效性含義分析

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

3.2模型的求解

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

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

4.1搜索速度比較

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

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

4.2搜索成功率比較

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

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

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

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

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

（3）易于其他方法相結(jié)合來(lái)改善算法。

（4）只適用于非負(fù)權(quán)值網(wǎng)絡(luò)的最短路問(wèn)題。

參? 考? 文? 獻(xiàn)

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

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