基于動態(tài)規(guī)劃和貪婪算法的停車樓智能停車優(yōu)化方法*

趙 瑋 徐良杰 姚裔虎 王冠云 李 革

(武漢理工大學(xué)交通學(xué)院1) 武漢 430063) (內(nèi)蒙古科技大學(xué)經(jīng)濟與管理學(xué)院2) 包頭 014010)

基于動態(tài)規(guī)劃和貪婪算法的停車樓智能停車優(yōu)化方法*

趙 瑋1,2)徐良杰1)姚裔虎1)王冠云1)李 革2)

(武漢理工大學(xué)交通學(xué)院1)武漢 430063) (內(nèi)蒙古科技大學(xué)經(jīng)濟與管理學(xué)院2)包頭 014010)

針對各種類型的立體停車樓停車管理系統(tǒng)混亂、無序?qū)е虏窜嚰俺鲕囘^程費時并易引起停車樓通道阻塞等問題，根據(jù)停車樓布局、歷史停車數(shù)據(jù)庫及待停車輛的信息，建立了二維背包模型，并將動態(tài)規(guī)劃算法和貪婪算法相融合，提出啟發(fā)式組合算法，使每一待停車輛進入停車場時即獲取泊車位指示以便有序?？?，優(yōu)化空閑停車資源分配，減少車輛在停車樓內(nèi)停留總時間和通道阻塞，提高停車樓利用率.

停車樓；貪婪算法；動態(tài)規(guī)劃算法；二維背包問題

0 引 言

我國針對多層停車樓的研究起步較晚，研究成果較少，已有的理論研究成果基本也是借鑒國外的現(xiàn)有成果和實踐經(jīng)驗，根據(jù)我國停車樓實際情況所做的相關(guān)文獻很少，文獻[1]對停車需求特點和停車管理方式做了系統(tǒng)地介紹，但只定性分析了多層停車樓出現(xiàn)的必要性和作用；文獻[2]以實例定量地證明了多層停車樓的發(fā)展前景及經(jīng)濟形勢都十分樂觀；文獻[3]提出了人口密集城市和經(jīng)濟發(fā)達地區(qū)停車模式的發(fā)展方向應(yīng)以機械式立體停車庫和自走式停車庫結(jié)合；文獻[4] 采用靜態(tài)優(yōu)化方法待停車輛的信息不完整的情況下來探討一種快速動態(tài)停車算法和模型，并且通過仿真模型驗證.文獻[5]側(cè)重研究自動停車控制系統(tǒng)的實用性，建立基于激光雷達的自動泊車系統(tǒng)并應(yīng)用于 DARPA 城市挑戰(zhàn)賽.文獻[6]提出了適用于任何停車場結(jié)構(gòu)，以停車用時最短為目標函數(shù)的快速自動停車算法，通過計算機程序?qū)崿F(xiàn)并進行了驗證.本文以動態(tài)規(guī)劃算法和貪婪算法的混合算法解決二維背包問題，考慮了每輛車的進入或駛出后整體停車位狀態(tài)變化，尋求周期性的整體最優(yōu)解，最后通過軟件實現(xiàn)多層停車樓智能停車優(yōu)化.

1 模型建立

1.1 建模基本假設(shè)

為簡化背包問題，作如下假設(shè)：(1)停車樓每層可停車空間為矩形，不考慮轉(zhuǎn)彎處的較小奇異型空間、樓內(nèi)承重柱體面積、護欄厚度、電梯占用空間等；(2)停車位的規(guī)格可以容納各種類型的汽車，忽略特殊車輛的影響；(3)所有汽車均按指示?？寇囕v，在停車樓內(nèi)均按照單行道限速勻速行駛；(4)車道均符合所有車輛的最小平曲線半徑標準，忽略車輛出車時間；(5)停車樓已經(jīng)具備詳細的歷史泊車信息，并且進入停車樓的車輛要選擇預(yù)計離開時間段.

1.2 數(shù)學(xué)模型

在停車位數(shù)量有限、通道內(nèi)車輛保持安全車距，以及不超過停車場最大容量的約束下，建立以既定周期內(nèi)所有駛離停車場車輛的總駛離用時最少為目標的優(yōu)化模型.停車樓每一層樓都作為二維背包來看待，橫縱坐標分別為i和j，入口和出口分開，分別和圖1中上、下方向的旋轉(zhuǎn)坡道相銜接.

圖1 停車樓每層車位分布平面示意圖

