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

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

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

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

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

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

停車(chē)樓；貪婪算法；動(dòng)態(tài)規(guī)劃算法；二維背包問(wèn)題

0 引 言

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

1 模型建立

1.1 建模基本假設(shè)

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

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

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

圖1 停車(chē)樓每層車(chē)位分布平面示意圖

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

目標(biāo)函數(shù)：

(1)

(2)

(3)

(4)

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

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

2 算法設(shè)計(jì)

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

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

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

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

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

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

(5)

圖2 決策方法邏輯圖

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

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

3 數(shù)值檢驗(yàn)

3.1 算例

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

3.2 結(jié)果分析

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

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

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

表2 駛離停車(chē)場(chǎng)車(chē)輛的用時(shí)

表3 不同方式駛離車(chē)輛總用時(shí)比值

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

4 結(jié) 束 語(yǔ)

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

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

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

[3]劉科為，曹麻茹.機(jī)械式與坡道式立體停車(chē)庫(kù)橫向比較研究[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

*國(guó)家青年科學(xué)基金項(xiàng)目資助(批準(zhǔn)號(hào)：51108361，51208400)

U491.4

10.3963/j.issn.2095-3844.2015.03.012

趙 瑋(1988- ):男，博士，講師，主要研究領(lǐng)域?yàn)榻煌ㄟ\(yùn)輸規(guī)劃與管理.