◆王 維 蓋之華

?

基于Dijkstra算法的停車場泊車引導(dǎo)路徑設(shè)計

◆王 維 蓋之華

(蘇州經(jīng)貿(mào)職業(yè)技術(shù)學院數(shù)字化校園管理中心 江蘇 215000)

Dijkstra算法是解決最短路徑非常有效的辦法，但在大型停車場內(nèi)，傳統(tǒng)的Dijkstra算法是將所有可能路徑都加進去，計算量較大、效率低。本文在分析停車場內(nèi)部結(jié)構(gòu)的基礎(chǔ)上，抽象建立起泊車引導(dǎo)數(shù)據(jù)模型，再結(jié)合影響駕駛員泊車心理的制約因素，用改進的Dijkstra算法來優(yōu)化、引導(dǎo)數(shù)據(jù)模型找出最優(yōu)泊車路徑。最后結(jié)合實例說明用改進的Dijkstra算法來優(yōu)化引導(dǎo)路徑模型能夠提高泊車效率。

Dijkstra算法；泊車；引導(dǎo)路徑

0 引言

近年來隨著汽車數(shù)量井噴式增長，“停車難”問題日漸突出，尤其是在停車場內(nèi)部，駕駛員為了尋找一個空閑車位往往需要耗費很長時間。低下的停車效率嚴重影響著駕駛員的泊車感受，這是一個亟待解決的問題。針對這一現(xiàn)象，本文在分析停車場內(nèi)部結(jié)構(gòu)的基礎(chǔ)上，抽象建立起泊車引導(dǎo)數(shù)據(jù)模型，再綜合考慮影響駕駛員泊車心理的制約因素，然后用改進的Dijkstra算法來優(yōu)化引導(dǎo)數(shù)據(jù)模型，最終找出最優(yōu)泊車路徑，從而大大提高了停車效率，改善了泊車感受。

1 停車場平面結(jié)構(gòu)分析及數(shù)據(jù)建模

1.1 停車場平面結(jié)構(gòu)特點

圖1 停車場平面結(jié)構(gòu)圖

現(xiàn)實生活中停車場有很多種，圖1是一個典型停車場平面結(jié)構(gòu)示意圖。這個停車場出入口唯一，并且分開設(shè)立，道路交叉口非常明顯，一部電梯在出入口中間，整體上呈現(xiàn)對稱狀。本文就以此停車場為例來探討最優(yōu)泊車路徑規(guī)劃問題。

1.2 建立數(shù)據(jù)模型

最優(yōu)泊位的選擇要考慮很多因素，比如行駛距離、行駛時間、步行距離等因素。設(shè)車庫內(nèi)空閑泊車位為Pi,該泊車位到電梯口的距離為S(E,i)，用D1(i)標示其權(quán)值；到車輛入口的距離為S(C,i)，用D2(i)標示其權(quán)值；到車輛出口的距離為S(T,i)，用D3(i)標示其權(quán)值。最優(yōu)泊車位權(quán)值應(yīng)該為min{ D1(i)+ D2(i)+ D3(i)}，對應(yīng)的泊車最優(yōu)路徑為min{ S(E,i)+ S(C,i)+ S(T,i)}。

2 Dijkstra算法實現(xiàn)

解決最短路徑問題有很多方法，其中比較經(jīng)典的有1959年荷蘭科學家Dijkstra提出了經(jīng)典的Dijkstra算法。該算法較簡單，容易實現(xiàn)，應(yīng)用非常廣泛。

2.1 Dijkstra經(jīng)典算法

在解決最短路問題時，Dijkstra經(jīng)典算法是將所有節(jié)點分成兩組，一組為已經(jīng)確定最短路徑的節(jié)點，另一組為未確定最短路徑的節(jié)點，按最短路徑長度遞增的順序逐個把未確定最短路徑的節(jié)點加到已經(jīng)確定的最短路徑節(jié)點里面，直到所有節(jié)點都加到一組之中。不難發(fā)現(xiàn)，Dijkstra經(jīng)典算法的缺點是在節(jié)點較多時計算量非常大，效率普遍較低。

2.2 改進的Dijkstra算法

傳統(tǒng)的Dijkstra算法是將所有可能路徑都加進去，然后找出最短路徑。在大型停車場內(nèi)計算量較大，這一算法非常影響效率。綜合考慮駕駛員步行距離、步行時間和駕駛員在車上的行駛時間等對停車的心理影響等因素，我們發(fā)現(xiàn)影響停車心理最為重要的因素是電梯到停車位的距離，也即步行距離和步行時間?；谶@一點，文本對傳統(tǒng)的Dijkstra算法進行了簡化改進，其基本思路是：以電梯為中心，在50m半徑范圍內(nèi)搜索車位，若沒找到空車位則逐次加50m，直至找到空車位，然后電梯為出發(fā)點，計算出離電梯最近節(jié)點D7到出入口節(jié)點D1和D9的最短距離，最后按照權(quán)值計算方法選擇出最佳車位。

具體步驟是：

第一步：以電梯L為中心，先在50ｍ半徑范圍內(nèi)搜索，若無空車位，則半徑逐次加50ｍ，直到有空車位出現(xiàn)，將搜索到的所有空車位集合記為P，每一個空車位標記為 Pi，其中i∈［0，n-1］，n為搜索到的空車位節(jié)點數(shù)目；

