穿梭車倉儲系統復合作業路徑優化

王姍姍，張紀會

(1.青島大學復雜性科學研究所，山東 青島 266071；2. 山東省工業控制技術重點實驗室，山東 青島 266071)

0 引言

隨著電子商務、藥品流通、服裝和快銷品等行業的迅速發展，物品流通呈現出高時效、多品種、小批量的特點，對倉儲核心設備的性能提出了更高的要求。穿梭車具有運行速度快、成本低、性能穩定等優點，而且可以與其它自動化立體倉庫設備柔性連接起來，在物流倉儲系統中得到廣泛應用[1]。

穿梭車倉儲系統(Shuttle-Based Storage and Retrieval System，SBS/RS)是一種新興的自動化倉儲系統。在該類系統中，位于巷道口的提升機完成垂直方向的移動，巷道內的穿梭車完成水平方向的移動。與傳統的堆垛機式自動化立體倉庫相比，在性價比、柔性化以及綜合成本等方面都更具明顯優勢[2]。功能各異的穿梭車倉儲系統不斷開發并成功應用。

國內外學者對不同形式的穿梭車倉儲系統進行了研究。針對單層作業的穿梭車倉儲系統，Carlo等[3]研究了系統中兩個貨物提升機的調度問題，并提出了一種新的控制策略。Lerher等[4]考慮穿梭車和提升機的加速度，建立了系統的行程時間模型，該模型可以計算單指令循環和雙指令循環的行程時間，從而評估系統的性能。Borovin?ek等[5]提出考慮系統吞吐率、總投資成本和能耗的多目標優化模型，利用改進型非支配排序遺傳算法求解。楊瑋等[6]針對提升機同時可運輸兩個貨物的系統，建立了復合作業路徑優化模型，設計了混合植物繁殖算法對模型進行求解。針對穿梭車換層的多層穿梭車倉儲系統，方彥軍等[7]研究了可跨巷道的四向穿梭車與穿梭車換層提升機搭配的系統，建立了復合作業路徑優化模型，設計了改進的人工狼群算法對模型進行求解。于巧玉等[8]研究了雙提升機的跨層穿梭車倉儲系統,建立了帶有出庫任務期限的出庫任務調度模型，設計了改進的蟻群—粒子群雙層智能優化算法對模型進行求解。Azadeh等[9]對近年來自動化立體倉庫的新系統進行了綜述，總結了前人對不同的穿梭車倉儲系統的研究成果，指出許多實際中應用的新系統，需要新的模型和方法來解決。

在模型的求解方面，楊磊等[10]對堆垛機式自動化倉庫建立了基于指派問題的復合作業路徑優化模型，并用匈牙利法進行求解，但匈牙利法只適合于求解小規模問題，并且在處理一些特殊數據時，算法容易失效。智能算法如粒子群算法[11-13]、遺傳算法[14]，、蟻群算法[15]、模擬退火算法[16]等也常被用來解決任務指派問題。其中，粒子群優化算法的原理簡單，需要調節的參數少，求解速度快，在尋優穩定性和全局收斂性等方面都具有一定優勢，應用范圍也由連續問題逐漸推廣到離散問題中。為了解決任務指派問題，高尚等[11]設計了一種交叉粒子群優化算法，采用了遺傳交叉的思想，對粒子群的位置更新，但該算法容易陷入局部最優，出現早熟收斂。談文芳等[12]采用處理連續問題粒子群優化算法的一般公式，在粒子解更新時通過位置的排序來得到新整數排列解，這種做法忽略了離散型組合優化解的特點，存在表示冗余大、搜索效率低的缺點。孫曉雅等[13]提出了一種基于離散粒子群優化算法的求解方法，在迭代中通過定位交叉和局部搜索來對粒子的位置進行更新，增加解的多樣性，避免陷入早熟收斂，但對不同的問題，需要通過復雜的參數調整，才能取得好的效果。

本文對中小型電商企業常用的穿梭車倉儲系統進行研究。該系統由一輛穿梭車和一臺穿梭車換層提升機協作完成巷道內貨物的搬運。雖然此類系統的效率不及多輛穿梭車系統，但企業建設倉庫的投入少，并且不存在由于穿梭車的碰撞和卡死帶來的負面影響，深受中小型電商企業倉庫的青睞。該系統的復合作業路徑優化類似于傳統堆垛機式的自動化立體倉庫，即如何在復合作業模式下有效地將多個貨位的出入庫任務進行組合，從而減少出入庫任務的總時間，此問題本質上是任務指派問題。針對模型的特點，重新定義了離散粒子群優化算法的位置和速度，將遺傳算法中的循環交叉和交換變異思想引入到離散粒子群優化算法速度的更新公式中,為保持種群多樣性和防止算法容易陷入局部最優，引入了排斥算子。最后通過仿真對比，驗證了模型和算法的有效性。

