兩端式自動化立體倉庫布局堆垛機調度

蔡安江 薛曉飛 郭師虹 蔡 曜 郭宗祥 趙項利

1.西安建筑科技大學機電工程學院，西安，710055 2.西安建筑科技大學土木工程學院，西安，710055 3.河北省帶式輸送機工程技術研究中心，衡水，053020

0 引言

自動化立體倉庫作為生產物流以及CIMS加工模式的中樞環節，集存儲、轉存、運輸、分發功能為一體，代表了當今生產物流的發展趨勢[1]。在高密集儲存需求下，兩端式自動化立體倉庫得到了更為廣泛的應用。為更加有效地進行管理，提高整體作業效率，兩端式自動化立體倉庫要求對貨位和堆垛機的運行路線進行優化，以縮短存儲時間，提高效益[2-3]。

國內外學者對自動化立體倉庫的優化調度問題進行了大量的研究。HACHEMI等[4]采用整數線性規劃研究了自動化立體倉庫的進出庫調度問題；龐龍等[5]將蟻群算法與遺傳算法相結合來解決了揀選作業模型優化問題；REGATTIERI等[6]對堆垛機的停靠點策略進行了研究，構建了策略評估模型，以此來提高倉庫作業效率；朱文真等[7]通過禁忌搜索算法改進遺傳算法的變異算子，利用遺傳禁忌混合算法解決了復合命令序列下的堆垛機路徑優化問題。以上研究主要針對堆垛機的某一種作業方式，未綜合考慮堆垛機單一命令作業和復合命令作業。MA等[8]提出一種基于集成學習策略的多目標優化算法，解決了立體化倉庫調度問題；王進業等[9]針對旁通式立體倉庫的工作效率問題，建立了同時考慮堆垛機出口選擇和揀選路徑的組合優化模型，采用結合了自適應鄰域法的遺傳算法進行求解。以上研究雖然綜合考慮了堆垛機的兩種作業方式，但未考慮復合命令作業方式中的出/入庫任務交替進行所引起的起始點變化問題。楊文強等[10]建立了兼顧質量和路徑的多目標優化模型，并采用改進的多目標禁忌搜索算法以實現調度優化求解；柳賽男等[11]為提高立體倉庫出/入庫操作的效率，研究了基于庫區分配策略和貨位分配策略的優化問題，并采用基于Pareto最優解的遺傳算法對問題進行了求解。上述研究中，貨物的出/入庫臺均在調度優化之前已經確定，而對于兩端式自動化立體倉庫，合理的出/入庫臺的選擇也會縮短堆垛機的行走路程和作業時間，從而提高堆垛機工作效率。

基于此，本文針對兩端式自動化立體倉庫布局堆垛機調度路徑模型進行研究，綜合考慮堆垛機單一命令作業和復合命令作業兩種方式，將貨物的出/入庫臺分配納入調度模型，運用渦流搜索(vortex search ，VS)算法進行優化求解，來提高算法求解效率和自動化立體倉庫的存儲效率。

1 調度優化問題與假設

1.1 問題描述

兩端式倉庫布局作為一種常見的自動化立體倉庫模式，在實際生產生活中得到了廣泛的應用，其出/入庫臺分別位于貨架的兩端，外部輸送系統需連接出/入庫臺，故平行于貨架區設置。圖1為兩端式倉庫布局結構圖，在自動化倉庫每個巷道上設置1臺堆垛機，巷道兩端各設置1個庫臺，2個庫臺均可用于貨物的入庫和出庫。入庫貨物由外部起始點運輸至左右兩端的出/入庫臺所用的時間相同；出庫貨物從左端出/入庫臺或右端出/入庫臺出庫，再運輸至指定輸送點的時間也相同。

圖1 兩端式倉庫布局結構圖Fig.1 Layout structure of warehouse with double ended

