平面移動(dòng)式立體車庫(kù)動(dòng)態(tài)庫(kù)位分配策略建模與仿真

李建國(guó)，李博文，楊 波

(蘭州交通大學(xué) 自動(dòng)化與電氣工程學(xué)院，蘭州 730070)

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

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

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

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

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

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

圖1 平面移動(dòng)式車庫(kù)的立體模型Fig. 1 Stereo model of plane mobile garage

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

1.1 顧客的等待隊(duì)長(zhǎng)L

L=m+n,

(1)

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

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

(2)

1.3 單次復(fù)合作業(yè)的服務(wù)時(shí)間

1)單次同層復(fù)合作業(yè)的服務(wù)時(shí)間Tserve1

(3)

2)單次跨層復(fù)合作業(yè)的服務(wù)時(shí)間Tserve2

(4)

1.4 顧客的等待時(shí)間Twait

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

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

(5)

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

(6)

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

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

(7)

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

(8)

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

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

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

蜻蜓個(gè)體的避撞行為位移公式

(9)

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

(10)

聚集行為位移公式

(11)

捕食行為位移公式

Fi=X+-Xi。

(12)

避敵行為位移公式

Ei=X-+Xi。

(13)

綜合上述5種蜻蜓群體行為，蜻蜓個(gè)體的步長(zhǎng)向量更新策略公式

Δ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個(gè)蜻蜓個(gè)體在種群行為中產(chǎn)生的位移；Xi表示第i個(gè)蜻蜓個(gè)體位置；Xj表示第j個(gè)蜻蜓個(gè)體位置；N表示與第i個(gè)蜻蜓個(gè)體相鄰的蜻蜓數(shù)量；X+表示食物所在位置，X-表示天敵所在位置；s，a，c，f，e分別為5種蜻蜓群體行為權(quán)重；w表示慣性權(quán)重；t為當(dāng)前迭代次數(shù)；ΔXt+1表示在t+1代種群更新步長(zhǎng)，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ò)算法通過(guò)信號(hào)正向傳播和誤差信號(hào)反向傳播來(lái)動(dòng)態(tài)迭代修正網(wǎng)絡(luò)的權(quán)值和閾值，使誤差函數(shù)達(dá)到期望要求。

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

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

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

(16)

通過(guò)蜻蜓種群的5種行為模式，使蜻蜓個(gè)體不斷搜索，最終尋找到最優(yōu)解位置。將蜻蜓算法搜索到的最優(yōu)解作為BP神經(jīng)網(wǎng)絡(luò)權(quán)值和閾值的初始選擇值，可以縮短神經(jīng)網(wǎng)絡(luò)訓(xùn)練時(shí)間，提高預(yù)測(cè)結(jié)果的準(zhǔn)確性。蜻蜓算法優(yōu)化BP神經(jīng)網(wǎng)絡(luò)的實(shí)驗(yàn)流程圖如圖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é)點(diǎn)數(shù)分別為1，6，1；隱藏層的傳遞函數(shù)選取為logsig函數(shù)，輸出層的傳遞函數(shù)為purelin函數(shù)，學(xué)習(xí)率為0.01；以車輛到達(dá)時(shí)間作為輸入量，停留時(shí)間作為輸出量。通過(guò)對(duì)平面移動(dòng)式立體車庫(kù)實(shí)際運(yùn)行數(shù)據(jù)進(jìn)行統(tǒng)計(jì)分析，選取500組車輛到達(dá)和停留時(shí)間數(shù)據(jù)作為實(shí)驗(yàn)數(shù)據(jù)，其中450組數(shù)據(jù)作為訓(xùn)練集，50組數(shù)據(jù)作為測(cè)試集，采用監(jiān)督學(xué)習(xí)算法對(duì)神經(jīng)網(wǎng)絡(luò)進(jìn)行訓(xùn)練，訓(xùn)練次數(shù)為2 000次；蜻蜓算法的種群規(guī)模設(shè)置為200，迭代次數(shù)為400次，實(shí)驗(yàn)仿真結(jié)果如圖4所示。

圖4 車輛停留時(shí)間預(yù)測(cè)圖Fig. 4 Prediction of vehicle stay time

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

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

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

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

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

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

4.1 基于禁忌搜索算法的實(shí)驗(yàn)設(shè)計(jì)

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

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

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

4.2 實(shí)驗(yàn)仿真與數(shù)據(jù)分析

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

圖6 立體車庫(kù)評(píng)價(jià)指標(biāo)數(shù)據(jù)Fig. 6 Evaluation index data of stereo garage

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

表1 不同優(yōu)化算法下立體車庫(kù)的評(píng)價(jià)指標(biāo)數(shù)據(jù)

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

5 結(jié) 論

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

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

2)采用此組合方案可以更為有效地減少顧客等待隊(duì)長(zhǎng)，縮短顧客等待時(shí)間和車輛服務(wù)時(shí)間，降低立體車庫(kù)運(yùn)行能耗，提高顧客的滿意程度。

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