李建國，李博文，楊 波

(蘭州交通大學 自動化與電氣工程學院，蘭州 730070)

隨著社會經(jīng)濟不斷發(fā)展，城市機動車數(shù)量日益增多，停車困難與城市發(fā)展之間的矛盾日益突出。為有效緩解城市停車困難的問題，平面移動式立體車庫以其占地面積小，車庫容量大，自動化程度高等優(yōu)點得到了廣泛的認可和應用。

平面移動式立體車庫在建設(shè)過程中可以有效地提高城市空間利用率，但本身也存在顧客等待時間過長，車輛出入庫效率低下的局限性。為解決此類問題江代君[1]根據(jù)車輛到達率的變化，提出將調(diào)度堆垛機數(shù)量和運行速度相結(jié)合的調(diào)度策略，但研究過程中未考慮車輛停留時間的狀態(tài)因素；王小農(nóng)[2]等人提出了基于神經(jīng)網(wǎng)絡(luò)和果蠅算法相結(jié)合的立體車庫車位分配決策模型，但單一神經(jīng)網(wǎng)絡(luò)對車輛停留時間預測準確率較低，進而影響車庫車位分配效率；張海飛[3]等人則以排隊論為理論基礎(chǔ)，分析了單服務臺系統(tǒng)車庫的布局方案，以提高立體車庫服務效率；文獻[4-5]分別通過遺傳算法[4]，改進遺傳[5]，模擬退火[5]對立體車庫車位分配過程進行優(yōu)化研究。

目前對立體車庫效率研究大多集中于堆垛機的調(diào)度策略[6]、車庫布局方式[7]以及智能算法與調(diào)度策略[8]的結(jié)合，未考慮車輛停留時間以及車位分配過程中庫位變化狀態(tài)對立體車庫服務效率的影響[9-10]。

筆者提出一種立體車庫動態(tài)庫位分配策略：首先以蜻蜓算法優(yōu)化的BP神經(jīng)網(wǎng)絡(luò)為理論依據(jù)，提高對車輛在庫內(nèi)停留時間的預測準確性；其次通過車庫車輛的停留時間，選擇車庫內(nèi)較大概率進行出車任務的車位區(qū)域；最后利用禁忌搜索算法較強的全局尋優(yōu)能力搜索出此區(qū)域內(nèi)最適宜的車位位置。同時，將此組合方案與遺傳算法和模擬退火算法的優(yōu)化效果進行對比分析，用以說明該策略的可行性和有效性，為立體車庫的建設(shè)提供參考依據(jù)。

1 立體車庫的數(shù)學模型

平面移動式立體車庫的立體模型如圖1所示，車庫結(jié)構(gòu)為p層q列，車廳(I/O)負責車輛的進出，調(diào)度設(shè)備是搬運器(RGV, rail-guided vehicle)和升降機(Lift)，其中RGV負責車輛在x軸方向的水平橫移運動，lift負責車輛在y軸方向的垂直升降運動。

圖1 平面移動式車庫的立體模型Fig. 1 Stereo model of plane mobile garage

由于車輛的存取調(diào)度操作需要RGV與Lift協(xié)同完成，當立體車庫進行多個調(diào)度任務時，RGV與Lift存在同層與跨層2種復合工作方式。選取雙車廳平面移動式立體車庫為研究對象，在車庫中配置有2臺RGV與Lift。設(shè)雙車廳立體車庫I/Oi的位置坐標為(ai,bi), I/Oj的位置坐標為(aj,bj)；調(diào)度設(shè)備需要在(xa,yb)處存車，在(xc,yd)處取車；RGV的水平運行功率為Px，運行速度為Vx，Lift的垂直運行功率為Py，運行速度為Vy；車位的寬為L，高為H。以顧客的等待隊長，等待時間，服務時間和車庫運行能耗作為立體車庫服務效率評價指標，則評價指標的數(shù)學表達式如下所示

1.1 顧客的等待隊長L

L=m+n,

(1)

式中:m，n分別表示排隊隊列中存車和取車的顧客數(shù)量。

1.2 單次存車或取車作業(yè)的服務時間Tserve0

(2)

1.3 單次復合作業(yè)的服務時間

1)單次同層復合作業(yè)的服務時間Tserve1

(3)

2)單次跨層復合作業(yè)的服務時間Tserve2

(4)

1.4 顧客的等待時間Twait