1 穿梭車倉儲系統模型

1.1 問題描述

本文研究的穿梭車倉儲系統由穿梭車、(穿梭車換層)提升機、高層貨架和傳送輥道等組成(見圖1)。貨物放在料箱中，以料箱為揀選單元進行作業，穿梭車具有夾抱式貨夾，用來夾取料箱，實現水平方向的移動，用提升機實現穿梭車垂直方向的移動。傳送輥道連接揀選臺，實現“貨到人”的揀貨模式。

該系統的作業模式有2種：單一作業和復合作業。單一作業是指系統一次只執行出庫任務或入庫任務。單一作業的大致流程為：提升機將穿梭車送到指定貨位層，給穿梭車發送信號，穿梭車響應后水平運行到指定貨位，完成存/取貨任務后，返回到提升機并發送信號，提升機響應后載著穿梭車回到第一層Input/Output站臺(I/O點)。在單一作業模式下，揀選時間是固定的，與任務的執行順序無關。

圖1 穿梭車倉儲系統示意圖

當系統既有入庫任務又有出庫任務時，為提高效率，系統先到達入庫任務貨位點，完成入庫任務后，不返回I/O點，而是直接到達出庫貨位點，完成取貨后，再返回I/O點。對于一批出入庫任務來說，按照不同的出入庫任務配對進行復合作業，消耗的總作業時間是不同的，因此，研究合理的復合作業路徑優化對于提升作業效率，降低作業成本具有重要意義。

1.2 模型建立

根據穿梭車倉儲系統的實際運行情況，系統運行時滿足以下條件：

1)穿梭車和提升機的初始位置均位于I/O點。穿梭車每次只能裝載一個料箱，提升機只可運送穿梭車，提升機將穿梭車送到目標層后，停在該層等待穿梭車。

2)料箱均為輕型料箱，不考慮重力作用，穿梭車與提升機滿載與空載情況下運行速度相同。

3)考慮穿梭車夾放貨物所消耗的時間，以及提升機與穿梭車交互響應的時間。

4)穿梭車與提升機在運行時均考慮設備的加(減)速度。運行時間按照速度是否達到設備額定最大運行速度分為兩種情況(見圖2)[4]。已知設備最大運行速度為vmax，加速度為a，運行的距離為s，則運行時間為：

(1)

根據入庫任務與出庫任務是否位于貨架的同一層，可將復合作業分為兩種情況(見圖3)，I/O點可以看作位于貨架的第1層第0排，將其坐標設為(0,1)，設入庫任務i的坐標為(xi,yi)，出庫任務j的坐標為(xj′,yj′)。當入庫任務i與出庫任務j位于貨架同一層時，穿梭車的行程路線為：(0,1)→(0,yi)→(xi,yi)→(xj′,yj′)→(0,yj′)→(0,1)。當入庫任務i與出庫任務j位于貨架不同層時，穿梭車的行程路線為：(0,1)→(0,yi)→(xi,yi)→(0,yi)→(0,yj′)→(xj′,yj′)→(0,yj′)→(0,1)。

圖2 速度-時間關系圖

圖3 復合作業路徑示意圖

對于給定的一批任務，設入庫任務有m個，出庫任務有n個。若m≠n，則用I/O點把數量較少的任務補齊，即將入庫任務與出庫任務均視為N=max{m,n}個。定義Q={q1,q2,…,qi,…,qN}為入庫任務集合，其中，i表示入庫任務編號，qi=(xi,yi)為入庫任務坐標。定義P={p1,p2,…,pj,…,pN}為出庫任務集合，其中，j表示出庫任務編號，pj=(xj′,yj′)為出庫任務坐標。

當入庫任務與出庫任務數量不相等時，與I/O點進行復合作業的任務，實際上執行的是單一作業。此時，穿梭車夾/放貨物的次數、穿梭車與提升機交互響應的次數，與真正的復合作業不同。為了統一公式，引入參數δ，當實際執行復合作業時，δ=0；當實際執行單一作業時，δ=2。當入庫任務i與出庫任務j配對進行復合作業時，完成該復合作業所需時間tij的計算公式如式(2)、(3)：

(2)

(3)

其中，

tcg表示穿梭車貨夾單次取/放貨時間；

tcl表示提升機與穿梭車交互響應時間。

