陳廣鋒， 余立潮

(東華大學(xué) 機(jī)械學(xué)院， 上海 201620)

倉(cāng)儲(chǔ)貨物多訂單的執(zhí)行操作顯著影響著供應(yīng)鏈性能，亞馬遜和沃爾瑪?shù)裙静粩嗵岣邆}(cāng)庫(kù)揀貨的柔性作業(yè)效率[1-2].提高倉(cāng)庫(kù)揀貨的柔性作業(yè)效率的關(guān)鍵步驟包括訂單合理分配、批處理、排序及揀選最優(yōu)小車路徑.倉(cāng)庫(kù)訂單揀選是一項(xiàng)勞動(dòng)密集型活動(dòng)，占用高達(dá)大約61%的倉(cāng)庫(kù)成本，而其中大約59%的揀貨時(shí)間用于行程優(yōu)化[3].因此，智能優(yōu)化的方法需要從多個(gè)方面優(yōu)化訂單履行，從而最小化訂單周期時(shí)間.

已有文獻(xiàn)研究各種情況下的訂單揀選問題[4].?elk等[5]運(yùn)用精確方法，以總距離和時(shí)間最短為目標(biāo)函數(shù)，結(jié)合魚形過道的倉(cāng)庫(kù)布局解決訂單揀選問題.Matusiak等[6]以總距離與時(shí)間的比值最小為目標(biāo)函數(shù)提出的模擬退火(SA)算法用于批處理.Chen等[7]為訂單批處理提出了非線性混合的整數(shù)規(guī)劃模型(MIP).在模型的基礎(chǔ)上，以最小化訂單的總延遲時(shí)間為目標(biāo)函數(shù)，提出了混合遺傳(GA)和蟻群優(yōu)化(ACO)算法.后來Chen等[8]使用混合粒子群優(yōu)化(PSO)和ACO方法解決訂單批處理問題.Henn[9]借助最大限度地減少總延遲時(shí)間模型研究可變鄰域下降(VND)和變鄰域搜索(VNS)算法在批量處理的應(yīng)用.?ncan[10]也引入MIP并在每個(gè)迭代中運(yùn)用禁忌搜索作為局部搜索算法.Pan等[11]引入訂單的分批和工作均衡問題，運(yùn)用分組GA研究訂單的分批效果.Chen等[12]制定出一個(gè)創(chuàng)新的訂單批處理方法解決倉(cāng)庫(kù)中的擁堵問題，他們使用ACO獲取每個(gè)小車的初始路線，然后使用一組方法規(guī)則試圖修改路線以緩解擁堵.Cortés等[13]將庫(kù)存約束考慮在內(nèi)，采用禁忌搜索(TS)算法來解決揀選小車路徑尋優(yōu)問題，他們將TS分別與GA和SA的結(jié)果進(jìn)行了對(duì)比，發(fā)現(xiàn)TS比其他方法具有更好的效果.Henn等[14]采用幾種元啟發(fā)式算法建立總延遲最小化數(shù)學(xué)模型解決批量處理問題，與標(biāo)準(zhǔn)的啟發(fā)式算法相比，他們的方法可以改進(jìn)解決方案.Menéndez等[15]提出了基于VNS改進(jìn)算法解決訂單批處理問題，并通過廣泛的測(cè)試顯示了該方法的性能.?ulj等[16]提出基于自適應(yīng)鄰域搜索算法和禁忌搜索算法，建立最小化總的行程和時(shí)間數(shù)學(xué)模型解決訂單分配問題.陸漢東等[17]提出基于禁忌搜索算法分批調(diào)度柔性作業(yè)車間的模型.

