基于權(quán)值的Dijkstra停車路徑規(guī)劃算法的優(yōu)化與實現(xiàn)

袁琳,王淵,孫建蕓，王新生,2(.湖北大學(xué)資源環(huán)境學(xué)院，湖北 武漢 430062；2.農(nóng)業(yè)部遙感應(yīng)用中心武漢分中心，湖北 武漢 430062)

?

基于權(quán)值的Dijkstra停車路徑規(guī)劃算法的優(yōu)化與實現(xiàn)

袁琳1,王淵1,孫建蕓1，王新生1,2
(1.湖北大學(xué)資源環(huán)境學(xué)院，湖北 武漢 430062；2.農(nóng)業(yè)部遙感應(yīng)用中心武漢分中心，湖北 武漢 430062)

基于用戶自由選擇車位，以停車時間最短為準(zhǔn)則，結(jié)合權(quán)值的計算方法及停車場的內(nèi)部結(jié)構(gòu)特點，對Dijkstra算法進行改進，設(shè)計并實現(xiàn)符合實際的最優(yōu)停車路徑規(guī)劃算法，并對武漢某公園的大型停車場進行應(yīng)用驗證.結(jié)果表明，相對于傳統(tǒng)算法，改進后的Dijkstra算法降低時間的復(fù)雜度，減少節(jié)點的搜索量，提高搜索效率，在停車場引導(dǎo)系統(tǒng)中有一定的實際應(yīng)用價值.關(guān)鍵詞：停車場；權(quán)值；Dijkstra算法；最優(yōu)停車路徑

0 引言

隨著經(jīng)濟的發(fā)展，人民生活水平的不斷提高，汽車普遍存在于生活之中，自駕出行的頻率也隨之增高，于是出現(xiàn)了城市“停車難”現(xiàn)象.早在1971年，國外就有了停車場引導(dǎo)系統(tǒng)，我國也于2001年開始建立停車引導(dǎo)系統(tǒng)[1-2]，但多數(shù)停車引導(dǎo)系統(tǒng)只能提示停車場的出入口位置以及當(dāng)前剩余停車位數(shù)量，對于車位的分配是隨機的，用戶進入停車場后只能盲目地尋找空車位，因此滿意度不高.這說明現(xiàn)有的停車引導(dǎo)系統(tǒng)沒有起到相應(yīng)的引導(dǎo)作用，用戶尋找空閑車位的時間仍較長，停車效率低，常常造成停車場的擁堵.

針對以上問題，本文中從用戶角度出發(fā)，基于用戶自由選擇車位，以停車時間最短為準(zhǔn)則，采用Dijkstra算法，結(jié)合停車場的內(nèi)部結(jié)構(gòu)特點，采用分層的方法對Dijkstra算法進行改進，設(shè)計并實現(xiàn)適用于手機Android系統(tǒng)的最優(yōu)停車路徑規(guī)劃算法，應(yīng)用于停車場停車引導(dǎo)應(yīng)用程序中，提供最優(yōu)停車路徑，使用戶可以快速到達空閑車位，提高停車效率，最后用Java對改進的算法進行應(yīng)用仿真.

1 停車場模型構(gòu)建

為了研究大型停車場的最優(yōu)停車路線規(guī)劃問題,需根據(jù)實際停車場的車位與道路布局建立抽象數(shù)學(xué)模型.圖1是武漢某公園停車場平面示意圖.Dijkstra算法基于有向(無向)帶權(quán)圖，因此將停車場內(nèi)部的車位網(wǎng)絡(luò)轉(zhuǎn)化成為有向(無向)帶權(quán)圖結(jié)構(gòu)，轉(zhuǎn)化后的效果如圖2所示.道路的交叉口、轉(zhuǎn)彎處、停車位以及停車場出入口均代表一個節(jié)點，其中R表示停車場的入口，E表示停車場的出口，本文中引用的停車場的出口與入口在同一位置.道路交叉處定義為道路節(jié)點，分別用n1、n2、……n12表示，Pi(i=1,2,3,…)表示車位節(jié)點，C(i，j=1,2,3,…)表示相鄰2個節(jié)點之間的道路[3].

圖1 武漢某公園停車場平面示意圖

圖2 停車場無向帶權(quán)結(jié)構(gòu)圖

2 方法描述

2.1 Dijkstra最短路徑算法 路徑規(guī)劃的核心就是最短路徑算法，研究最短路徑的方法很多，如凸輪基本方法、啟發(fā)式搜索方法、動態(tài)規(guī)劃方法、神經(jīng)網(wǎng)絡(luò)方法等.傳統(tǒng)的最短路徑算法主要有Floyd算法、矩陣算法和Dijkstra算法等.其中Floyd算法用于計算網(wǎng)絡(luò)中每次段路徑；Dijkstra算法用于計算一個源節(jié)點到其他節(jié)點的最短代價路徑.Dijkstra算法由于適應(yīng)網(wǎng)絡(luò)拓撲的變化，其性能穩(wěn)定，因而在計算機網(wǎng)絡(luò)拓撲路徑選擇以及GIS中得到廣泛應(yīng)用[3].

