基于改進集束搜索的立體車庫庫位布局優(yōu)化研究

常立丹，李建國，李博文

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

自動化立體車庫在解決城市靜態(tài)交通問題方面起著越來越重要的作用，汽車保有量的日益增長和土地資源的稀缺更推動了自動化立體車庫的發(fā)展。與此同時，自動化立體車庫的出現(xiàn)在一定程度上縮短了車輛的存取時間，降低了資源的浪費。但其也存在一定的局限性，例如存取車效率較低、顧客等待時間長和運行能耗較高等問題。

目前，對自動化立體倉庫的研究較多且較全面，在考慮倉儲系統(tǒng)內(nèi)部搬運器與升降機調(diào)度問題時，主要將車輛存取過程抽象為旅行售貨員問題（travel salesmen problem，TSP）［1］。采用遺傳算法［2］、多目標集成優(yōu)化［3］、系統(tǒng)智能預(yù)測［4］對立體倉儲系統(tǒng)進行調(diào)度分析。

對于立體車庫調(diào)度優(yōu)化的研究，呂洪柱等［5］針對大型立體停車庫存取車控制問題，設(shè)計了一種智能存取車控制算法，解決了多臺車輛同時存取的經(jīng)濟效益權(quán)衡和安全問題。陳博等［6］通過改機遺傳算法對堆垛機運行路徑進行了優(yōu)化。丁彩虹等［7］采用PLC對車庫系統(tǒng)進行控制操作。

針對尋找最優(yōu)路徑的研究，李建國等以堆垛機運行最短路徑為目標，建立了堆垛機復(fù)合作業(yè)和單一作業(yè)的數(shù)學(xué)模型，利用改進遺傳算法對存取車序列進行優(yōu)化，并與傳統(tǒng)的存取車作業(yè)方式進行對比，結(jié)果取得了明顯的效果［8］。李劍鋒等［9］以總存取時間為目標函數(shù)建立了數(shù)學(xué)模型，利用改進遺傳算法，采用混合編碼、改良的OX交叉算子對車庫存取序列進行優(yōu)化，獲得了預(yù)期的車輛存取優(yōu)化序列。黃衛(wèi)平等［10］以費用最小為目標，將集束搜索算法應(yīng)用到隨機型混合模式裝配線平衡問題中，得到了較好的效果。羅曉冬等［11］采用Dijkstra算法并結(jié)合深度優(yōu)先遍歷算法篩選出任意2個節(jié)點間的所有最短路徑，并找出花費代價最小的路徑。

本文以北京市某立體車庫實際運行數(shù)據(jù)為依據(jù)，以運行時間最短為目標，提出了一種改進集束搜索算法對立體車庫堆垛機作業(yè)路徑進行建模與優(yōu)化，并對實驗仿真結(jié)果進行分析，為立體車庫選擇合理的布局提供參考。

1 背景介紹

1.1 立體車庫實體模型

立體車庫主要由車廳、巷道、停車位、堆垛機和搬運器等組成，可以根據(jù)場地和高度的不同要求建成多種結(jié)構(gòu)形式。立體車庫本身是三維實體［12］，本文將堆垛機選擇巷道的操作方向定為x軸方向，將堆垛機選擇所要進行存取操作列的方向定為y軸方向，將選擇所在層的操作方向定為z軸方向。

由于存取車作業(yè)是三維運動［13］，即在巷道內(nèi)所進行一次存取車操作可分解為3個分方向上的運動：巷道方向上的水平運動X，用來選擇巷道，并實現(xiàn)存取操作；垂直升降運動Z，即存取車位點所在的層j，用來選擇車位所處的層；橫向存取運動Y，即存取車位點所在的列i。對于不同的車位而言，X方向上的操作相同，因此可將模型簡化為單巷道內(nèi)（Y，Z）的二維運動，即尋找存取車位點（i，j）。由立體車庫簡化成的單巷道實體模型進行分析，將立體車庫模型簡化，取I/O口位置為坐標原點O，取選擇存取位置所列的方向為i軸，取選擇存取位置所在層的方向為j軸，取單側(cè)車位進行分析，立體車庫立體示意圖如圖1所示。