上述研究從倉(cāng)庫(kù)的布局、使用的方法、考慮的特殊約束以及所使用的優(yōu)化目標(biāo)等方面考慮訂單揀選相關(guān)問題，大多數(shù)研究都集中在建立行程的總距離或者時(shí)間最小化數(shù)學(xué)模型解決訂單揀選問題，只有少數(shù)學(xué)者將完工時(shí)間作為優(yōu)化目標(biāo)融進(jìn)訂單分批問題.Scholz等[18]的研究將訂單分配、訂單批處理及揀選小車路徑尋優(yōu)同時(shí)考慮在內(nèi)，使完工時(shí)間盡量減少，達(dá)到總拖期較少的目標(biāo).然而，每批訂單揀選的批次序列不會(huì)改變總體完工時(shí)間，不同的批次序列可能導(dǎo)致不同的拖期級(jí)別，并不能保證揀貨小車之間的工作量均衡.

訂單分配、訂單批次、揀選小車路線及可用揀選小車數(shù)量會(huì)影響總揀貨完工時(shí)間.雖然最小化行駛的總距離可以降低揀選成本，但并不能保證揀貨小車之間的工作量均衡.

針對(duì)上述問題，考慮最小化完工時(shí)間有利于揀選小車之間的負(fù)載均衡，因此，考慮揀選倉(cāng)庫(kù)中的最小完工時(shí)間是必不可少的.近年來，眾多研究人員對(duì)使用差分進(jìn)化(DE)解決優(yōu)化問題越來越感興趣.由Storn等[19]提出的DE算法是一種有效的局部搜索算法，各國(guó)學(xué)者將其用于各種優(yōu)化問題.本文提出基于拉格朗日插值混合差分進(jìn)化算法，建立每批訂單最小化最大完工時(shí)間的數(shù)學(xué)模型，用拉格朗日插值提高DE算法的局部搜索能力，通過自適應(yīng)控制DE算法的進(jìn)化參數(shù)，使算法避免早熟收斂.此外，設(shè)計(jì)出DE算法局部和全局搜索自動(dòng)切換因子，可以顯著改善算法在收斂性和準(zhǔn)確性方面的表現(xiàn).

1 問題模型

倉(cāng)儲(chǔ)環(huán)境下的多訂單分配優(yōu)化內(nèi)容可以描述如下：訂單o∈{1,2,…,O}，將每個(gè)訂單o含有客戶要求數(shù)目不確定的貨物n∈{1,2,…,N}與具有i排，j列，k層的倉(cāng)儲(chǔ)貨物揀選庫(kù)(圖1)在r∈{1,2,…,R}的揀選小車的運(yùn)輸下進(jìn)行交互.圖1所示倉(cāng)儲(chǔ)貨物揀選庫(kù)研究的倉(cāng)庫(kù)呈矩形，所有通道都是平行的，黑格子表示所需揀選的貨物貨位，白格子表示未需揀選貨物貨位.每一件貨物可以選擇任意一批入庫(kù)或者出庫(kù)訂單，每一批入庫(kù)或者出庫(kù)的不同訂單都可以隨機(jī)組合， 每一批入庫(kù)或者出庫(kù)訂單可以選擇任何一輛揀選小車， 每一輛揀選小車可以選擇任意一條到達(dá)目的位置的路徑.

圖1 倉(cāng)儲(chǔ)貨物揀選庫(kù)Fig.1 Warehouse goods picking library

揀貨操作從揀選小車挑選分配給它們的訂單開始，每批包含1個(gè)或多個(gè)訂單.圖2所示為多個(gè)訂單和多輛揀選小車的分配優(yōu)化問題，其中每個(gè)格子代表完成某個(gè)訂單若干個(gè)物料對(duì)應(yīng)分區(qū)揀選小車所消耗的最大完工時(shí)間，圖中，q為不同的物料分區(qū)；t為某一分區(qū)完成揀選的最大完工時(shí)間.假設(shè)每個(gè)訂單對(duì)應(yīng)的物料分區(qū)最優(yōu)倉(cāng)儲(chǔ)貨位已經(jīng)求得，訂單一起做批處理，每批都分配給第r輛揀選小車，tmax是所有批次中最大的完工時(shí)間.假設(shè)揀選小車的行進(jìn)速度恒定，不受過道擁擠的影響.當(dāng)前研究的問題可以表述如下：通過一定數(shù)量的揀選小車完成一組非空的客戶訂單的目標(biāo)貨位分配，批次p被分配到m個(gè)訂單，最小化p中m個(gè)訂單每個(gè)分區(qū)的最大完工時(shí)間，從而最小化所有批次各分區(qū)的最大完工時(shí)間，其中每個(gè)客戶訂單包含一組具有倉(cāng)儲(chǔ)中待確定位置的物料若干.