旋轉(zhuǎn)車道共2條單向車道，1條只上不下，另1條只下不上，車輛上、下樓分別通過不同車道.計算每輛車駛離時間時要考慮下樓時間，每下一層樓的用時為固定值，不考慮坡道內(nèi)突發(fā)阻塞用時.目標函數(shù)(1)表示在b階段內(nèi)停車樓內(nèi)車輛駛出花費的總時間

目標函數(shù)：

(1)

(2)

(3)

(4)

以上變量均為整數(shù)，計算為小數(shù)時采用向下圓整.

以上各式中：式(3)限制停車樓內(nèi)停放車輛數(shù)不超過停車位數(shù)量；式(4)限制停車場內(nèi)?？寇囕v和行駛中車輛的總數(shù)不超過停車樓的最大安全容量.T為所有駛出停車場車輛的總用時；將待優(yōu)化周期內(nèi)時間以2h為單位分成若干時段，并依序排列，b為排列序號(b=1，2，…，n)；Mb為b時段內(nèi)停車樓內(nèi)車輛數(shù)量的最大值；f為樓層數(shù)；i,j分別為某一樓層停車位的橫縱坐標；tbfij為b時段f層(i,j)位置的車輛到本層出口的時間；t*為車輛沒下一層樓所用時間，單位小時；dfij為f層樓(i,j)位置車輛到本層出口的行駛路程，m；ebfij為0-1變量，當b時段f層(i,j)位置停放車輛時取1，否則取0；v為停車場內(nèi)勻速行駛速度，km/h；R為停車樓內(nèi)總停車位數(shù)量；L為停車樓長度；W為停車樓寬度；z1為橫向安全車距；z2為橫向安全車距；k1為橫向車道數(shù)；k2為縱向車道數(shù)；w1為橫向車道寬度；w2為縱向車道寬度，以上涉及長度、寬度變量單位均為m.

2 算法設(shè)計

本文的停車問題可以看作“二維背包問題”，屬于NP難問題.利用動態(tài)規(guī)劃算法為主線思想，每次決策依靠貪婪算法來進行優(yōu)化.本算法的基礎(chǔ)是可獲得的詳細歷史數(shù)據(jù)平均值作為判斷的依據(jù)，cb為b時段駛?cè)胪＼嚇堑能囕v歷史平均數(shù)；Gb為b時段駛離停車樓的車輛歷史平均數(shù)；且待駛?cè)胲囕v取卡時需選擇預(yù)計離開時段b*(參照b時段的劃分).

應(yīng)用動態(tài)規(guī)劃算法的主要流程如下.

1) 階段 以時間方式劃分階段，將待優(yōu)化周期內(nèi)時間以2 h為單位分成若干階段.階段數(shù)用b表示.

2) 狀態(tài) 從b時段開始時停車樓內(nèi)整體泊車位置為初始狀態(tài)，b+1時段開始時整體泊車位置為b階段結(jié)束狀態(tài).b階段的可達狀態(tài)記為Sb，此狀態(tài)起始時部分位置已經(jīng)配載完車輛.

3) 決策變量為Xbfij，以貪婪算法為核心的決策集P(Sb)流程圖見圖2.

4) 動態(tài)規(guī)劃的基本方程

(5)

圖2 決策方法邏輯圖

式中：Xbfij(Sk)=1表示b階段待停車輛在f層(i，j)位置泊車，否則為0.Ybfij(Sk)=1表示b階段有車輛在f層(i，j)位置并且駛離，否則為0.

5) 策略 從b階段開始到終止的所有泊車位置策略的集合.由Pn(Sb)表示，背包問題存在許多備選策略，本文通過貪婪算法確定b階段每一待停車輛泊車位置的最優(yōu)策略：Pn(Sb)={x111,x112,…,xfij}.本文選擇正序遞推法求得最優(yōu)策略集：Pn(Sb)={P1(S1),P2(S2),…,Pn(Sb)}.實際策略集由實際問題數(shù)據(jù)計算得出.

3 數(shù)值檢驗

3.1 算例

以現(xiàn)有某停車樓實際數(shù)據(jù)作為參照，停車樓共有4層，停車位450個，停車樓平面呈1∶2的矩形布置，南北進深50 m，東西跨度100 m，占地面積4 820 m，每層停車位基本平均；建筑層高為3 m，采用旋轉(zhuǎn)式坡道式，車道為3 m的車道.根據(jù)歷史數(shù)據(jù)得到歷史每天每個時段進入停車場的車輛數(shù)的平均值，并按12個時段為周期換算出每個時段進入車輛數(shù)占1 d進入車輛數(shù)的百分比，見表1.