《車庫建筑設(shè)計規(guī)范（2015）》規(guī)定，1個 I/O口對應(yīng)約50個停車位，I/O口處應(yīng)設(shè)置不少于2個的候車位，當(dāng)I/O口分開設(shè)置時，候車位不應(yīng)少于1個。考慮立體車庫整體的造價，立體車庫建造的最低層數(shù)為3層。堆垛機水平速度v1=80 m/min，垂直速度v2=20 m/min。車庫車位的長L0=5 m，寬W0=2 m，高H0=1.8 m，但是規(guī)范中明顯缺少了對車位如何進行布局的規(guī)定。

1.2 立體車庫排隊模型

排隊論是一套主要研究系統(tǒng)隨機聚散現(xiàn)象以及隨機服務(wù)系統(tǒng)工作過程特點的數(shù)學(xué)理論和方法，通過對服務(wù)對象數(shù)量指標的統(tǒng)計，得出服務(wù)對象與服務(wù)系統(tǒng)之間存在的規(guī)律，并根據(jù)規(guī)律重新調(diào)整服務(wù)機構(gòu)及組織服務(wù)對象，使得保證服務(wù)對象在滿足需要的基礎(chǔ)上服務(wù)系統(tǒng)的經(jīng)濟效益得到優(yōu)化［14］。

結(jié)合北京市某醫(yī)院自動化立體車庫，它作為一個服務(wù)機構(gòu)，到達的車輛可視為顧客，且車輛到達和服務(wù)時間均是隨機的。根據(jù)排隊論基本思想，可將立體車庫存取車輛的過程看作1個排隊系統(tǒng)，該系統(tǒng)主要由輸入過程、服務(wù)機構(gòu)和排隊規(guī)則3部分組成，如圖2所示。

自動化立體車庫對車輛進行存取操作時，考慮復(fù)合作業(yè)方式。當(dāng)對A車輛進行存儲后，若B位置隨即有出庫任務(wù)，則堆垛機執(zhí)行取車操作，即每次車庫的作業(yè)方式為復(fù)合作業(yè)方式，如圖3所示。若完成車輛入庫后，無出庫任務(wù)，則堆垛機返回出入口待命。

在車庫排隊系統(tǒng)中，其運行參考指標主要包括：

1）顧客到達率為λ，顧客服務(wù)率為μ；

2）整個車庫系統(tǒng)中的顧客平均等待的隊長Lq和等待時間Wq；

自動化立體車庫有一個排隊隊列，有s個堆垛機參與存取任務(wù)，而且各個堆垛機之間相互獨立，定義服務(wù)強度 ρs=λ/（sμ）。

則空閑概率P0為：

其中，a表示排隊系統(tǒng)中有a個堆垛機正在參與服務(wù)，且0≤a＜s。

在排隊系統(tǒng)中，只有當(dāng)準備接收服務(wù)的車輛i大于堆垛機的數(shù)量s時，才會出現(xiàn)車輛排隊等待，所以等待服務(wù)車輛的平均數(shù)為：

堆垛機將車輛A進行存儲所需時間T1為：

堆垛機將車輛A進行存儲后，隨即對車輛B進行取車，所需時間T2為：

堆垛機將車輛B運送到出入口所需時間T3為：

則堆垛機在庫內(nèi)運行時間T為：

則系統(tǒng)運行時顧客的平均等待時間為：

其中，k表示停放車輛數(shù)，M表示車庫停車位個數(shù)，i、j分別表示車庫的列數(shù)和層數(shù)。

1.3 改進集束搜索算法

