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

陳廣鋒， 余立潮

(東華大學 機械學院， 上海 201620)

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

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

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

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

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

1 問題模型

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

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

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

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

為了最小化最大完工時間，建立對應數學模型如下:

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

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

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

2.1 標準差分進化

(14)

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

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

(15)

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

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

ui,j(g+1)=

(16)

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

采用貪婪算法選擇進入下一代種群個體：

xi(g+1)=

(17)

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

(18)

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

2.2 時變交叉概率

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

(19)

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

(20)

式中：l為概率系數；tm為最大進化代數；T為當前進化代數；CR0為交叉概率算子；t′為當前消耗時間；t0為消耗時間參數.

2.3 拉格朗日插值

拉格朗日插值是一種在已知多個坐標點的情況下得到通過坐標點的近似函數的建模方法[20].采用拉格朗日插值構造近似函數加強差分進化算法的局部搜索能力.已知坐標點(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代種群個體的適應度.因此得到l次拉格朗日插值多項式：

Ll(xi,j(g))=

(21)

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

(22)

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

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

xi,2(g)=

(23)

(24)

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

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

步驟2計算新的染色體xr1(g),xr2(g)對應的函數值f(xr1(g)),f(xr2(g))；

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

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

2.4 自適應調整差分進化算法搜索方向

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

(25)

(26)

提出的自適應調整差分進化算法搜索方向是通過一個動態(tài)調整的閾值因子(DF)控制：

DF=

(27)

DF=

(28)

λg>λL

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

2.5 算法流程

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

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

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

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

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

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

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

步驟6統(tǒng)計當前代數種群的最優(yōu)值與最優(yōu)個體，并與步驟4所得結果進行比較，更新全局最優(yōu)解和最優(yōu)個體.按照式(25)、(28)更新DF和λg，迭代代數加1，轉至步驟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的隨機數編碼，表示貨位的選中與否.訂單分配階段采用如圖6所示的多批次個體編碼，根據編碼規(guī)則選擇相應的訂單編號為同一批次.運用LGDE算法計算出每個分區(qū)相應訂單貨物對應的貨位時間向量表，進入步驟2；

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

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

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

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

3 算法實例驗證

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

表1 改進差分進化算法參數設置Tab.1 Parameter settings of improved differential evolution algorithm

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

3.1 貨位分配實驗分析

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

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

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

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

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

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

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

圖8 各個算法運行50次目標函數值和CPU消耗時間Fig.8 Objective function value and CPU consumption time of each algorithm running 50 times

表4 各個算法運行50次目標函數值平均值

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

表5 各個算法運行50次CPU消耗時間的平均值

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

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

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

為了更加清晰地分析LGDE算法對多批次多訂單分配情況，將LGDE算法的實驗結果以三維曲面的形式表示，三維曲面的形式可以更加直觀的看到不同訂單不同揀選小車數量對實驗模型的影響，如圖10所示.

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

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

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

4 結語

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