Dijkstra算法由荷蘭計算機科學(xué)家迪克斯特拉提出的[4].Dijkstra算法是典型的單源最短路徑算法，用于計算一個節(jié)點到其他所有節(jié)點的最短路徑.主要特點是以起始點為中心向外層層擴展，直至擴展到終點，是有代表性的最短路徑算法，有較高的應(yīng)用價值[4].1996年Zhan等[5]使用實際交通網(wǎng)絡(luò)測試了17種最短路徑算法的15種，結(jié)果表明，計算一點到其他點的最短路徑的最快的方法是Dijkstra算法.

2.2 道路權(quán)值設(shè)定 權(quán)值是道路某個或某些特征屬性的量化表示，如道路長度、路段車流量等屬性都可以被量化為路段相對應(yīng)的權(quán)值.權(quán)值是Dijkstra算法計算最短路徑的依據(jù)，尋找最短路徑即起點到終點之間的消耗最低，所以權(quán)值的確定是算法精確度的關(guān)鍵.由于在停車場內(nèi)部駕車行駛的無方向性特性，本文中設(shè)定每個路段來回方向上對應(yīng)的邊權(quán)值相等，即每條邊都有且僅有一個權(quán)值.

在傳統(tǒng)的Dijkstra算法中，權(quán)值僅表示2個節(jié)點之間的距離.由于停車場車流量的不確定性，即道路暢通性是無法確定的，所以通過距離長短來判斷是否是最優(yōu)路徑的方法不準(zhǔn)確.本文中對權(quán)值的設(shè)定進行改進，以用戶的停車時間最短為準(zhǔn)則，在考慮最優(yōu)路徑時，結(jié)合道路長度以及道路上的實時車流量信息來計算權(quán)值.隨著圖像射頻技術(shù)和射頻技術(shù)的快速發(fā)展，已能準(zhǔn)確采集停車場道路實時車流量信息[6-7].

設(shè)定D(i，j=1,2,3,…)表示道路C(i，j=1,2,3,…)上的權(quán)值，M(i，j=1,2,3,…)表示道路C(i，j=1,2,3,…)上的實時車輛數(shù)，S(i，j=1,2,3,…)表示道路C(i，j=1,2,3,…)上的距離，V(i，j=1,2,3,…)表示道路C(i，j=1,2,3,…)上的實時車速.根據(jù)采集到的道路實時車流量信息計算該道路的實時車速，即道路的暢通性.道路交通規(guī)定，停車場限速為5km/h，用Vk表示，則道路C(i，j=1,2,3,…)上的實時車速計算公式為：

(1)

(2)

其中，β的值由實地統(tǒng)計得到[7].權(quán)值計算公式為：

(3)

2.3 Dijkstra算法的改進 傳統(tǒng)的Dijkstra最短路徑算法在確定某一起點到任一節(jié)點的最短路徑時，會遍歷計算所有的節(jié)點，本文中針對的是節(jié)點較多的停車場，傳統(tǒng)的Dijkstra算法計算慢，效率低.針對這一缺陷，本文中對傳統(tǒng)的Dijkstra算法進行改進.

由于停車場的節(jié)點數(shù)較多，如圖2所示，所以將道路節(jié)點和車位節(jié)點區(qū)分開.采用分層搜索方法，把路徑搜索過程化，對每個過程進行求解，得到全局較優(yōu)解[8-9].具體操作為：把停車場中的所有節(jié)點分為2層，車位節(jié)點Pi(i=1,2,3,…)屬于第一層，入口節(jié)點R、出口節(jié)點E和交叉口的道路節(jié)點C(i，j=1,2,3,…)屬于第二層.在確定入口節(jié)點到目標(biāo)車位節(jié)點的最優(yōu)路徑時，將路徑搜索分為2個過程，第一過程，通過計算車位節(jié)點Pi(i=1,2,3,…)分別到其所處道路C(i，j=1,2,3,…)上兩端節(jié)點ni和nj的距離，判斷距離大小，距離車位近的道路節(jié)點將代替目標(biāo)車位節(jié)點，作為下一層搜索的目標(biāo)節(jié)點.第二過程，通過在第一層中找到的道路節(jié)點，再次進行道路節(jié)點搜索，確定入口節(jié)點到目標(biāo)道路節(jié)點的最優(yōu)路徑.綜合以上兩個過程，就可以得到最優(yōu)路徑所通過的節(jié)點.最后，將最優(yōu)路徑通過的道路節(jié)點與目標(biāo)車位節(jié)點連線，確定最優(yōu)路徑.通過改進的Dijkstra算法可以大大減少算法搜索節(jié)點的工作量，提高算法的搜索效率.