圖2 多訂單分批分配優(yōu)化Fig.2 Allocation optimization of multi-order batch

為了最小化最大完工時(shí)間，建立對(duì)應(yīng)數(shù)學(xué)模型如下:

mintmax

(1)

(2)

(3)

(4)

?b∈{1,2,…,B},r∈{1,2,…,R}

(5)

?b∈{1,2,…,B},r∈{1,2,…,R}

(6)

?b∈{1,2,…,B},r∈{1,2,…,R},

z∈{1,2,…,Z}

(7)

?b∈{1,2,…,B}, ?r∈{1,2,…,R}

(8)

?b∈{1,2,…,B},r∈{1,2,…,R}

(9)

?b∈{1,2,…,B},r∈{1,2,…,R}

(10)

?b∈{1,2,…,B},r∈{1,2,…,R}

ω1+ω2=1

(11)

(12)

(13)

式中：

如式(1)所示，模型是以最小化最大完工時(shí)間為目標(biāo)函數(shù)，目標(biāo)函數(shù)的解決是以式(10)的懲罰條件為前提；約束(2)和(3)保證在可行的解集中所有訂單和所有物料都能被揀選小車選中；約束(4)表示批次b中揀選小車r所能承載的最大訂單o的數(shù)量；約束(5)為倉(cāng)儲(chǔ)貨物揀選庫(kù)貨位容量約束并確保批次b中揀選小車r承載合理的物料重量；約束(6)～(8)為貨架穩(wěn)定性和貨位的存貨能力；約束(9)為揀貨小車r在滿足物料周轉(zhuǎn)率條件下將物料運(yùn)送到目標(biāo)貨位的等價(jià)運(yùn)行時(shí)間；式(10)表示保證在滿足約束(6)～(9)條件下物料的最優(yōu)貨位分配最優(yōu)模型；約束(11)為權(quán)重因子；約束(12)和(13)為每輛揀選小車的完工時(shí)間以及其最大完工時(shí)間.

2 融合拉格朗日插值算法的改進(jìn)差分進(jìn)化(LGDE)算法

差分進(jìn)化算法主要包括4個(gè)步驟：種群初始化、變異、交叉及選擇.

2.1 標(biāo)準(zhǔn)差分進(jìn)化

(14)

式中：xu,v(0)為種群中第0代的第u條“染色體”以及第v個(gè)基因；rand(0,1)為均勻生成0～1的隨機(jī)數(shù).

差分進(jìn)化算法通過隨機(jī)選取種群中的兩個(gè)個(gè)體進(jìn)行向量縮放與變異個(gè)體進(jìn)行合成：

(15)

式中：vi(g+1)為變異個(gè)體；F為縮放因子；xi(g)為第g代的第i個(gè)個(gè)體；r1、r2及r3分別為第r個(gè)個(gè)體的隨機(jī)3個(gè)基因位.

對(duì)xi(g)及其變異個(gè)體vi(g+1)進(jìn)行交叉操作產(chǎn)生新的個(gè)體ui,j(g+1)：

ui,j(g+1)=

(16)

式中：CR為交叉概率；jrand∈(1,2,…,D)為隨機(jī)整數(shù).

采用貪婪算法選擇進(jìn)入下一代種群個(gè)體：

xi(g+1)=

(17)

式中：f為目標(biāo)評(píng)價(jià)函數(shù).為了能提高算法的收斂速度，保持較高的種群多樣性，選擇從種群中隨機(jī)選擇4個(gè)不同個(gè)體修正式(15)：

(18)