堆垛機在存取貨作業中存在兩種作業方式：單一命令(SC)作業方式和復合命令(DC)作業方式[12]。堆垛機進入倉庫僅進行1次存貨或取貨的操作為SC作業方式，堆垛機進入倉庫進行1次存貨和1次取貨的操作為DC作業方式。該布局的自動化立體倉庫的系統如圖2所示，為單控制器雙隊列排隊形式，出/入庫任務指令被發送至堆垛機控制系統后，先經系統調度優化算法處理成合理的任務序列，然后再控制堆垛機進行操作。由此可見，因DC作業方式將出庫作業和入庫作業合為堆垛機一次復合作業，所以減少了堆垛機從出/入庫臺到貨位之間的往返次數，大大提高了作業效率。然而在一批出/入庫作業任務中，出庫任務與入庫任務的數量一般不相等，所以堆垛機不可避免要進行SC作業。

圖2 單控制器雙隊列排隊形式Fig.2 Single controller queue with two queues

對于一個出/入庫作業訂單，只需要確定每個出/入庫貨位的庫位坐標(即待入庫貨物的入庫貨位坐標和待出庫貨物的出庫貨位坐標)即可，而對每個貨物的出/入庫臺不作規定，將其作為堆垛機路徑調度優化的一部分。由分析可知，執行第一個出/入庫作業時，若該任務為入庫作業，則該入庫貨物的入庫庫臺為堆垛機執行完上一個出/入庫作業訂單后所停留的庫臺，若該任務為出庫作業，則堆垛機執行該出庫作業的起始位置為堆垛機執行完上一個出/入庫作業訂單后所停留的庫臺；堆垛機執行到最后一次任務時，若該任務為入庫作業，則堆垛機返回至最近的庫臺，若該任務為出庫作業，則該出庫貨物的出庫庫臺為離堆垛機最近的庫臺。

由上述分析可知，要提高自動化立體倉庫的作業效率，使其更好地適應生產物流的需求，就需要考慮堆垛機不同的出/入庫序列運行的調度問題，如何將1個出/入庫作業訂單中的作業任務進行排列，組成DC作業和SC作業，使堆垛機運行時間最短。因此，本文針對兩端式自動化立體倉庫布局模式，提出了適用于該情況的DC/SC作業方式，并在此基礎上建立堆垛機調度模型，進而進行優化研究。

1.2 基本假設

為方便研究問題，在兩端式自動化立體倉庫布局中，對固定貨架和堆垛機的運行參數作如下設定：

(1)固定貨架有I列、J層，共IJ個貨位，各貨位的長度為l，高度為h。設第i列、第j層貨位的坐標為(i，j)，左端出/入庫臺IOj的坐標為(0, 1)，右端出/入庫臺IOk的坐標為(I+1, 1)，左右兩端庫臺均可用于貨物的入庫作業和出庫作業。

(2)堆垛機貨叉運行速度恒定，對任一貨位的揀選時間固定，不隨該貨位在揀選路徑中的揀選順序不同而發生變化。設堆垛機水平方向運行速度為vx，垂直方向運行速度為vy， 2個方向的運動是獨立的，運行速度恒定，忽略堆垛機啟動時間和制動時間。

(3)堆垛機在作業過程中，1次最多只能裝載1件貨物，固定貨架的每個貨位尺寸相同且貨架中每個貨位也只能存放1件貨物。

通過以上基本假設可知堆垛機自貨架位置(xa,ya)運行至貨架位置(xb,yb)所需要的時間：

2 兩端式倉庫形式堆垛機調度模型

綜上分析可知，本文所建立的堆垛機調度模型應解決兩個問題：出/入庫任務排序；出/入庫貨物庫臺選擇。故在建模過程中，入庫貨物的入庫庫臺和出庫貨物的出庫庫臺在兩端各有2個出/入庫臺可供選擇，而實際情況是每個貨物對應的出/入庫臺是由堆垛機執行該任務所用時間最短來決定的。

兩端式堆垛機完成所有SC作業任務和DC作業任務需要的時間為

(1)

