基于動態規劃和貪婪算法的停車樓智能停車優化方法*

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

(武漢理工大學交通學院1) 武漢 430063) (內蒙古科技大學經濟與管理學院2) 包頭 014010)

基于動態規劃和貪婪算法的停車樓智能停車優化方法*

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

(武漢理工大學交通學院1)武漢 430063) (內蒙古科技大學經濟與管理學院2)包頭 014010)

針對各種類型的立體停車樓停車管理系統混亂、無序導致泊車及出車過程費時并易引起停車樓通道阻塞等問題，根據停車樓布局、歷史停車數據庫及待停車輛的信息，建立了二維背包模型，并將動態規劃算法和貪婪算法相融合，提出啟發式組合算法，使每一待停車輛進入停車場時即獲取泊車位指示以便有序?？浚瑑灮臻e停車資源分配，減少車輛在停車樓內停留總時間和通道阻塞，提高停車樓利用率.

停車樓；貪婪算法；動態規劃算法；二維背包問題

0 引 言

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

1 模型建立

1.1 建?；炯僭O

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

1.2 數學模型

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

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

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

目標函數：

(1)

(2)

(3)

(4)

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

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

2 算法設計

本文的停車問題可以看作“二維背包問題”，屬于NP難問題.利用動態規劃算法為主線思想，每次決策依靠貪婪算法來進行優化.本算法的基礎是可獲得的詳細歷史數據平均值作為判斷的依據，cb為b時段駛入停車樓的車輛歷史平均數；Gb為b時段駛離停車樓的車輛歷史平均數；且待駛入車輛取卡時需選擇預計離開時段b*(參照b時段的劃分).

應用動態規劃算法的主要流程如下.

1) 階段 以時間方式劃分階段，將待優化周期內時間以2 h為單位分成若干階段.階段數用b表示.

2) 狀態 從b時段開始時停車樓內整體泊車位置為初始狀態，b+1時段開始時整體泊車位置為b階段結束狀態.b階段的可達狀態記為Sb，此狀態起始時部分位置已經配載完車輛.

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

4) 動態規劃的基本方程

(5)

圖2 決策方法邏輯圖

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

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

3 數值檢驗

3.1 算例

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

3.2 結果分析

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

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

表1 每天每時段進入停車樓車輛數平均值歷史數據

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

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

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

4 結 束 語

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

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

[2]王春洪，查秀萍.停車庫投資的可行性分析[J].中外房地產導報，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

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

U491.4

10.3963/j.issn.2095-3844.2015.03.012

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