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

?

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

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

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

0 引言

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

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

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

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

圖1 武漢某公園停車場(chǎng)平面示意圖

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

2 方法描述

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

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

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

在傳統(tǒng)的Dijkstra算法中，權(quán)值僅表示2個(gè)節(jié)點(diǎn)之間的距離.由于停車場(chǎng)車流量的不確定性，即道路暢通性是無(wú)法確定的，所以通過(guò)距離長(zhǎng)短來(lái)判斷是否是最優(yōu)路徑的方法不準(zhǔn)確.本文中對(duì)權(quán)值的設(shè)定進(jìn)行改進(jìn)，以用戶的停車時(shí)間最短為準(zhǔn)則，在考慮最優(yōu)路徑時(shí)，結(jié)合道路長(zhǎng)度以及道路上的實(shí)時(shí)車流量信息來(lái)計(jì)算權(quán)值.隨著圖像射頻技術(shù)和射頻技術(shù)的快速發(fā)展，已能準(zhǔn)確采集停車場(chǎng)道路實(shí)時(shí)車流量信息[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í)時(shí)車輛數(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,…)上的實(shí)時(shí)車速.根據(jù)采集到的道路實(shí)時(shí)車流量信息計(jì)算該道路的實(shí)時(shí)車速，即道路的暢通性.道路交通規(guī)定，停車場(chǎng)限速為5km/h，用Vk表示，則道路C(i，j=1,2,3,…)上的實(shí)時(shí)車速計(jì)算公式為：

(1)

(2)

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

(3)

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

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

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

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

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

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

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

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

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

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

3 實(shí)例與分析

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

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

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

更改每條道路的實(shí)時(shí)車輛數(shù)，重新計(jì)算權(quán)值，更改后的道路權(quán)值屬性表如表2所示.根據(jù)以上停車場(chǎng)各路段的屬性值，運(yùn)行最優(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)路徑時(shí)有效地避開(kāi)了較為擁堵的C和C兩條路段，保持用戶到達(dá)停車位的道路通暢性.

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

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

表2 停車場(chǎng)道路權(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

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

表3 傳統(tǒng)的Dijkstra算法和改進(jìn)后的Dijkstra算法運(yùn)行時(shí)間對(duì)比

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

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

4 結(jié)論

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

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

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

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

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

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

[6] 吳若偉,樓佩煌.基于Dijkstra算法的大型停車場(chǎng)最優(yōu)泊車路徑規(guī)劃[J].工業(yè)控制計(jì)算機(jī)，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)化算法在停車場(chǎng)車位引導(dǎo)系統(tǒng)中的應(yīng)用[J]. 計(jì)算機(jī)測(cè)量與控制，2014，22(1):191-193.

[9] 錢紅昇,葛文鋒,鐘鳴,等.基于分層的改進(jìn)A算法在路徑規(guī)劃中的應(yīng)用[J].計(jì)算機(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