設貨架有L層H排，貨格長度為l，貨格高度為h，提升機加速度為ay，提升機最大速度為vy，穿梭車加速度為ax，穿梭車最大速度為vx，由式(1)可計算穿梭車和提升機在各階段的運行時間為:

(4)

(5)

(6)

(7)

(8)

(9)

對于給定的一批出入庫任務，由于入庫任務需要依照一定的順序執行，所以固定入庫任務順序，通過改變出庫任務順序，實現出入庫任務的配對。將入庫任務與出庫任務的配對視為N個人分擔N項任務的指派問題，以完成一批出入庫任務的總時間最小為目標，建立復合作業路徑優化模型如式(10)～(13)所示。

(10)

s.t.

(11)

(12)

(13)

其中，tij表示入庫任務i與出庫任務j進行復合作業所用的時間，由式(2)求出。當入庫任務i與出庫任務j進行復合作業時，cij=1，否則為0。約束條件(12)和(13)表示1個入庫任務只能與1個出庫任務配對，1個出庫任務也只能與1個入庫任務配對。

2 改進離散粒子群優化算法

粒子群優化算法的思想源于鳥類捕食時群體間的信息共享和協作。每個粒子包含位置和速度兩個屬性，粒子的位置代表問題的一個可行解，用粒子位置對應的適應度函數值評估粒子的優劣，迭代過程中記錄粒子自身和群體的歷史最優位置，通過速度調整粒子位置使之不斷向更優的方向移動。標準粒子群優化算法的速度和位置更新方程如式(14)、(15)所示。

Vi(t+1)=ωVi(t)+c1r1(Xipbest(t)-Xi(t))+c2r2(Xgbest(t)-Xi(t))

(14)

Xi(t+1)=Xi(t)+Vi(t+1)

(15)

其中，t表示迭代次數，Xi和Vi分別表示粒子i的位置和速度，Xipbest為粒子i自身的歷史最優位置，Xgbest為整個群體的歷史最優位置。ω為慣性系數,c1和c2為學習因子，r1和r2是[0,1]之間的均勻分布隨機數。速度的更新方程(14)由3個部分組成：ωVi稱為慣性部分，主要作用是產生擾動，防止算法早熟收斂；c1r1(Xipbest-Xi)是認知部分，反應了粒子向自身歷史最優位置逼近的趨勢；c2r2(Xgbest-Xi)是社會部分，反應粒子向整個群體的歷史最優位置逼近的趨勢。通過設置適當的ω、c1、c2，可以權衡各部分所占的權重，使粒子具有均衡的局部搜索能力和全局搜索能力。

標準的粒子群優化算法是針對連續型問題給出的，并不能直接用來解決離散型問題。kennedy等[17]首先提出了二進制離散粒子群優化算法，隨后許多學者提出了不同的離散粒子群優化算法。Clerc[18]指出設計離散粒子群優化算法的關鍵在于根據實際問題的特點對算法中的位置和速度以及運算規則重新定義。本文模型是典型的離散型問題，需要針對其特點對離散粒子群優化算法進行重新設計。

2.1 改進離散粒子群的更新方程

標準的粒子群速度更新方程(14)中涉及的運算有：速度的加法，速度的數乘、位置的減法。對于本文的模型來說，由于離散變量的特殊性，速度加法中的慣性項及速度的數乘會擾亂速度的更新，不利于算法向有利方向迭代，所以取消了標準粒子群速度更新方程中的慣性部分[19]和速度的數乘運算，只考慮個體歷史最優位置、群體歷史最優位置分別與粒子當前位置相減后產生的兩個速度的加法運算。通過對速度的加法運算規則的設計，實現慣性部分和速度數乘運算的功能以及速度的更新。因為離散變量的運算并不是簡單的數值運算，所以使用符號“⊕”“?”來表示離散變量的加減運算。綜上所述，將速度和位置更新方程修改如式(16)、(17)所示。

Vi(t)=(Xipbest(t)?Xi(t))⊕(Xgbest(t)?Xi(t))

(16)

Xi(t+1)=Xi(t)⊕Vi(t)

(17)

算法首先隨機產生粒子群的初始位置，再依照更新方程(16)和(17)依次迭代更新每個粒子的速度和位置。下面對算法中粒子位置和速度的定義及更新方程(16)和(17)中所涉及的運算規則，進行詳細說明。

2.2 粒子位置和速度的定義

粒子位置X表示出入庫任務的配對方案，粒子速度V的作用是改變粒子位置，使算法逐步找到更優的出入庫任務配對方案。