式中：xgbest(g)為最優(yōu)個(gè)體染色體；r4為第r個(gè)個(gè)體的第4個(gè)隨機(jī)基因位.

2.2 時(shí)變交叉概率

由式(16)可知，如果CR越大，則選中個(gè)體vi,j(g+1)的幾率較大，有利于局部搜索和加速收斂速率；反之，選中xi(g)的幾率大，有利于保持種群的多樣性和全局搜索.良好的搜索策略應(yīng)該是在搜索的初始階段保持種群多樣性，進(jìn)行全局搜索，而在搜索的后期應(yīng)加強(qiáng)局部搜索能力，以提高算法的精度.因此，采用下式將CR應(yīng)用于自適應(yīng)差分進(jìn)化 (ADE) 算法和本文算法.

(19)

CR=1/[1+e-(t-t0)]

(20)

式中：l為概率系數(shù)；tm為最大進(jìn)化代數(shù)；T為當(dāng)前進(jìn)化代數(shù)；CR0為交叉概率算子；t′為當(dāng)前消耗時(shí)間；t0為消耗時(shí)間參數(shù).

2.3 拉格朗日插值

拉格朗日插值是一種在已知多個(gè)坐標(biāo)點(diǎn)的情況下得到通過坐標(biāo)點(diǎn)的近似函數(shù)的建模方法[20].采用拉格朗日插值構(gòu)造近似函數(shù)加強(qiáng)差分進(jìn)化算法的局部搜索能力.已知坐標(biāo)點(diǎn)(xi,0(g),f(xi,0(g))),(xi,1(g),f(xi,1(g))),…,(xi,D(g),f(xi,D(g)))，其中xi,j(g)為第g代種群個(gè)體，f(xi,j(g))為第g代種群個(gè)體的適應(yīng)度.因此得到l次拉格朗日插值多項(xiàng)式：

Ll(xi,j(g))=

(21)

式中：m′為索引參數(shù).本文取l∈{0,1,2}，代入式(21)得到拋物插值，將其簡(jiǎn)化成二次函數(shù)模型：

(22)

式中：h′、p′及q′為方程式的系數(shù)，計(jì)算過程分別為

h′=

p′=

q′=q0+q1

l0=xi,0(g)-xi,1(g)
l1=xi,1(g)-xi,2(g)
l2=xi,2(g)-xi,0(g)

為了利用拉格朗日插值優(yōu)化差分進(jìn)化算法搜索局部最優(yōu)值，取出最優(yōu)個(gè)體染色體的一個(gè)基因位和變異最優(yōu)個(gè)體染色體的一個(gè)基因位作為插值點(diǎn)，得到兩個(gè)插值點(diǎn)：xi,0(g)和xi,1(g)，則xi,2(g)可由下式得到：

xi,2(g)=

(23)

(24)

算法1拉格朗日插值算法流程

步驟1輸入當(dāng)前迭代階段的xgbest(g)和該最優(yōu)染色體對(duì)應(yīng)的最優(yōu)目標(biāo)函數(shù)值f(xgbest(g))，遍歷最優(yōu)染色體每一位基因位h，通過隨機(jī)數(shù)隨機(jī)生成r1∈D,r2∈D，替代xgbest(g)的第h位基因，得到新的染色體xr1(g),xr2(g)；

步驟2計(jì)算新的染色體xr1(g),xr2(g)對(duì)應(yīng)的函數(shù)值f(xr1(g)),f(xr2(g))；

步驟3將步驟1和2計(jì)算得到的染色體xgbest(g)、xr1(g)及xr2(g)和對(duì)應(yīng)的函數(shù)值f(xgbest(g))、f(xr1(g))及f(xr2(g))代入式(22)及p′,q′,h′的計(jì)算式進(jìn)行計(jì)算，根據(jù)式(23)、(24)將得到染色體新的基因位xi,2(g)，對(duì)染色體新的基因位xi,2(g)進(jìn)行界限判斷，根據(jù)實(shí)際染色體的編碼設(shè)計(jì)求得相應(yīng)的最優(yōu)染色體；