式中，T為完成該出/入庫作業訂單所需的總時間；TSCi為第i個SC作業任務所用的時間；TDCj為第j個DC作業任務所用的時間；m為SC作業任務的數量；n為DC作業任務的數量。

對于SC作業方式，假設堆垛機裝貨和卸貨所用的時間相等，則

TSCi=TIOjPi+TPiIOk+2τIO

(2)

j,k∈1,2

其中，TIOjPi表示執行第i個SC作業任務時，堆垛機由裝載貨物的出/入庫臺運動至Pi貨位的時間；TPiIOk表示執行第i個SC作業任務時，堆垛機由Pi貨位運動至裝載貨物的出/入庫臺的時間；τIO表示堆垛機進行一次裝/卸貨物操作所用的時間。

由此，當有m個SC作業任務時，堆垛機運動總時間為

(3)

對于DC作業方式，同樣假設堆垛機裝貨和卸貨所用的時間相等，則

TDCj=TIOjP2j-1+TP2j-1P2j+TP2jIOk+4τIO

(4)

其中，TIOjP2j-1表示執行第j個DC作業任務時，堆垛機由裝載貨物的出/入庫臺運動至P2j-1貨位的時間；TP2j-1P2j表示堆垛機從入庫貨位到出庫貨位的時間；TP2jIOk表示在當前任務序列中，第j個DC作業任務的出庫貨物到下一個入庫作業的出/入庫臺，堆垛機的運行時間。

由此，當有n個DC作業任務時，堆垛機運動總時間為

(5)

綜上所述，堆垛機完成一出/入庫作業訂單，所需要的總時間為

(6)

在一批出/入庫作業任務中，出庫作業任務與入庫作業任務的數量一般不相等，因此我們假設在一批出/入庫作業任務中，有n1個入庫作業和n2個出庫作業，取Q1=max(n1,n2)，Q2=min(n1,n2)。故此得出，該批出/入庫作業訂單由Q2個DC作業任務和Q1-Q2個SC作業任務組成?；诖耍讯鈾C完成該批出/入庫作業訂單的運行總時間為

(7)

則完成這批出/入庫作業訂單時，堆垛機最優路徑模型為

g(T)=minT

(8)

3 出/入庫調度路徑優化

在求解自動化立體倉庫堆垛機出/入庫調度問題時，通常采用的遺傳算法、粒子群算法等智能算法需要多次迭代才能找到近似最優解，且容易陷入局部最小，收斂效率低。針對這些不足，本文在建立的堆垛機調度模型的基礎上，采用渦流搜索算法[13]進行調度路徑優化。渦流搜索算法是在隨機搜索和模式搜索基礎上提出的一種啟發式優化算法，它采用了一種根據迭代次數自適應調整搜索半徑的策略，參數較少，迭代迅速，能夠在較短的時間內找到最優解[14]。該算法可以提供搜索行為的探索和開發之間良好的平衡，通過使用自適應步長調整方案的搜索行為模擬渦流現象，具有操作簡單和搜索能力強的突出優點[15]。渦流算法的搜索能力超過了單解的模擬退火算法、模式搜索算法和群解的人工蜂群算法，操作簡單且搜索能力強，不需要設置過多參數，只需考慮迭代次數/候選解集大小以及搜索空間上下界等參數[16]。

3.1 渦流搜索算法的思想

在初始階段，渦流搜索算法提供高效的探索行為，而當算法收斂到局部解附近時，則開始進一步的局部開發，使當前解向著最優解逐步逼近[15]。在迭代過程中，用最好的候選解S′∈Ct(s)替換當前解，并將其作為下一次迭代過程中半徑的內環中心，產生新的候選解集Ct+1s；若最優解S′∈Ct+1s優于全局最優解，則更新全局最優解記錄，并將最優解作為下一次迭代過程中縮減半徑后的內環中心，重復上述過程直至滿足結束條件，輸出全局最優解記錄，如圖3所示。

圖3 渦流搜索算法的搜索過程Fig.3 Search process of vortex search algorithm