粒子位置表示為X=(x1,x2,…,xi,…,xN)，其分量都是不超過N的自然數而且各分量不重復。分量xi表示與第i個入庫任務配對的出庫任務編號，即其含義是編號為xi的出庫任務與編號為i的入庫任務組成第i個執行的復合作業任務對。

粒子速度表示為V=(v1,v2,…,vi,…,vN)，其分量也都是不超過N的自然數而且各分量不重復。粒子速度的含義是將原來與編號為i的入庫任務配對的出庫任務，修改為與編號為vi的入庫任務配對。實際上，這樣定義速度的作用是對出庫任務編號進行了重新排列，實現粒子位置的移動。這樣定義可以保證X與任意V相加后，仍然是一個可行解。

2.3 位置的更新

更新方程(17)表示，通過粒子位置與速度的加法運算實現粒子位置的更新，使粒子到達一個新位置[19]。為便于描述，用X2=X1⊕V表示位置與速度的加法運算。如圖4所示，根據粒子速度的定義，將粒子原位置X1的第i個分量x1,i依次賦值給粒子新位置X2的第vi個分量x2,vi，即X2的每一個分量由公式(18)確定。

x2,vi=x1,i

(18)

由此可以看出，當V=(1,…,i,…,N)時，將其加到原位置上，新位置將不發生改變,即X2=X1⊕V=X1。

2.4 速度的更新

速度的更新方程(16)中包含了位置的減法運算和速度的加法運算。通過位置減法得到兩個速度，這兩個速度反映了粒子當前位置與個體最優和群體最優的差距。通過速度的加法運算，將這兩個速度結合，實現粒子速度的更新，新產生的速度綜合了粒子個體最優和群體最優的位置信息，將其加到粒子位置上，可以使粒子群逐步向全局最優解靠近。

2.4.1 位置的減法

位置的減法運算用V=X2?X1表示，根據粒子速度的定義，該運算的實現方式是：依次找到X2中與x1,i相等的分量x2,j的位置j，并將j賦值給vi，即速度V中的每一個分量vi由式(19)產生(見圖5)。

find(x2,j=x1,i)，return(j)，vi=j

(19)

圖4 位置與速度的加法

圖5 位置的減法

2.4.2 速度的加法

速度的加法運算用V=V1⊕V2表示。為了實現速度加法的功能，將遺傳算法的循環交叉引入到速度的加法中，把V1和V2看作兩個父代染色體。循環交叉的基本思想是子代的基因必須與父母相應位置上的基因相等，這樣可以較好地保留位值信息，適用于解決任務指派問題[20]。若兩個速度只進行循環交叉，新產生的速度作用到粒子位置上，將使種群迅速趨同，算法失效。為防止種群迅速趨同，將交叉后的速度進行交換變異，為種群增加擾動。當粒子的多樣性下降到一定程度時，定義一個排斥算子，減少算法陷入局部最優的可能，提高算法的求解精度。

綜上所述，V1⊕V2的運算步驟如下：

1)循環交叉。首先隨機選擇V1的某一個基因，為了便于描述，以選中了V1的第一個基因為例說明(見圖6)，具體操作如下：

(1)將V1的第一個基因，賦給C1的第一個基因，同時將V2的第一個基因賦給C2的第一個基因。

(2)在V1中找V2的第一個基因的基因位i，將V1該基因位的基因賦給C1的相應位，將V2該基因位的基因賦給C2的相應位，……重復此過程，直到在V2上找到V1的第一個基因為止，稱為一個循環。

(3)對于循環中未被選中的基因位，將V1相應位基因賦給C2，將V2相應位基因賦給C1，從而產生兩個子代：C1和C2。

(4)以等同的概率隨機選擇C1和C2中的一個，記為V′。

2)交換變異。對循環交叉后產生的V′，以一定的變異概率Pm進行交換變異。如圖7所示，若Pm大于隨機數rand，則隨機交換V′的兩個基因，求得V；否則，直接令V=V′。變異的作用是增加擾動，在探索初期，為提高全局搜索能力，Pm取一個較大的值；在探索后期，Pm取較小的值。設Pm的取值范圍為[pmin,pmax]，最大迭代次數為Itermax，則第gen代的變異概率由式(20)確定。

Pm=pmax-(pmax-pmin)gen/Itermax

(20)

圖6 循環交叉

圖7 交換變異

圖8 排斥算子

3)排斥算子。隨著算法的迭代，粒子群逐漸趨同，個體的進化能力受到很大限制，只有在其它粒子找到新的全局最優位置后，粒子才能恢復進化能力，所以，當算法迭代到一定的次數Iter時，定義一個排斥算子來增加粒子的多樣性[19]。如果粒子經過循環交叉后的速度V′=(1,…,i,…,N)，則表示該粒子為全局最優。為了增加擾動，此速度不再進行變異操作，而是隨機選中V′上的k個基因進行反轉(k∈{2,…,N})，隨著迭代次數的增加，k逐漸增大，實現從局部搜索到全局搜索的過程，使得算法跳出局部最優。以k=4為例，排斥算子對速度的影響，如圖8所示。