改進后的Dijkstra算法的實現(xiàn)步驟如下：

1) 根據(jù)用戶選擇的車位結(jié)點，查詢車位節(jié)點所在路段兩端的道路節(jié)點，記錄節(jié)點名稱，分別計算車位節(jié)點到兩端道路節(jié)點的距離；

2) 判斷距離長度，確定目標(biāo)道路節(jié)點；

3) 初始化道路節(jié)點集合T，T集合中只包含入口節(jié)點以及到其本身的最小權(quán)值，令T={S(0)}，初始化集合U，U集合包含除入口節(jié)點R外的其余道路節(jié)點以及邊相對應(yīng)的最小權(quán)值(與入口節(jié)點相鄰的則記錄權(quán)值，不相鄰的權(quán)值則為∞)；

4) 從U集合中選出權(quán)值最小的節(jié)點，并加入到T集合中，同時從U集合中移除該節(jié)點；

5) 更新U集合中各個節(jié)點到入口節(jié)點R的權(quán)值；

6) 重復(fù)步驟4)和5)，直到捕捉到目標(biāo)節(jié)點；

7) 將入口節(jié)點與通過的節(jié)點和最終的車位節(jié)點連接起來，則為最終的最優(yōu)路徑.

3 實例與分析

為驗證算法的正確性與有效性，采用上述算法步驟，在Eclipse環(huán)境下通過Java語言實現(xiàn)改進后的Dijkstra算法.以圖1所示的停車場為實驗場景，假設(shè)某一時刻停車場內(nèi)剩余27個空閑車位，其余車位均已被占用.P1為用戶所選擇的空閑車位，表1為圖1停車場在某一時刻的道路權(quán)值屬性表，表中記錄停車場內(nèi)17條路段的屬性信息.道路長度固定不變，且停車場限速5km/h(約為2m/s)，錄入每條路段實時車流量，根據(jù)(1)式、(2)式計算相應(yīng)每條路段的行駛速度，根據(jù)(3)式計算每條路段相對應(yīng)的權(quán)值D(i，j=1,2,3,…).

表1 停車場道路權(quán)值屬性表(一)

由表1可以清楚看到每條道路的權(quán)值屬性，道路C，C權(quán)值相對較大，是較為擁堵的路段.根據(jù)最優(yōu)停車算法，計算車位入口R(n4)到P1的最優(yōu)路徑，如圖3所示.由圖3可以看出距離目標(biāo)車位節(jié)點P1最近的道路節(jié)點為C12，得出的最優(yōu)路徑道路權(quán)值的和最小，路徑為n4→n7→n8→n9→n12→P1，權(quán)值為45.00.從規(guī)劃的最優(yōu)路徑可以明顯看出，改進后的算法能準(zhǔn)確地避開擁堵路段C和C.

更改每條道路的實時車輛數(shù)，重新計算權(quán)值，更改后的道路權(quán)值屬性表如表2所示.根據(jù)以上停車場各路段的屬性值，運行最優(yōu)停車路徑算法，得到的最優(yōu)路徑為n4→n5→n6→n9→n12→P1，最小權(quán)值為52.56，最優(yōu)路徑如圖4所示.