第二步：初始化最短路徑集合T及其對應(yīng)的最短路徑權(quán)值D2(i)，其中i∈［0，n-1］；

第三步：選取Pm，使得Pm=｛minD2(i)| Pi∈P-T｝，則Pm就是目前從T 出發(fā)的最短路徑終點，此時將節(jié)點Pm加入到集合T中；

第四步：更新從L 到Pm的最短路徑權(quán)值，令D2(i)＝min{D2(i)，D(i，m)}；

第五步：重復(fù)第三步和第四步做法，直至將空車位集合P 內(nèi)的節(jié)點全部包在集合T中；

第六步：初始化最短路徑集合M及其對應(yīng)的最短路徑權(quán)值D3(i)，即D3(i)＝D3(0,i)，i∈［0，n-1］；

第七步：用同樣方法，將集合M內(nèi)的節(jié)點全部包含在T 1中；

第八步：計算出空車位集合P中所有空車位節(jié)點的最終權(quán)值，則min{ D1(i)+ D2(i)+ D3(i)，D1(i)=0}所對應(yīng)的泊位Pn為最優(yōu)泊位，D(n)所對應(yīng)的路徑即為電梯口到Pn的最優(yōu)路徑。

3 實例分析

為驗證上述算法的可行性，我們結(jié)合實例進行分析。以圖2為例，某時刻停車場車位空閑情況。首先以電梯L為中心，在50m半徑范圍內(nèi)搜索車位，搜索結(jié)果發(fā)現(xiàn)這個范圍內(nèi)停車位很多。為了好分析，我們選取其中三個空閑停車位，分別為P1，P2，P3。

圖2 某時刻停車場示意圖

離電梯最近的節(jié)點為D7，入口節(jié)點為D1，出口節(jié)點為D9，縱向節(jié)點權(quán)值為2，橫向節(jié)點D1→D2權(quán)值為4，D2→D3權(quán)值為5。根據(jù)上述改進的Dijkstra算法，P1的最短路徑為D1(D4→D7)+D2(D7→D1)+D3(D5→D9)，權(quán)值為13；P2的最短路徑為D1(D7→D7)+D2(D7→D1)+D3(D8→D9)，權(quán)值為9；P3的最短路徑為D1(D7→D7)+D2(D7→D1)+D3(D8→D9)，權(quán)值為9，如表1所示。

表1 P1，P2，P3最短路徑及權(quán)值

P1的最短路徑權(quán)值要大于P2、P3，P2和P3最短路徑權(quán)值則相同，因此P2，P3為最佳泊車位。由此不難發(fā)現(xiàn)，改進的Dijkstra算法在準確性上沒有經(jīng)典的Dijkstra算法高，但是大大提高了計算效率，能顯著改善駕駛員泊車感受。

4 結(jié)語

Dijkstra算法是解決最短路徑非常有效的辦法，但在大型停車場內(nèi)，傳統(tǒng)的Dijkstra算法是將所有可能路徑都加進去，計算量較大，非常影響效率。本文綜合考慮步行距離、步行時間和駕駛員在車上的行駛時間等對駕駛員泊車心理的影響因素，采用簡化改進的Dijkstra算法，從而提高了停車效率，改善了泊車感受。

[1]季彥婕，王煒，鄧衛(wèi).停車場內(nèi)部泊車行為特性分析及最優(yōu)泊位選擇模型[J].東南大學學報（自然科學版），2009.

[2]王樹西，吳學.改進的Dijkstra最短路徑算法及其應(yīng)用研究[J].計算機科，2012.

[3]劉姣，葛召炎，謝靜等.停車場泊車問題的研究與仿真[J].計算機仿真，2011．

[4]劉媛媛.大型停車場內(nèi)車位誘導(dǎo)系統(tǒng)研究[D].西安：長安大學，2010．

[5]張玉杰，田碩.Dijkstra優(yōu)化算法在停車場車位引導(dǎo)系統(tǒng)中的應(yīng)用[J].計算機測量與控制，2014.

[6]何健.基于Dijkstra算法的AGV最短路徑方法研究[J].工業(yè)控制計算機, 2017.

[7]袁彬，劉建勝，錢丹等.一種基于改進Dijkstra的物流網(wǎng)絡(luò)路徑優(yōu)化算法分析[J].制造業(yè)自動化，2014.

[8]李偉，李巧君，余森.使用物聯(lián)網(wǎng)技術(shù)的停車場泊車引導(dǎo)系統(tǒng)[J].自動化與儀器儀表，2015.

[9]孫奧，朱桂斌，江鐵.一種基于路況預(yù)測信息的最小時間路徑算法[J].現(xiàn)代電子技術(shù)，2012.

[10]胡萍.基于出行者擇路策略的城市路網(wǎng)結(jié)構(gòu)優(yōu)化策略研究[D].西南交通大學，2014.

蘇州經(jīng)貿(mào)職業(yè)技術(shù)學院院級科研項目：面向Android 終端用戶的智能泊車引導(dǎo)系統(tǒng)設(shè)計（項目批準號：KY-ZR1716）。