步驟4判斷染色體基因位遍歷是否結(jié)束，如果沒有結(jié)束，轉(zhuǎn)步驟1，否則，結(jié)束算法.

2.4 自適應(yīng)調(diào)整差分進(jìn)化算法搜索方向

為了保持種群的多樣性與算法局部搜索能力的平衡，采用全局收斂算子λg和局部收斂算子λL評(píng)估算法的進(jìn)化方向：

(25)

(26)

提出的自適應(yīng)調(diào)整差分進(jìn)化算法搜索方向是通過一個(gè)動(dòng)態(tài)調(diào)整的閾值因子(DF)控制：

DF=

(27)

DF=

(28)

λg>λL

式中：DFmax，DFmin∈(0,1).為避免所提算法在進(jìn)化過程全局無法收斂，采用式(27)控制算法進(jìn)入局部搜索區(qū)域，式(28)則避免算法進(jìn)入早熟階段.當(dāng)λg較大時(shí)，算法進(jìn)入全局搜索，反之進(jìn)入局部搜索.

2.5 算法流程

2.5.1LGDE算法 LGDE算法流程如圖3所示，具體步驟如下.

圖3 LGDE算法流程圖Fig.3 Flow chart of LGDE algorithm

步驟1設(shè)置算法的種群大小NP，最大進(jìn)化代數(shù)為maxG以及其他進(jìn)化參數(shù).初始化DF和收縮算子.初始化種群，將要優(yōu)化的貨位或者時(shí)間存入數(shù)組，并初步統(tǒng)計(jì)種群的最優(yōu)個(gè)體xgbest(g)以及最優(yōu)解f(xgbest(g))；

步驟2進(jìn)入算法主循環(huán)，判斷結(jié)果是否達(dá)到 maxG，如果是則退出主循環(huán)，否則進(jìn)入步驟3；

步驟3生成一個(gè)0～1之間的隨機(jī)數(shù)rand(0,1)與DF初值比較，如果rand(0,1)

步驟4根據(jù)算法1計(jì)算出的f(xi,2(g))和統(tǒng)計(jì)出目標(biāo)函數(shù)f(xi,0(g))、f(xi,1(g))及f(xi,2(g))的最優(yōu)解及其最優(yōu)個(gè)體，按照式(26)、(27)更新DF和λL，并將迭代代數(shù)加2；

步驟5根據(jù)式(16)、(18)及(19)進(jìn)行變異和時(shí)變交叉操作，按照式(17)進(jìn)行選擇操作；

步驟6統(tǒng)計(jì)當(dāng)前代數(shù)種群的最優(yōu)值與最優(yōu)個(gè)體，并與步驟4所得結(jié)果進(jìn)行比較，更新全局最優(yōu)解和最優(yōu)個(gè)體.按照式(25)、(28)更新DF和λg，迭代代數(shù)加1，轉(zhuǎn)至步驟2；

步驟7得到最優(yōu)值和最優(yōu)個(gè)體.

2.5.2多訂單分批分配優(yōu)化 多訂單分批分配優(yōu)化過程如圖4所示，具體步驟如下.

圖4 多訂單分批分配優(yōu)化Fig.4 Allocation optimization of multi-order batch

步驟1貨位分配階段采用圖5所示單批次個(gè)體編碼，每一個(gè)基因位是倉(cāng)儲(chǔ)區(qū)域可行的倉(cāng)儲(chǔ)貨位編號(hào)，初始編碼將采用0～1的隨機(jī)數(shù)編碼，表示貨位的選中與否.訂單分配階段采用如圖6所示的多批次個(gè)體編碼，根據(jù)編碼規(guī)則選擇相應(yīng)的訂單編號(hào)為同一批次.運(yùn)用LGDE算法計(jì)算出每個(gè)分區(qū)相應(yīng)訂單貨物對(duì)應(yīng)的貨位時(shí)間向量表，進(jìn)入步驟2；