3.2 編碼設計

任務編碼是進行算法優化求解的第一步，為了方便問題的處理，采用基于任務編號序列排序的整數編碼方法將堆垛機接到的入庫任務進行編號，組成一段編碼，將堆垛機接到的出庫任務在入庫任務編號的基礎上進行編號，組成另一段編碼，同時將每個出/入庫任務的入庫庫臺和出庫庫臺寫成兩段編碼，用1、2表示出/入庫任務的庫臺選擇。

3.3 渦流搜索算法的步驟

針對兩端式自動化立體倉庫堆垛機調度模型，采用渦流算法進行調度優化，具體步驟如下。

(1)確定渦流搜索空間的初始中心。在D維空間中，第j維的取值范圍為Ej=elj,euj，j=1,2,…,D，則渦流搜索空間的初始中心為

μ0=(μ01,μ02,…,μ0D)

μ0j=(elj+euj)/2

其中，el、eu均為D維向量，表示搜索空間的上邊界和下邊界，el=(el1,el2, …,elD)，eu=(eu1,eu2, …,euD)。

(3)設置初始迭代數t=0。

(4)確定渦流搜索空間的初始半徑。初始均方差σ0也可以看作在二維優化問題中渦流外圈的初始半徑r0，即r0≈σ0，σ0= maxelj+mineuj/2。算法搜索初始階段，弱化局部性是必要的，所以初始半徑r0可以選擇一個較大的值,因此，初始步驟通過設置大半徑的最外圈實現了搜索空間的全覆蓋。

(5)產生候選解。初始候選解集Cts=S1,S2,…,Sn，t為迭代的次數，初始為0。通過以μ0為中心的高斯分布隨機產生，n代表候選解集中解的個數。高斯分布的一般形式為

其中，x為D維隨機向量；μ為D維樣本均值(渦流中心)向量；Σ為協方差矩陣，Σ=σ2I；σ2為高斯分布的方差；I為D維單位矩陣。

(6)候選解的超邊界處理。候選解必須在搜索空間邊界內才能被選擇，超出邊界范圍的解可以通過下式進行調整變換進入到邊界內：

(9)

Δ=euj-elj

式中，Skj為第k組候選解集中第j維的備選解；r為一符合均勻分布的隨機數。

(7)對高斯分布產生的n個解進行目標函數值計算，選出該代中的目標值最優解O，以及O對應的待優化序列最優解S′。

(9)若t小于最大迭代數gmax，則令t←t+1，否則，執行步驟(13)。

rt≈σt=σ0γ(λ,α)/λ

(12)令μ=μt，r=rt，執行步驟(5)，進入下一次迭代。

由以上可得，堆垛機調度優化的渦流搜索算法流程見圖4。

圖4 堆垛機調度優化的渦流搜索算法流程Fig.4 Optimization process of vortex search algorithm for stacker crane scheduling

以所建立的堆垛機調度模型為基礎，以堆垛機完成一出/入庫作業訂單時間最短為目標，通過運用渦流搜索算法，最終獲得出/入庫任務的作業序列以及各任務所對應的出/入庫臺。

4 仿真驗證

以某企業實際使用的自動化立體倉庫為研究對象，驗證所建立的調度模型的適用性和渦流搜索算法的有效性。該倉庫采用固定貨架挑選模式，當1個出/入庫作業訂單指令被傳送至堆垛機控制臺時，如何調度堆垛機在最短時間內完成所有出/入庫任務是衡量其倉儲能力的唯一標準。該立體倉庫由1條巷道、成組的2排貨架、1臺堆垛機、貨物緩沖區、外部輸送系統和貨物分揀臺組成，每排貨架為12層、80列，共有12×80×2=1 920個貨位用于貨物存儲。出/入庫臺共有2個，分布在巷道兩端，均可用于貨物的出庫和入庫，兩端出/入庫臺的坐標分別為(1,0)和(1,81)。堆垛機在作業過程中1次最多只能裝載1件貨物，固定貨架的每個貨位尺寸相同，且貨架中每個貨位也只能存放1件貨物。該立體倉庫各項指標參數見表1，在實際生產中，某批出/入庫作業訂單的出/入庫任務序列和對應貨位坐標見表2。