顧客的等待時間為多次復合作業(yè)服務時間的總和，假設(shè)顧客到達時，需要等待A次存車任務，B+C+D次取車任務(其中B次為同層復合取車任務，C次為跨層復合取車任務，D次為單次取車任務)，才能接受服務，則顧客的等待時間Twait

Twait=B*Tserver1+C*Tserver2+[(A+D)-(B+C)]*Tserver0。

(5)

1.5 單次存車或者取車作業(yè)的運行能耗Wenergy0

(6)

1.6 單次復合作業(yè)的運行能耗

1)同層復合作業(yè)的運行能耗Wenergy1

(7)

2)跨層復合作業(yè)的運行能耗Wenergy2

(8)

2 蜻蜓算法優(yōu)化神經(jīng)網(wǎng)絡(luò)預測模型

2.1 蜻蜓優(yōu)化算法

蜻蜓算法(DA, dragonfly algorithm)是通過對蜻蜓種群避撞，結(jié)隊，聚集，捕食以及避敵5種行為模式進行數(shù)學建模的群智能優(yōu)化算法[11]。

蜻蜓個體的避撞行為位移公式

(9)

結(jié)隊行為位移公式

(10)

聚集行為位移公式

(11)

捕食行為位移公式

Fi=X+-Xi。

(12)

避敵行為位移公式

Ei=X-+Xi。

(13)

綜合上述5種蜻蜓群體行為，蜻蜓個體的步長向量更新策略公式

ΔXt+1=(sSi+aAi+cCi+fFi+eEi)+wΔXt。

(14)

蜻蜓種群位置更新策略公式為

Xt+1=Xt+ΔXt+1。

(15)

式中：Si，Ai，Ci，F(xiàn)i，Ei分別表示第i個蜻蜓個體在種群行為中產(chǎn)生的位移；Xi表示第i個蜻蜓個體位置；Xj表示第j個蜻蜓個體位置；N表示與第i個蜻蜓個體相鄰的蜻蜓數(shù)量；X+表示食物所在位置，X-表示天敵所在位置；s，a，c，f，e分別為5種蜻蜓群體行為權(quán)重；w表示慣性權(quán)重；t為當前迭代次數(shù)；ΔXt+1表示在t+1代種群更新步長，Xt+1表示第t+1代種群位置。

2.2 蜻蜓算法優(yōu)化BP神經(jīng)網(wǎng)絡(luò)

BP(back propagation)神經(jīng)網(wǎng)絡(luò)是一種多層前饋網(wǎng)絡(luò)[12]，通常為輸入層，隱藏層，輸出層3層網(wǎng)絡(luò)結(jié)構(gòu)，神經(jīng)網(wǎng)絡(luò)模型如圖2所示。BP神經(jīng)網(wǎng)絡(luò)算法通過信號正向傳播和誤差信號反向傳播來動態(tài)迭代修正網(wǎng)絡(luò)的權(quán)值和閾值，使誤差函數(shù)達到期望要求。

圖2 BP神經(jīng)網(wǎng)絡(luò)模型Fig. 2 BP neural network model

由于神經(jīng)網(wǎng)絡(luò)權(quán)值和閾值的初始選擇值對最終訓練結(jié)果影響較大，且存在收斂速度較慢，訓練結(jié)果易陷入局部最優(yōu)解的局限性，整體預測精度不高[13]。而蜻蜓算法具有良好的全局尋優(yōu)能力，通過蜻蜓算法來優(yōu)化神經(jīng)網(wǎng)絡(luò)的權(quán)值與閾值，可以提高神經(jīng)網(wǎng)絡(luò)的預測精度。蜻蜓算法優(yōu)化BP神經(jīng)網(wǎng)絡(luò)的實驗步驟：

Step1：初始化BP神經(jīng)網(wǎng)絡(luò)模型，確定神經(jīng)網(wǎng)絡(luò)的層數(shù)，權(quán)值w以及閾值θ，傳遞函數(shù)，訓練函數(shù)，以及各層的節(jié)點數(shù)；Step2：樣本數(shù)據(jù)處理，設(shè)置訓練樣本集和測試樣本集，并對數(shù)據(jù)進行歸一化處理；Step3：DA算法初始化，確定蜻蜓種群規(guī)模N和迭代次數(shù)T，將神經(jīng)網(wǎng)絡(luò)的權(quán)值w和閾值θ有序排列組成(w,θ)行向量，作為蜻蜓個體位置x，根據(jù)權(quán)值和閾值范圍隨機初始化蜻蜓個體位置；Step4：將訓練樣本數(shù)據(jù)輸入BP神經(jīng)網(wǎng)絡(luò)，根據(jù)適應度函數(shù)計算蜻蜓個體的適應度值，并記錄當前最優(yōu)解；選擇均方誤差為適應度函數(shù)，其數(shù)學表達式為