圖5 單批次個(gè)體編碼Fig.5 Single batch individual code

圖6 多批次個(gè)體編碼Fig.6 Multi-batch individual code

步驟2將基于訂單編號(hào)的染色體輸入到LGDE算法模型中，算法模型將進(jìn)行每批次每個(gè)分區(qū)的最大完工時(shí)間最優(yōu)分配，求解出每個(gè)訂單的批次分配情況；

步驟3判斷是否滿足終止條件，如果滿足則完成訂單分批分配，結(jié)束分配，否則轉(zhuǎn)到步驟2.

3 算法實(shí)例驗(yàn)證

為了驗(yàn)證所提算法的有效性，本文將采用具有圖1所示的貨物揀選庫(kù)結(jié)構(gòu)進(jìn)行實(shí)驗(yàn).將貨架從底層依次向上編號(hào)，所提算法的種群個(gè)體編碼將采用0～1的隨機(jī)數(shù)編碼，同時(shí)為每種貨物劃定可行的存儲(chǔ)貨位.用傳統(tǒng)的啟發(fā)式算法如遺傳算法、粒子群優(yōu)化算法進(jìn)行對(duì)比實(shí)驗(yàn)，同時(shí)與標(biāo)準(zhǔn)的差分進(jìn)化算法以及改進(jìn)的自適應(yīng)差分進(jìn)化算法進(jìn)行對(duì)比分析.實(shí)驗(yàn)計(jì)算機(jī)基本配置參數(shù)為：Intel(R)Pentinum(R)/CPUG2020@2.90 GHz/6 GB，操作系統(tǒng)為Windows 7，實(shí)驗(yàn)算法采用Python 2.7版本編程語(yǔ)言進(jìn)行編寫，所提算法參數(shù)設(shè)置如表1所示，表中CRinit為交叉概率的初始值.

表1 改進(jìn)差分進(jìn)化算法參數(shù)設(shè)置Tab.1 Parameter settings of improved differential evolution algorithm

在差分進(jìn)化算法參數(shù)中，交叉概率和縮放因子兩個(gè)參數(shù)對(duì)算法的性能影響較大，經(jīng)過多次仿真實(shí)驗(yàn)，分析不同的參數(shù)組合對(duì)算法性能的影響，改進(jìn)的算法采用式(19)和(20)的變交叉概率因子有利于提高算法的性能.經(jīng)過大量實(shí)驗(yàn)，將縮放因子取值在0.5左右取得較好實(shí)驗(yàn)效果，局部和全局調(diào)整因子在0.04～0.3時(shí)，算法具有較好的收斂性能.對(duì)于對(duì)比實(shí)驗(yàn)的算法中，本文將采用多次實(shí)驗(yàn)確定算法的參數(shù).遺傳算法中的變異因子和交叉因子會(huì)對(duì)算法產(chǎn)生重要影響，在粒子群算法的慣性權(quán)重表明粒子對(duì)當(dāng)前的粒子速度的繼承情況，其對(duì)算法的性能和效率會(huì)產(chǎn)生影響，自適應(yīng)差分進(jìn)化算法中的交叉概率因子將采用式(19)進(jìn)行時(shí)變操作.參考文獻(xiàn)[11]設(shè)定的遺傳算法參數(shù)，經(jīng)過多次實(shí)驗(yàn)將遺傳算法的交叉因子設(shè)為pc=0.6，變異因子設(shè)為pm=0.02，參考文獻(xiàn)[8]粒子群優(yōu)化算法的求解過程并將慣性權(quán)重設(shè)置為ω=0.5，學(xué)習(xí)因子設(shè)置為c1=c2=2.

3.1 貨位分配實(shí)驗(yàn)分析

最小化每批訂單的揀選小車的最大完工時(shí)間可以分解為最優(yōu)各個(gè)分區(qū)的貨位分配時(shí)間和最小化每批訂單各分區(qū)的揀選小車的最大完工時(shí)間兩個(gè)子問題，解決因多訂單路徑不同導(dǎo)致的訂單完成順序不同的問題.

