王姍姍，張紀會

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

0 引言

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

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

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

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

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

1 穿梭車倉儲系統(tǒng)模型

1.1 問題描述

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

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

圖1 穿梭車倉儲系統(tǒng)示意圖

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

1.2 模型建立

根據(jù)穿梭車倉儲系統(tǒng)的實際運行情況，系統(tǒng)運行時滿足以下條件：

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

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

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

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

(1)

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

圖2 速度-時間關(guān)系圖

圖3 復(fù)合作業(yè)路徑示意圖

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

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

(2)

(3)

其中，

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

tcl表示提升機與穿梭車交互響應(yīng)時間。

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

(4)

(5)

(6)

(7)

(8)

(9)

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

(10)

s.t.

(11)

(12)

(13)

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

2 改進離散粒子群優(yōu)化算法

粒子群優(yōu)化算法的思想源于鳥類捕食時群體間的信息共享和協(xié)作。每個粒子包含位置和速度兩個屬性，粒子的位置代表問題的一個可行解，用粒子位置對應(yīng)的適應(yīng)度函數(shù)值評估粒子的優(yōu)劣，迭代過程中記錄粒子自身和群體的歷史最優(yōu)位置，通過速度調(diào)整粒子位置使之不斷向更優(yōu)的方向移動。標(biāo)準(zhǔn)粒子群優(yōu)化算法的速度和位置更新方程如式(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表示迭代次數(shù)，Xi和Vi分別表示粒子i的位置和速度，Xipbest為粒子i自身的歷史最優(yōu)位置，Xgbest為整個群體的歷史最優(yōu)位置。ω為慣性系數(shù),c1和c2為學(xué)習(xí)因子，r1和r2是[0,1]之間的均勻分布隨機數(shù)。速度的更新方程(14)由3個部分組成：ωVi稱為慣性部分，主要作用是產(chǎn)生擾動，防止算法早熟收斂；c1r1(Xipbest-Xi)是認知部分，反應(yīng)了粒子向自身歷史最優(yōu)位置逼近的趨勢；c2r2(Xgbest-Xi)是社會部分，反應(yīng)粒子向整個群體的歷史最優(yōu)位置逼近的趨勢。通過設(shè)置適當(dāng)?shù)摩?、c1、c2，可以權(quán)衡各部分所占的權(quán)重，使粒子具有均衡的局部搜索能力和全局搜索能力。

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

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

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

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

(16)

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

(17)

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

2.2 粒子位置和速度的定義

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

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

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

2.3 位置的更新

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

x2,vi=x1,i

(18)

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

2.4 速度的更新

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

2.4.1 位置的減法

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

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

(19)

圖4 位置與速度的加法

圖5 位置的減法

2.4.2 速度的加法

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

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

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

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

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

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

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

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

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

(20)

圖6 循環(huán)交叉

圖7 交換變異

圖8 排斥算子

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

2.5 適應(yīng)度函數(shù)

根據(jù)第1.2節(jié)建立的復(fù)合作業(yè)路徑優(yōu)化模型，將適應(yīng)度函數(shù)定義為完成一批出入庫任務(wù)的總時間最小：

fitness=minT

(21)

2.6 算法流程

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

圖9 改進離散粒子群優(yōu)化算法流程圖

3 仿真結(jié)果及分析

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

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

表1 倉庫設(shè)備參數(shù)

表2 出入庫任務(wù)列表

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

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

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

從表3可以看出，在不同任務(wù)規(guī)模下，IDPSO得到的最優(yōu)值、最差值、平均值、標(biāo)準(zhǔn)差均小于GA，證明IDPSO的求解精度和穩(wěn)定性都優(yōu)于GA。從算法平均運行一次的時間來看，GA的運行時間超過IDPSO的2倍，證明IDPSO的求解速度更快。

表3 IDPSO與GA算法優(yōu)化結(jié)果對比

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

圖11 不同任務(wù)規(guī)模下兩種算法的收斂曲線對比圖

4 結(jié)論

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

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