(16)

通過蜻蜓種群的5種行為模式，使蜻蜓個體不斷搜索，最終尋找到最優(yōu)解位置。將蜻蜓算法搜索到的最優(yōu)解作為BP神經(jīng)網(wǎng)絡(luò)權(quán)值和閾值的初始選擇值，可以縮短神經(jīng)網(wǎng)絡(luò)訓練時間，提高預測結(jié)果的準確性。蜻蜓算法優(yōu)化BP神經(jīng)網(wǎng)絡(luò)的實驗流程圖如圖3所示。

圖3 蜻蜓算法優(yōu)化神經(jīng)網(wǎng)絡(luò)Fig. 3 Dragonfly algorithm optimizes the neural network

神經(jīng)網(wǎng)絡(luò)的具體設(shè)置參數(shù)：輸入層，隱藏層，輸出層的節(jié)點數(shù)分別為1，6，1；隱藏層的傳遞函數(shù)選取為logsig函數(shù)，輸出層的傳遞函數(shù)為purelin函數(shù)，學習率為0.01；以車輛到達時間作為輸入量，停留時間作為輸出量。通過對平面移動式立體車庫實際運行數(shù)據(jù)進行統(tǒng)計分析，選取500組車輛到達和停留時間數(shù)據(jù)作為實驗數(shù)據(jù)，其中450組數(shù)據(jù)作為訓練集，50組數(shù)據(jù)作為測試集，采用監(jiān)督學習算法對神經(jīng)網(wǎng)絡(luò)進行訓練，訓練次數(shù)為2 000次；蜻蜓算法的種群規(guī)模設(shè)置為200，迭代次數(shù)為400次，實驗仿真結(jié)果如圖4所示。

圖4 車輛停留時間預測圖Fig. 4 Prediction of vehicle stay time

從仿真結(jié)果中可知初始BP神經(jīng)網(wǎng)絡(luò)模型預測精度不高，誤差較大，預測結(jié)果的整體準確率為63.2%；而DA-BP組合模型，由于優(yōu)化了神經(jīng)網(wǎng)絡(luò)的閾值與權(quán)值，減少了神經(jīng)網(wǎng)絡(luò)訓練誤差，提高了預測精度，預測結(jié)果的整體準確率為90.4%，比單一BP神經(jīng)網(wǎng)絡(luò)的預測精度提高了27.2%，整體預測性較好。

3 車位分配三維圖形的建立

立體車庫車位分配三維圖形在建立過程中，以DA-BP組合模型獲得的車輛停留時間和車位位置坐標為軸線建立三維立體圖形，通過其在平面坐標上的投影圖形來選擇車位。由于存在多個車輛停留時間相同或相近的情況，并且在車庫作業(yè)過程中庫位狀態(tài)是動態(tài)變化的過程，所以以區(qū)域選擇的方式來動態(tài)選擇車位。

圖5為實驗仿真過程中車位分配的三維立體圖形(a)和其俯視圖(b)，(c，d，e)分別為每間隔30 min后車庫車位動態(tài)變化的狀態(tài)圖，其中X軸，Y軸分別表示車庫的層和列，即庫位的位置坐標，Z軸則表示車輛在庫內(nèi)停留時間。在俯視圖(b)中，車輛在庫內(nèi)停留時間長短用不同顏色的深淺來區(qū)分表示，停留時間較長的車位區(qū)域用黃色區(qū)域表示，停留時間較短車位區(qū)域用藍色區(qū)域表示，且停留時間越短顏色越深，則這一區(qū)域的車輛有較大的概率進行出車作業(yè)(圖中紅色方框區(qū)域)。在進行存車任務時則優(yōu)先考慮藍色較深區(qū)域的車位，以適應系統(tǒng)可能發(fā)生的出車請求任務，達到存車與取車兼顧，減少調(diào)度設(shè)備空載運行距離，縮短顧客等待時間的目的。