為驗(yàn)證最優(yōu)各個(gè)分區(qū)的貨位分配時(shí)間子問題的解決效果，采用一定數(shù)量的貨物樣例進(jìn)行實(shí)驗(yàn)，貨物種類編號(hào)和數(shù)量如表2所示，實(shí)驗(yàn)結(jié)果如圖7所示.圖中J為目標(biāo)函數(shù)值，算法測(cè)試的種群個(gè)體為1行，63列的數(shù)組矩陣.

圖7 各個(gè)算法目標(biāo)函數(shù)值和各代平均值迭代情況Fig.7 Objective function value of each algorithm and the iterative case of each generation

表2 某一訂單批次貨物種類編號(hào)和數(shù)量Tab.2 Number and quantity of the goods of an order batch

表3是在揀貨小車運(yùn)行時(shí)間較短、 貨架穩(wěn)定性較優(yōu)及貨位滿足最大存貨的能力等約束條件下各種算法目標(biāo)函數(shù)值的計(jì)算結(jié)果.表中，Nt為迭代代數(shù)；tCPU為CPU消耗時(shí)間.

表3 各個(gè)算法優(yōu)化結(jié)果對(duì)比

從圖7和表3的結(jié)果可知，迭代過程每一代種群個(gè)體的平均值都有比較大的數(shù)值震蕩，在5種算法中，遺傳算法耗時(shí)最長(zhǎng)，且其最優(yōu)值和迭代代數(shù)較小，CPU消耗時(shí)間較長(zhǎng).標(biāo)準(zhǔn)的粒子群優(yōu)化算法出現(xiàn)局部陷入最優(yōu)的情況，解決問題的全局搜索的能力明顯不如其他4種算法，最優(yōu)值僅比遺傳算法好，但CPU消耗時(shí)間卻比ADE算法和DE算法短，逼近所提算法的時(shí)間耗時(shí)間.差分進(jìn)化算法的在局部搜索方面具有較強(qiáng)的表現(xiàn)能力，在最優(yōu)值上均能達(dá)到較優(yōu)的結(jié)果.在自適應(yīng)差分進(jìn)化算法中，擴(kuò)大了種群的搜索能力，最優(yōu)值上不如DE算法.對(duì)比以上5種算法，所提算法在各種表現(xiàn)上均出現(xiàn)較優(yōu)結(jié)果，CPU消耗時(shí)間明顯低于DE算法，局部搜索能力表現(xiàn)最佳.

圖8 各個(gè)算法運(yùn)行50次目標(biāo)函數(shù)值和CPU消耗時(shí)間Fig.8 Objective function value and CPU consumption time of each algorithm running 50 times

表4 各個(gè)算法運(yùn)行50次目標(biāo)函數(shù)值平均值

耗時(shí)間的平均值在總體上具有較優(yōu)效果，收斂的最優(yōu)目標(biāo)函數(shù)值相較于PSO算法降低了37.34%，同時(shí)CPU消耗時(shí)間節(jié)省了31.62%.由于自適應(yīng)差分進(jìn)化算法增加了種群的擾動(dòng)度，導(dǎo)致局部搜索能力下降.雖然改進(jìn)的差分進(jìn)化算法相對(duì)于標(biāo)準(zhǔn)差分進(jìn)化算法最優(yōu)目標(biāo)函數(shù)值只降低了0.017%，但是CPU消耗時(shí)間節(jié)省了32.12%，所以，改進(jìn)的算法在加速算法的收斂性上具有顯著的效果.

表5 各個(gè)算法運(yùn)行50次CPU消耗時(shí)間的平均值

3.2 多批次多訂單分配實(shí)驗(yàn)分析

