基于級聯(lián)的改進(jìn)差分進(jìn)化算法的倉儲多訂單分批優(yōu)化

陳廣鋒， 余立潮

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

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

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

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

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

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

1 問題模型

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

圖1 倉儲貨物揀選庫Fig.1 Warehouse goods picking library

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

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

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

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

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

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

(14)

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

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

(15)

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

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

ui,j(g+1)=

(16)

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

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

xi(g+1)=

(17)

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

(18)

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

2.2 時變交叉概率

由式(16)可知，如果CR越大，則選中個體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)前消耗時間；t0為消耗時間參數(shù).

2.3 拉格朗日插值

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

Ll(xi,j(g))=

(21)

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

(22)

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

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)個體染色體的一個基因位和變異最優(yōu)個體染色體的一個基因位作為插值點，得到兩個插值點：xi,0(g)和xi,1(g)，則xi,2(g)可由下式得到：

xi,2(g)=

(23)

(24)

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

步驟1輸入當(dāng)前迭代階段的xgbest(g)和該最優(yōu)染色體對應(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計算新的染色體xr1(g),xr2(g)對應(yīng)的函數(shù)值f(xr1(g)),f(xr2(g))；

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

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

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

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

(25)

(26)

提出的自適應(yīng)調(diào)整差分進(jìn)化算法搜索方向是通過一個動態(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較大時，算法進(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ù)組，并初步統(tǒng)計種群的最優(yōu)個體xgbest(g)以及最優(yōu)解f(xgbest(g))；

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

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

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

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

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

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

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

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

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

圖5 單批次個體編碼Fig.5 Single batch individual code

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

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

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

3 算法實例驗證

為了驗證所提算法的有效性，本文將采用具有圖1所示的貨物揀選庫結(jié)構(gòu)進(jìn)行實驗.將貨架從底層依次向上編號，所提算法的種群個體編碼將采用0～1的隨機(jī)數(shù)編碼，同時為每種貨物劃定可行的存儲貨位.用傳統(tǒng)的啟發(fā)式算法如遺傳算法、粒子群優(yōu)化算法進(jìn)行對比實驗，同時與標(biāo)準(zhǔn)的差分進(jìn)化算法以及改進(jìn)的自適應(yīng)差分進(jìn)化算法進(jìn)行對比分析.實驗計算機(jī)基本配置參數(shù)為：Intel(R)Pentinum(R)/CPUG2020@2.90 GHz/6 GB，操作系統(tǒng)為Windows 7，實驗算法采用Python 2.7版本編程語言進(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ù)中，交叉概率和縮放因子兩個參數(shù)對算法的性能影響較大，經(jīng)過多次仿真實驗，分析不同的參數(shù)組合對算法性能的影響，改進(jìn)的算法采用式(19)和(20)的變交叉概率因子有利于提高算法的性能.經(jīng)過大量實驗，將縮放因子取值在0.5左右取得較好實驗效果，局部和全局調(diào)整因子在0.04～0.3時，算法具有較好的收斂性能.對于對比實驗的算法中，本文將采用多次實驗確定算法的參數(shù).遺傳算法中的變異因子和交叉因子會對算法產(chǎn)生重要影響，在粒子群算法的慣性權(quán)重表明粒子對當(dāng)前的粒子速度的繼承情況，其對算法的性能和效率會產(chǎn)生影響，自適應(yīng)差分進(jìn)化算法中的交叉概率因子將采用式(19)進(jìn)行時變操作.參考文獻(xiàn)[11]設(shè)定的遺傳算法參數(shù)，經(jīng)過多次實驗將遺傳算法的交叉因子設(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 貨位分配實驗分析

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

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

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

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

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

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

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

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

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

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

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

3.2 多批次多訂單分配實驗分析

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

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

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

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

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

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

4 結(jié)語

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