穿梭車倉(cāng)儲(chǔ)系統(tǒng)復(fù)合作業(yè)路徑優(yōu)化

王姍姍，張紀(jì)會(huì)

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

0 引言

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

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

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

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

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

1 穿梭車倉(cāng)儲(chǔ)系統(tǒng)模型

1.1 問(wèn)題描述

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

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

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

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

1.2 模型建立

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

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

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

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

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

(1)

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

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

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

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

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

(2)

(3)

其中，

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

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

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

(4)

(5)

(6)

(7)

(8)

(9)

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

(10)

s.t.

(11)

(12)

(13)

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

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

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

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

2.1 改進(jìn)離散粒子群的更新方程

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

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

(16)

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

(17)

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

2.2 粒子位置和速度的定義

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

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

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

2.3 位置的更新

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

x2,vi=x1,i

(18)

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

2.4 速度的更新

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

2.4.1 位置的減法

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

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

(19)

圖4 位置與速度的加法

圖5 位置的減法

2.4.2 速度的加法

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

綜上所述，V1⊕V2的運(yùn)算步驟如下：

1)循環(huán)交叉。首先隨機(jī)選擇V1的某一個(gè)基因，為了便于描述，以選中了V1的第一個(gè)基因?yàn)槔f(shuō)明(見圖6)，具體操作如下：

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

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

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

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

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

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

(20)

圖6 循環(huán)交叉

圖7 交換變異

圖8 排斥算子

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

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

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

fitness=minT

(21)

2.6 算法流程

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

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

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

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

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

表1 倉(cāng)庫(kù)設(shè)備參數(shù)

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

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

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

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

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

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

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

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

4 結(jié)論

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

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