集束搜索算法（beam search algorithm，BSA）是一種啟發(fā)式圖搜索算法，其基本思想與分支定界法類似，但二者有一定的區(qū)別，主要表現(xiàn)在集束搜索算法不是對所有節(jié)點進行分支，為了減少節(jié)點搜索過程中所占用的空間和時間，在對每一個節(jié)點進行深度擴展時，對一些質(zhì)量較差的節(jié)點進行裁剪，保留一些質(zhì)量較高的節(jié)點。在搜索過程中對節(jié)點進行裁剪既節(jié)約了空間，又提高了效率。

針對一個搜索樹，首先要確定一個叫束寬（beam width，bw）的參數(shù)。集束搜索首先根據(jù)某種準則，選擇bw個最優(yōu)的節(jié)點作為束節(jié)點（beam node）。如圖4所示，第1層中的2個（bw=2）陰影節(jié)點，中間的那個節(jié)點就被忽略不計了，不再對其進行分支［15］。

對于每個束節(jié)點即陰影節(jié)點，以該節(jié)點作為搜索起始點，再進行分支，根據(jù)某種篩選規(guī)則對其子節(jié)點進行選擇，將其中最優(yōu)的一個節(jié)點作為束節(jié)點，而對其余節(jié)點不再進行分支。然后，再對選擇的最優(yōu)的節(jié)點進行分支，以此類推，直到葉節(jié)點。最后，得到bw個代表備選方案的束，對比不同的方案并選擇最優(yōu)的作為輸出。

集束搜索方法其實提供了一種找最優(yōu)解的思路，就是說在適當(dāng)?shù)那闆r下，可以剪掉一些可信度低的路徑，在實際使用中，可以每層的集束寬度不一致，比如在初始的一些層次中多保留一些結(jié)果，在后邊就可以放心大膽地進行剪枝。

由于傳統(tǒng)集束搜索方法存在常數(shù)線寬大小影響求解效果的問題，因此本研究對傳統(tǒng)集束搜索算法進行改進［16］，新算法的主要思路是將經(jīng)典算法中的束進行分組，通過引入懲罰機制，使得每組的相似度盡量低，保證生成的解相互之間差異更大一些，即滿足了多樣性的需求，在每組束中用經(jīng)典算法進行優(yōu)化搜索。

2 立體車庫庫位布局分析

以北京市某醫(yī)院自動化立體車庫為例，該車庫布局為4層7列雙排對列布設(shè)，單巷道，單I/O口，堆垛機數(shù)量為1臺。但在該配置及布局下，車庫在實際運行過程中，尤其是存取車高峰期，存在排隊過長、顧客等待和接收服務(wù)時間過長的現(xiàn)象。由此可以看出設(shè)備配置及庫位布局會在一定程度上對立體車庫的整體運行造成影響。因此，為保證立體車庫具有較高的運行效率，在對立體車庫進行設(shè)計時需考慮整體庫位布局及合理數(shù)量的設(shè)備配置。本文將參考該立體車庫的設(shè)備配置，討論不同的車庫布局對顧客平均等待時間及平均等待隊長等因素的影響。

2.1 立體車庫運行參數(shù)擬合

以該自動化立體車庫實際運行數(shù)據(jù)為基礎(chǔ)數(shù)據(jù)，截取1天24 h時即1 440 min內(nèi)車輛到達時間，對車輛達到時間間隔進行統(tǒng)計分析，并進行到達概率擬合，如圖5所示。

其中橫坐標表示車輛到達時間間隔，縱坐標表示車輛到達時間段內(nèi)的密度，對顧客到達時間進行概率擬合，得出顧客到達率分別服從參數(shù)λ為0.5輛/分鐘的泊松分布。

2.2 改進集束搜索算法搜索最優(yōu)路徑

根據(jù)北京市某立體車庫實體模型，將該車庫的I/O口位置設(shè)為改進集束搜索的起始點，即根節(jié)點。采用改進集束搜索算法對堆垛機路徑進行搜索選擇時，首先將束按照臨近搜索節(jié)點和遠離搜索節(jié)點分為兩組，每組均按照搜索當(dāng)前距離L不大于2.5 m對路徑進行搜索，即懲罰機制為當(dāng)前搜索距離不大于2.5 m。

