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

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

0 引言

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

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

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

1 調(diào)度優(yōu)化問題與假設

1.1 問題描述

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

圖1 兩端式倉庫布局結(jié)構(gòu)圖Fig.1 Layout structure of warehouse with double ended

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

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

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

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

1.2 基本假設

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

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

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

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

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

2 兩端式倉庫形式堆垛機調(diào)度模型

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

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

(1)

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

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

TSCi=TIOjPi+TPiIOk+2τIO

(2)

j,k∈1,2

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

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

(3)

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

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

(4)

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

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

(5)

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

(6)

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

(7)

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

g(T)=minT

(8)

3 出/入庫調(diào)度路徑優(yōu)化

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

3.1 渦流搜索算法的思想

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

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

3.2 編碼設計

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

3.3 渦流搜索算法的步驟

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

(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)設置初始迭代數(shù)t=0。

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

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

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

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

(9)

Δ=euj-elj

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

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

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

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

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

由以上可得，堆垛機調(diào)度優(yōu)化的渦流搜索算法流程見圖4。

圖4 堆垛機調(diào)度優(yōu)化的渦流搜索算法流程Fig.4 Optimization process of vortex search algorithm for stacker crane scheduling

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

4 仿真驗證

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

表1 該立體倉庫各項指標參數(shù)

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

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

運用所建立的堆垛機調(diào)度模型對該出/入庫作業(yè)訂單任務進行優(yōu)化仿真，堆垛機調(diào)度執(zhí)行時間的優(yōu)化曲線如圖5所示。

圖5 堆垛機執(zhí)行時間優(yōu)化曲線Fig.5 Optimization curve of stacker execution time

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

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

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

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

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*。

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

5 結(jié) 論

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

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

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