圖5 立體車庫動態(tài)庫位分配Fig. 5 Dynamic location allocation of stereo garage

4 基于禁忌搜索的庫位分配優(yōu)化方案

4.1 基于禁忌搜索算法的實驗設(shè)計

禁忌搜索算法(TS, tabu search)是一種啟發(fā)式隨機搜索算法，它從一個初始可行解出發(fā)，通過引入靈活的存儲結(jié)構(gòu)和禁忌準則來避免迂回搜索，同時通過特赦準則來赦免一些被禁忌的優(yōu)良狀態(tài)，進而實現(xiàn)讓目標函數(shù)值向全局最優(yōu)解移動[14-16]。

通過車位分配圖形的建立，選擇出有較大概率進行出車作業(yè)的庫位位置坐標區(qū)域，再用禁忌搜索算法進行尋優(yōu)搜索，禁忌搜索算法的實驗設(shè)計步驟如下所示：

Step1：選擇俯視圖深藍色區(qū)域中的某一空閑車位作為初始解xnow，將初始車位周圍鄰近車位作為候選解，確定禁忌對象與禁忌長度，并令禁忌表為空；Step2：選擇特定方向進行禁忌移動，選取公式(16)作為適應度函數(shù)，找出候選解中的最優(yōu)解xbest，并令xnow=xbest，記錄最優(yōu)解，同時更新禁忌表；Step3：比較候選解中的xbest與禁忌表中的最優(yōu)解xnow，若xbest>xnow，則忽視禁忌準則，更新最優(yōu)值；若xbest

4.2 實驗仿真與數(shù)據(jù)分析

保持神經(jīng)網(wǎng)絡(luò)的實驗設(shè)計參數(shù)不變，TS算法中禁忌對象為車位位置，禁忌長度為3，車庫系統(tǒng)服務規(guī)則為先到先服務原則，RGV待命位策略為存車優(yōu)先策略，顧客的客源數(shù)為500，車輛到達率為15.7輛/min，采用MATLAB2014進行仿真實驗，立體車庫評價指標數(shù)據(jù)的實驗仿真結(jié)果如圖6所示。

圖6 立體車庫評價指標數(shù)據(jù)Fig. 6 Evaluation index data of stereo garage

從實驗仿真結(jié)果中可知顧客平均等待時間為2.94 min，平均服務時間1.38 min，平均等待隊長為4.5個，立體車庫平均運行能耗為1 403 KJ。多次進行仿真實驗，實驗結(jié)果取平均值，將DA-BP模型與禁忌搜索算法的動態(tài)組合方案與遺傳算法(GA, genetic algorithm)，模擬退火算法(SA, simulated annealing)優(yōu)化效果進行對比分析，實驗仿真結(jié)果如表1所示。

表1 不同優(yōu)化算法下立體車庫的評價指標數(shù)據(jù)

從表1中可知，組合方案優(yōu)化下的評價指標數(shù)據(jù)均為最小值，同比于遺傳算法與模擬退火算法優(yōu)化，顧客的平均等待時間，平均服務時間，平均等待隊長和立體車庫運行能耗優(yōu)化效率分別提高了39.6%和32.5%，33.3%和22.2%，13.2%和9.8%，18.5%和13.3%，具有更好的優(yōu)化效果。

5 結(jié) 論

以平面移動式立體車庫的車位分配策略為研究對象，建立了立體車庫數(shù)學模型，提出DA-BP預測模型與禁忌搜索算法的動態(tài)車位分配方案，并將此方案與現(xiàn)有庫位分配優(yōu)化方式進行了對比分析，研究結(jié)果表明：

1)動態(tài)庫位分配策略在預測車輛停留時間的基礎(chǔ)上，根據(jù)庫位變化狀態(tài)來動態(tài)選擇分配車位，可以達到存車任務與出車請求兼顧，減少調(diào)度設(shè)備空載運行距離，提升立體車庫整體作業(yè)效率的目的。

2)采用此組合方案可以更為有效地減少顧客等待隊長，縮短顧客等待時間和車輛服務時間，降低立體車庫運行能耗，提高顧客的滿意程度。

但是在動態(tài)庫位分配策略研究中車輛停留時間預測存在誤差，在今后的研究中需要進一步研究車輛停留時間預測出現(xiàn)偏差時對立體車庫作業(yè)效率的影響。