圖3 最優(yōu)路線規(guī)劃(一

圖4 最優(yōu)路線規(guī)劃(二

由圖4可知，在規(guī)劃最優(yōu)路徑時有效地避開了較為擁堵的C和C兩條路段，保持用戶到達停車位的道路通暢性.

分別保持停車場道路權(quán)值屬性表(表1和表2)的狀態(tài)，更改用戶所選車位為P2，運行程序，分別得到以下2種最優(yōu)路徑規(guī)劃為：n4→n7→n8→P2，最小權(quán)值為22.5，如圖5所示；n4→n5→n8→P2，最小權(quán)值為33.84，如圖 6所示.規(guī)劃行車路線時，有效地避開較為擁堵的C路段.

圖5 最優(yōu)路線規(guī)劃(三

表2 停車場道路權(quán)值屬性表(二)

道路屬性Vk/(m/s)M/輛C/mβV/(m/s)DC21301.02.0015.00C22151.51.3311.28C20301.02.0015.00C23152.60.7719.48C20151.02.007.50C22301.51.3322.56C20301.02.0015.00C22151.51.3311.28C21151.02.007.50C23302.60.7738.96C20151.02.007.50C24303.10.6546.15C22151.51.3311.28C21151.02.007.50C22301.51.3322.56C20301.02.0015.00

針對以上實驗例證，本文中對傳統(tǒng)的Dijkstra算法和改進后的Dijkstra算法在2種不同道路權(quán)值屬性下，規(guī)劃入口到車位P1的行車路線，將程序所需運行時間進行比對，如表3所示.

表3 傳統(tǒng)的Dijkstra算法和改進后的Dijkstra算法運行時間對比

從表3中可以看出，改進后的Dijkstra算法在運行時間上有很大的提高，運行時間大約是傳統(tǒng)的Dijkstra算法的1/40，基本達到預(yù)期目標(biāo).

由以上實例驗證，可以看到改變實時車流量信息的同時，權(quán)值也隨之變化.運行程序后，在規(guī)劃路徑時，改進的最優(yōu)路徑算法可以有效地引導(dǎo)用戶通過權(quán)值較小的路段,避開權(quán)值較大的路段即擁堵路段，為用戶節(jié)省停車所需時間.如果僅僅考慮道路距離判斷權(quán)值大小，將導(dǎo)致用戶無法準(zhǔn)確避免擁堵道路，增加用戶停車所用時間，降低停車場的使用效率.本文中結(jié)合道路距離及道路的實時車流量信息計算權(quán)值，提高用戶的停車效率及停車場的運行效率.

4 結(jié)論

針對停車場的車位引導(dǎo)問題,本文中建立停車場數(shù)學(xué)模型，引入時間權(quán)值和節(jié)點分層的方法對傳統(tǒng)的Dijkstra算法進行改進,并利用改進后的算法結(jié)合實例驗證，規(guī)劃出入口到目標(biāo)車位之間的最優(yōu)停車路徑.相比于傳統(tǒng)的Dijkstra算法，改進后的最優(yōu)停車路徑算法能夠引導(dǎo)用戶通過路況通暢的路段，避開通行質(zhì)量不佳的路段，使用戶可以快速、安全地完成停車行為，減少用戶停車時間，避免停車場內(nèi)部的道路擁擠，有利于停車場內(nèi)部的管理，對于多車位、路線復(fù)雜的停車場具有一定的實用價值.

[1] 彭紅星,解鳳玲.改進Dijkstra算法在停車誘導(dǎo)系統(tǒng)中的應(yīng)用與仿真[J].計算機應(yīng)用，2011，31(12):63-66.

[2] 于德新,楊兆升,劉雪杰.基于停車場選擇的停車誘導(dǎo)路徑優(yōu)化方法研究[J].交通運輸系統(tǒng)工程與信息，2006，6(12):41-48.

[3] 程麗平,譚永海.改進的分層A*算法在停車場路徑尋優(yōu)中的應(yīng)用[J].計算機測量與控制，2015，23(1):183-186.

[4] 王梅梅.基于GIS的最優(yōu)路徑算法研究與實現(xiàn)[D]. 南京：南京理工大學(xué)，2008.

[5] 許增昭,許倫輝.Dijkstra改進算法在泊位誘導(dǎo)系統(tǒng)中的應(yīng)用與仿真[J].科學(xué)技術(shù)與工程，2009，23(12):7226-7229.

[6] 吳若偉,樓佩煌.基于Dijkstra算法的大型停車場最優(yōu)泊車路徑規(guī)劃[J].工業(yè)控制計算機，2013，26(5):93-95.

[7] James D T. A Dijkstra’s algorithm shortest path assignment using the Google Maps API: poster session[J].Journal of Computing Sciences in Colleges，2010,25(6):253-255.

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

[9] 錢紅昇,葛文鋒,鐘鳴,等.基于分層的改進A算法在路徑規(guī)劃中的應(yīng)用[J].計算機工程與應(yīng)用，2014，50(7):225-229.

(責(zé)任編輯 郭定和)

Optimizing Dijkstra algorithm design and accomplishment for parkingroutine programming based on weight caculation

YUAN Lin1, WANG Yuan1, SUN Jianyun1, WANG Xinsheng1,2

(1.Faculty of Resources and Environmental Science, Hubei University, Wuhan 430062, China；2.Wuhan Branch of Remote Sensing Application Center, Ministry of Agriculture, Wuhan 430062, China)

Relying on the principle that the user self-defined routine, and shortest parking time purpose, we associate with combining the weight calculation algorithm and parking lot internal structure to optimize the Dijkstra algorithm and accomplished the algorithm for the best parking routine design. The research result has been successfully tested in one selected large parking garage in Wuhan Park, and proved to be a great improvement in reducing time complication, node searching times, and improved the searching efficiency. The improved parking guide system has some practical value.Key words:parking garage;weight calculation;Dijkstra algorithm;parking routine optimization

2016-10-24

袁琳(1992-)，女，碩士生；王新生，通信作者，教授，E-mail:443941982@qq.com

1000-2375(2017)03-0279-06

TP301.6

A

10.3969/j.issn.1000-2375.2017.03.012