基于Dijkstra算法的停車場泊車引導路徑設計

◆王 維 蓋之華

?

基于Dijkstra算法的停車場泊車引導路徑設計

◆王 維 蓋之華

(蘇州經貿職業技術學院數字化校園管理中心 江蘇 215000)

Dijkstra算法是解決最短路徑非常有效的辦法，但在大型停車場內，傳統的Dijkstra算法是將所有可能路徑都加進去，計算量較大、效率低。本文在分析停車場內部結構的基礎上，抽象建立起泊車引導數據模型，再結合影響駕駛員泊車心理的制約因素，用改進的Dijkstra算法來優化、引導數據模型找出最優泊車路徑。最后結合實例說明用改進的Dijkstra算法來優化引導路徑模型能夠提高泊車效率。

Dijkstra算法；泊車；引導路徑

0 引言

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

1 停車場平面結構分析及數據建模

1.1 停車場平面結構特點

圖1 停車場平面結構圖

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

1.2 建立數據模型

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

2 Dijkstra算法實現

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

2.1 Dijkstra經典算法

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

2.2 改進的Dijkstra算法

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

具體步驟是：

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

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

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

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

第五步：重復第三步和第四步做法，直至將空車位集合P 內的節點全部包在集合T中；

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

第七步：用同樣方法，將集合M內的節點全部包含在T 1中；

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

3 實例分析

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

圖2 某時刻停車場示意圖

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

表1 P1，P2，P3最短路徑及權值

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

4 結語

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

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

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

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

[4]劉媛媛.大型停車場內車位誘導系統研究[D].西安：長安大學，2010．

[5]張玉杰，田碩.Dijkstra優化算法在停車場車位引導系統中的應用[J].計算機測量與控制，2014.

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

[7]袁彬，劉建勝，錢丹等.一種基于改進Dijkstra的物流網絡路徑優化算法分析[J].制造業自動化，2014.

[8]李偉，李巧君，余森.使用物聯網技術的停車場泊車引導系統[J].自動化與儀器儀表，2015.

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

[10]胡萍.基于出行者擇路策略的城市路網結構優化策略研究[D].西南交通大學，2014.

蘇州經貿職業技術學院院級科研項目：面向Android 終端用戶的智能泊車引導系統設計（項目批準號：KY-ZR1716）。