為驗(yàn)證多批次多訂單分配的實(shí)驗(yàn)效果，采用LGDE算法對(duì)模型進(jìn)行求解，模型以每一批次各個(gè)分區(qū)的最大完工時(shí)間為目標(biāo)，最后保證所有批次各個(gè)分區(qū)工作負(fù)載均衡.分別采用遺傳算法、粒子群優(yōu)化算法、標(biāo)準(zhǔn)差分進(jìn)化算法、自適應(yīng)差分進(jìn)化算法對(duì)模型進(jìn)行對(duì)比實(shí)驗(yàn)分析，實(shí)驗(yàn)中采用數(shù)量為100，150，200及250 的4組訂單，每組訂單分別進(jìn)行多批分批實(shí)驗(yàn)，5種算法求得的實(shí)驗(yàn)結(jié)果如圖9和10所示.圖中：C′為訂單數(shù)量；Nr為小車數(shù)量.

圖9 各種算法實(shí)驗(yàn)結(jié)果Fig.9 Experimental results of each algorithm

為了更加清晰地分析LGDE算法對(duì)多批次多訂單分配情況，將LGDE算法的實(shí)驗(yàn)結(jié)果以三維曲面的形式表示，三維曲面的形式可以更加直觀的看到不同訂單不同揀選小車數(shù)量對(duì)實(shí)驗(yàn)?zāi)Ｐ偷挠绊?，如圖10所示.

圖10(a)表示LGDE算法的CPU損耗時(shí)間(TCPU，LGDE)與揀選小車數(shù)量和訂單揀選數(shù)量的關(guān)系.圖10(b)表示LGDE算法的最大完工時(shí)間與揀選小車數(shù)量和訂單揀選數(shù)量的關(guān)系.由圖10可知，LGDE算法得到的實(shí)驗(yàn)結(jié)果具有可預(yù)測(cè)的效果， 隨著揀選小車數(shù)量和訂單揀選數(shù)量的增加，CPU損耗時(shí)間和最大完工時(shí)間的趨勢(shì)是在增加的，即使在某些情況下，略微有實(shí)驗(yàn)偏差，實(shí)驗(yàn)結(jié)果依然可以清楚地顯示出LGDE算法的可靠性.

圖10 LGDE算法實(shí)驗(yàn)結(jié)果擬合曲面Fig.10 Fitting curves of experimental results of LGDE algorithm

圖11 不同訂單不同揀選小車對(duì)應(yīng)的每批次最大和最小完工時(shí)間的差值Fig.11 Difference between maximum and minimum completion time for each batch of different picking carts for different orders

4 結(jié)語(yǔ)

提出一種融合拉格朗日插值算法的改進(jìn)差分進(jìn)化算法求解倉(cāng)儲(chǔ)多訂單分批優(yōu)化，構(gòu)建了以揀貨小車運(yùn)行時(shí)間、貨架穩(wěn)定性及貨位的存貨能力為資源條件的貨位分配和以每批訂單中每一貨物分配到對(duì)應(yīng)分區(qū)的最優(yōu)貨位的最大完工時(shí)間為條件的訂單重新分批分配的兩級(jí)目標(biāo)模型.通過實(shí)驗(yàn)驗(yàn)證了改進(jìn)的差分進(jìn)化算法比傳統(tǒng)的啟發(fā)式算法在解決訂單分批問題上具有較佳的效果，相對(duì)于傳統(tǒng)的啟發(fā)式算法，可以得到更可靠的最大完工時(shí)間，有利于揀選小車更好地均衡工作量，為企業(yè)分配訂單提供有效的參考模型.同時(shí)，改進(jìn)的差分進(jìn)化算法的局部尋優(yōu)表現(xiàn)出更佳的全局搜索和局部搜索能力，避免算法早熟和無法收斂.在實(shí)際數(shù)據(jù)量較大的情況下，改進(jìn)的差分進(jìn)化算法求解出的倉(cāng)儲(chǔ)分批優(yōu)化消耗計(jì)算機(jī)的運(yùn)行時(shí)間也在合理的范圍內(nèi).為了更好地改善算法的性能，分布式計(jì)算結(jié)構(gòu)的設(shè)計(jì)以及加速算法是下一步的研究方向.