表1 該立體倉庫各項指標參數

表2 出/入庫作業訂單的任務序列和對應貨位坐標

針對該出/入庫作業訂單，采用渦流搜索(VS)算法對其進行優化求解，同時以遺傳算法(GA)和混合粒子群優化(CPSO)算法為基準，驗證VS算法較GA算法和CPSO算法在解決兩端式自動化立體倉庫出/入庫調度問題方面的優越性。三種算法的各項仿真參數設置如下：VS算法迭代次數為200，候選解個數為1 000；GA算法迭代次數為200，初始化染色體數為1 000，交叉算子為0.95，變異算子為0.05；CPSO算法迭代次數為200，初始化粒子數為1 000。

運用所建立的堆垛機調度模型對該出/入庫作業訂單任務進行優化仿真，堆垛機調度執行時間的優化曲線如圖5所示。

圖5 堆垛機執行時間優化曲線Fig.5 Optimization curve of stacker execution time

由圖5可知，堆垛機執行該出/入庫訂單任務所需要的時間隨著迭代次數的增加，逐漸縮短，與GA算法和CPSO算法相比，VS算法在解的質量方面表現更優。VS算法在迭代至288代時達到最優，此時堆垛機的調度執行時間為853.5 s，而在實際工況下，堆垛機執行該任務訂單所需要的實際時間為1 324 s，優化后,堆垛機的調度執行效率提高了35.5%。

優化后，堆垛機調度運行的最短時間所對應的出/入庫任務序列以及與其對應的出/入庫臺序列即為最優序列，見表3。

表3 出/入庫任務序列以及與其對應的出/入庫臺序列

注：表中的1*、2*分別代表左端出/入庫臺和右端出/入庫臺。 在求得堆垛機的最優調度路徑后，可知堆垛機的運行序列：

2*→21→37→2*→9→26→1*→12→29→2*→10→30→1*→18→38→2*→1→27→2*→13→35→2*→22→31→1*→6→36→2*→3→33→2*→11→39→1*→24→32→2*→16→34→1*→5→40→1*→19→28→1*→14→1*→17→1*→2→1*→25→2*→4→1*→8→1*→23→1*→15→1*→20→2*→7→2*。

綜上所述，本文建立的堆垛機調度模型適用于兩端式布局的立體倉庫，通過VS算法優化求解得到了堆垛機路徑調度的最優解，并與GA算法和CPSO算法進行比較，驗證了VS優化算法的有效性和優越性。

5 結 論

(1)在分析兩端式倉庫布局結構形式和作業特點的情況下，提出了適用于兩端式倉庫布局下堆垛機的SC和DC作業方式。

(2)在兩端式倉庫布局下，以堆垛機執行出/入庫任務序列所需的總時間為評價標準，對堆垛機調度路徑進行建模。建立了適用于兩端式倉庫布局下的堆垛機調度路徑模型，將入庫任務和出庫任務組合起來考慮，形成DC任務和SC任務，減少了堆垛機的往返次數，并將出/入庫貨物的出/入庫臺選擇也納入調度路徑的優化模型之中，使得調度優化更加有效。

(3)針對GA算法、CPSO算法等智能算法需要迭代次數較大才能找到近似最優解，且容易陷入局部最小、收斂效率低等缺點，利用渦流搜索算法對所建立的堆垛機調度路徑模型進行優化求解，在算法迭代的過程中嵌入小生境技術，得到最優出/入庫任務序列以及貨物對應的出/入庫臺序列。通過實例仿真，并將仿真結果與GA算法和CPSO算法的仿真結果進行比較，驗證了所建立的堆垛機調度路徑模型的正確性，以及渦流搜索算法在優化堆垛機調度路徑方面的適用性和優越性。