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

常立丹，李建國，李博文

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

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

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

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

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

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

1 背景介紹

1.1 立體車庫實(shí)體模型

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

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

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

1.2 立體車庫排隊(duì)模型

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

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

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

在車庫排隊(duì)系統(tǒng)中，其運(yùn)行參考指標(biāo)主要包括：

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

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

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

則空閑概率P0為：

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

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

堆垛機(jī)將車輛A進(jìn)行存儲(chǔ)所需時(shí)間T1為：

堆垛機(jī)將車輛A進(jìn)行存儲(chǔ)后，隨即對(duì)車輛B進(jìn)行取車，所需時(shí)間T2為：

堆垛機(jī)將車輛B運(yùn)送到出入口所需時(shí)間T3為：

則堆垛機(jī)在庫內(nèi)運(yùn)行時(shí)間T為：

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

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

1.3 改進(jìn)集束搜索算法

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

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

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

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

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

2 立體車庫庫位布局分析

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

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

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

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

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

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

改進(jìn)集束搜索步驟如下：

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

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

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

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

步驟5 對(duì)束節(jié)點(diǎn)進(jìn)行分支，并計(jì)算節(jié)點(diǎn)的目標(biāo)值，選擇最優(yōu)庫位；

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

3 仿真實(shí)驗(yàn)與分析

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

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

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

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

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

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

表2 改進(jìn)集束搜索與集束搜索對(duì)比

4 結(jié)論

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