2.5 適應度函數

根據第1.2節建立的復合作業路徑優化模型，將適應度函數定義為完成一批出入庫任務的總時間最?。?/p>

fitness=minT

(21)

2.6 算法流程

綜上所述，改進離散粒子群優化算法(IDPSO)的基本流程如圖9所示。

圖9 改進離散粒子群優化算法流程圖

3 仿真結果及分析

為了證明模型和算法的有效性，以某電商倉庫為例，根據其具體數據及設備特性，使用MATLAB軟件進行仿真。倉庫中具體的設備運行參數如表1所示。

以系統的一組任務數據為例(見表2)。該數據有12個出庫任務，10個入庫任務，用I/O點將入庫任務補齊為12個。根據提出的模型，經過IDPSO算法優化后，得到最優解X=(6,12,1,2,10,8,7,5,11,9,4,3)，表示入庫任務與出庫任務以(1-6)→(2-12)→(3-1)→(4-2)→(5-10)→(6-8)→(7-7)→(8-5)→(9-11)→(10-9)→(11-3)→(12-4)的順序進行配對執行復合作業，其中，出庫任務3和4實際執行單一出庫作業。優化后的總作業時間為742.666 s，較執行單一作業(1 096.734 s)和未優化前的復合作業(838.705 s)，效率分別提高了32.3%和11.5%。

表1 倉庫設備參數

表2 出入庫任務列表

圖10 不同速度加法操作下的IDPSO收斂曲線對比圖

為了驗證算法中速度加法的有效性，保持其它操作不變，將速度加法里面的不同操作方式產生的效果進行對比，結果如圖10所示。若在速度的加法中，只進行循環交叉，不加入交換變異和排斥算子，則算法將迅速收斂早熟；在加入交換變異后，可以避免算法早熟，但仍然容易陷入局部最優解；通過排斥算子，可以進一步提高算法的求解精度。通過多次重復仿真，得到的比較結果相同，驗證了算法中速度加法設計的有效性和必要性。

為了驗證IDPSO算法在不同規模的數據下的性能，分別對復合作業數N(m=n=N)為30，50，100的任務訂單進行優化，并與遺傳算法(GA)進行比較。IDPSO種群大小設N，pmax=1.2，pmin=0.2，Iter=1/10*Itermax。GA種群大小設為3N，采用循環交叉，交換變異，精英保留策略，交叉概率為0.8，變異概率為0.2，代溝比例為0.9。兩個算法最大迭代次數Itermax均設為1000，每個算法獨立運行30次，計算出平均值、最小值、最大值和標準差，統計結果如表3所示。

從表3可以看出，在不同任務規模下，IDPSO得到的最優值、最差值、平均值、標準差均小于GA，證明IDPSO的求解精度和穩定性都優于GA。從算法平均運行一次的時間來看，GA的運行時間超過IDPSO的2倍，證明IDPSO的求解速度更快。

表3 IDPSO與GA算法優化結果對比

圖11是兩種算法在不同任務規模下的收斂曲線，可以看出IDPSO在迭代初期，可以快速收斂，而GA的收斂速度較慢。對于任務規模為30和50的曲線，IDPSO在250代左右就達到穩定，GA在400代左右才能達到穩定。對于任務規模為100的曲線，IDPSO在400代左右就達到穩定，GA在1 000代仍然未達到穩定。綜上，IDPSO的收斂速度和收斂穩定性都優于GA。

圖11 不同任務規模下兩種算法的收斂曲線對比圖

4 結論

研究了一種穿梭車倉儲系統的復合作業路徑優化問題。分析了該系統的作業模式和設備運行特征，以完成一批任務的總時間最小為目標，建立了基于任務指派問題的復合作業路徑優化模型。根據模型的特點，設計了一種離散粒子群優化算法對模型求解，通過仿真結果，與遺傳算法進行比較，驗證了本文提出的算法具有更好的效果。經過優化，大大縮短了復合作業的時間，提高了作業效率，為企業節省了時間成本。

本文研究的穿梭車倉儲系統一個巷道內只包含一輛穿梭車，無需考慮復雜的調度，穿梭車在巷道內運行時，提升機空閑會造成資源浪費,下一步將對更加復雜，效率更高的穿梭車倉儲系統進行研究。