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

◆王 維 蓋之華

?

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

◆王 維 蓋之華

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

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

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

0 引言

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

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

1.1 停車場(chǎng)平面結(jié)構(gòu)特點(diǎn)

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

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

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

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

2 Dijkstra算法實(shí)現(xiàn)

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

2.1 Dijkstra經(jīng)典算法

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

2.2 改進(jìn)的Dijkstra算法

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

具體步驟是：

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

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

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

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

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

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

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

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

3 實(shí)例分析

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

圖2 某時(shí)刻停車場(chǎng)示意圖

離電梯最近的節(jié)點(diǎn)為D7，入口節(jié)點(diǎn)為D1，出口節(jié)點(diǎn)為D9，縱向節(jié)點(diǎn)權(quán)值為2，橫向節(jié)點(diǎn)D1→D2權(quán)值為4，D2→D3權(quán)值為5。根據(jù)上述改進(jìn)的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)，改進(jìn)的Dijkstra算法在準(zhǔn)確性上沒(méi)有經(jīng)典的Dijkstra算法高，但是大大提高了計(jì)算效率，能顯著改善駕駛員泊車感受。

4 結(jié)語(yǔ)

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

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

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

[3]劉姣，葛召炎，謝靜等.停車場(chǎng)泊車問(wèn)題的研究與仿真[J].計(jì)算機(jī)仿真，2011．

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

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

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

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

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

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

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

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