3.2 結(jié)果分析

根據(jù)上述混合式啟發(fā)算法編輯C++程序，其中橫向車道數(shù)取2，縱向車道數(shù)取1，安全車距設(shè)定為10 m，平均車速限定為15 km/h，取1 d 12個時段作為計算周期.先對空閑停車樓隨機分配即停車輛及其駛離時段信息，然后分別輸入共進入200,500及1 000輛車的情況下各個時段分別駛?cè)胲囕v數(shù)的歷史平均值，并隨機分配給每輛進入車輛駛離時段，見表2.

同時根據(jù)相同的初始條件計算采用本文組合優(yōu)化算法、駛?cè)胲囕v首選距離出口最近的空位泊車、隨機泊車以及駛?cè)胲囕v首選距離出口最遠的空位泊車這4種泊車方式下所有計算時段內(nèi)駛離停車樓的車輛駛離所耗費總時間，并對結(jié)果進行比較分析，見表3.

表1 每天每時段進入停車樓車輛數(shù)平均值歷史數(shù)據(jù)

表2 駛離停車場車輛的用時

表3 不同方式駛離車輛總用時比值

根據(jù)表3結(jié)果可以看出,本方法確實對實際問題達到優(yōu)化效果，并且對較大數(shù)量的停車問題優(yōu)化效果更為明顯，但在更大規(guī)模的實驗中，由于車位限制，等時過長不具有實際意義，本算法在此算例中的1 000輛車進入規(guī)模試驗比其他規(guī)則減少耗時最為顯著，在12.1%～23.6%之間.但更大規(guī)模的實驗由于車位限制，等時過長不具有優(yōu)化的實際意義.

4 結(jié) 束 語

本文依據(jù)歷史數(shù)據(jù)對停車問題通過混合式啟發(fā)算法進行優(yōu)化，但是對新型停車設(shè)施或者突發(fā)性變化適用性不強，需要進一步以自動停車設(shè)施及路徑跟蹤為基礎(chǔ)，對已停車輛進行合理自動換位來提高資源利用率，并展開停車樓突發(fā)性事件特性研究，提高模型算法的適用性.

[1]張秀媛，董蘇華，蔡華民，等.城市停車規(guī)劃與管理[M].北京：中國建筑工業(yè)出版社，2006.

[2]王春洪，查秀萍.停車庫投資的可行性分析[J].中外房地產(chǎn)導(dǎo)報，2003(17):40-41.

[3]劉科為，曹麻茹.機械式與坡道式立體停車庫橫向比較研究[J].南方建筑，2006(3):20-21.

[4]ZIPS P, B?CK M, KUGI A. A fast motion planning algorithm for car parking based on static optimization[C]∥2013 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) November 3-7, 2013. Tokyo, Japan.

[5]MING F H, OZGUNER U, A parking algorithm for an autonomous vehicle in proc[J]. IEEE Intelligent Vehicles Symposium. Eindhoven, The Netherlands, 2008(4/6):1155-1160.

[6]KONDAK K, HOMMEL G. Computation of time optimal movements for autonomous parking of non-holonomic mobile platforms[C]∥ Int. Conf. on Robotics & Automation, Seoul, Korea, 2001(3):2698-2703.

Optimization on the Intelligent Parking for a Parking Building Based on Dynamic Programming and Greedy Algorithms

ZHAO Wei1,2)XU Liangjie1)YAO Yihu1)WANG Guanyun1)LI Ge2)

(SchoolofTransportation,WuhanUniversityofTechnology,Wuhan430063，China)1)(CollegeofEconomicsandBusiness,InnerMongoliaUniversityofScience&Technology,Baotou014010,China)2)

Aiming at all types chaos of the multilayer parking management system , time-consuming process and obstruction caused by disorderly parking, according to parking building layout, parking historical database and the information to be parked vehicles, a two-dimensional backpack model is established. A heuristic combined algorithm is proposed by integrating dynamic programming and the greedy algorithm, aiming at making every coming vehicle park in order , optimizing the allocation of resources, reducing parking time and channel blockage and improving parking building utilization.

parking building; greedy algorithm; dynamic programming algorithm; dimensional knapsack problem

2014-11-25

*國家青年科學(xué)基金項目資助(批準號：51108361，51208400)

U491.4

10.3963/j.issn.2095-3844.2015.03.012

趙 瑋(1988- ):男，博士，講師，主要研究領(lǐng)域為交通運輸規(guī)劃與管理.