改進集束搜索步驟如下：

步驟1 在復(fù)合作業(yè)任務(wù)優(yōu)先次序圖中，生成可分配庫位的集合；

步驟2 判斷初始節(jié)點的數(shù)量N是否大于bw，若N＞bw，轉(zhuǎn)向步驟3；若 N＜bw，則對初始節(jié)點進行分支；

步驟3 將不完整的分配通過某種派發(fā)規(guī)則轉(zhuǎn)變成完整分配，并根據(jù)懲罰機制對分配進行分支；

步驟4 比較完整分配的目標值，并選擇最優(yōu)的bw個作為初始庫位；

步驟5 對束節(jié)點進行分支，并計算節(jié)點的目標值，選擇最優(yōu)庫位；

步驟6 從最終會產(chǎn)生的bw個完整的分配方案中選擇最優(yōu)的搜索的最佳庫位。

3 仿真實驗與分析

綜合分析北京市某立體車庫，得出該車庫車輛到達時間服從參數(shù)為λ=0.5輛/min的泊松分布，車庫服務(wù)率μ=0.9輛/min，在車庫布局為4層7列雙排對列布設(shè)，單巷道，單I/O口，堆垛機數(shù)量為1臺的配置下，不同庫位布局對整體運行效率產(chǎn)生影響?？紤]整個立體車庫的造價和安全性能等問題，設(shè)置車庫的最低層數(shù)為3層，最高層數(shù)不超過9層，則該立體車庫層數(shù)可設(shè)置為3、4、5、6、7或8層。考慮庫容量約為50個，那么層數(shù)為3時，列數(shù)即設(shè)置為8列，此布局下該立體車庫共有48個庫位，符合約50個庫位容量的要求。以此類推，得出不同層數(shù)所對應(yīng)的列數(shù)，則可得出表1的立體車庫層和列的不同組合。

表1 層和列不同情況的組合

針對上述7種層和列不同情況的組合進行模擬仿真，根據(jù)立體車庫運行情況，設(shè)定束寬bw為4，就近存儲規(guī)則，搜索最大層數(shù)為8層，懲罰機制為當(dāng)前搜索距離不大于2.5 m，以S3為例，改進集束搜索算法搜索堆垛機路徑示意圖如圖6所示。

采用Matlab進行仿真模擬對比，系統(tǒng)仿真流程如圖7所示。

得出在北京市某醫(yī)院自動化立體車庫的配置設(shè)備下，不同庫位布局下堆垛機作業(yè)路徑長度、顧客的平均等待時間和平均等待隊長，如表2所示。

從表2可以看出：改進集束搜索比集束搜索有較大的改進，堆垛機運行距離縮短約13%，顧客平均等待時間縮短約3.2%，平均等待隊長縮短約18.7%。而且無論在任何方式下，S3情況即4層6列的庫位布局顧客的平均等待時間、平均等待隊長最短，堆垛機運行效率最高；隨著層數(shù)變大，列數(shù)變小，顧客的平均等待時間、平均等待隊長逐漸增加。

表2 改進集束搜索與集束搜索對比

4 結(jié)論

本文中以北京市某立體車庫的實際運行數(shù)據(jù)為依據(jù)，提出了立體車庫庫位布局選擇問題的集束搜索算法，并對此進行改進。首先給出集束搜索的路徑選擇原理過程，針對傳統(tǒng)集束搜索方法存在常數(shù)線寬大小影響求解效果的問題，引入懲罰機制，對集束搜索進行了改進；然后將改進集束搜索應(yīng)用到立體車庫庫位選擇問題上，使用改進集束搜索算法對立體車庫庫位布局進行了優(yōu)化。算例顯示：本文中提出的改進集束搜索算法可以縮短堆垛機運行距離，提高立體車庫運行效率，從而對立體車庫的布局進行優(yōu)化。