改進(jìn)遺傳算法求解訂單分批優(yōu)化模型

馮愛蘭，王晨西，孔繼利

1.北京科技大學(xué) 機(jī)械工程學(xué)院，北京100083

2.北京郵電大學(xué) 現(xiàn)代郵政學(xué)院，北京100876

1 引言

目前，網(wǎng)上零售發(fā)展迅速，它給人們帶來極大便利的同時，也給電商配送中心帶來了巨大的挑戰(zhàn)。配送中心訂單呈現(xiàn)出小批量、多品種的特征，拆零揀選成為其主要的業(yè)務(wù)形態(tài)。這種業(yè)務(wù)形態(tài)下需要的勞動量更大，勞動程度更密集，因此，提高揀選作業(yè)效率極其重要。

在電商配送中心內(nèi)部，通常將存儲區(qū)和揀選區(qū)分開以提高運(yùn)營效率。在揀選區(qū)內(nèi)，往往根據(jù)貨品的揀選頻率設(shè)置不同的揀選區(qū)。揀選頻率較低的商品存放在普通隔板貨架區(qū)進(jìn)行揀選，揀選頻率較高的貨品則存放在流利式貨架區(qū)進(jìn)行揀選。流利式貨架擴(kuò)展性好，揀選效率高，出錯率低，單個SKU 存放數(shù)量較多，且補(bǔ)貨不影響揀貨流程，因此得到了廣泛的應(yīng)用。但在實際揀選中，流利式貨架揀選策略大多依據(jù)管理者經(jīng)驗，或引用普通隔板貨架適用的策略，導(dǎo)致揀貨員等待時間過長，揀選效率不高。

流利式貨架分區(qū)揀選系統(tǒng)，如圖1 所示，由于其揀選效率高，分區(qū)管理方便，責(zé)任便于追蹤，揀貨員易于熟悉自己的揀選區(qū)域，廣泛應(yīng)用于快速揀選區(qū)內(nèi)周轉(zhuǎn)頻率較高貨品的揀選。van Gils T 等人[1]討論了訂單分批、儲位指派、路徑策略、分區(qū)揀選之間的關(guān)系，通過實驗證明倉庫在考慮同時采用這四項策略時，將可以獲得顯著的收益。優(yōu)化流利式貨架分區(qū)揀選系統(tǒng)的訂單分批方法和儲位指派策略將會使揀選效率得到進(jìn)一步提升。學(xué)者李詩珍[2]通過仿真研究得出：訂單分批策略對減少揀貨作業(yè)的總時間影響最大。至今，對揀選系統(tǒng)中訂單分批方式、模型及求解算法的研究依然是熱點。目前主要的訂單分批方式有時窗分批、單品合計量分批、固定訂單量分批、智能型分批等。

圖1 流利式貨架分區(qū)揀選系統(tǒng)場景

從訂單分批模型來看，大多學(xué)者根據(jù)研究場景和優(yōu)化目標(biāo)的不同建立數(shù)學(xué)模型。王占磊[3]考慮雙區(qū)型倉庫中以總揀選距離最短為目標(biāo)，以多個揀選設(shè)備并存為條件建立優(yōu)化模型。趙蘭[4]以揀選總行走時間與分揀時間之和為優(yōu)化目標(biāo)，對分批模型和求解算法進(jìn)行仿真實驗，并分析了訂單數(shù)量、批次容量等參數(shù)對優(yōu)化目標(biāo)的影響。馬飛[5]考慮路徑相似度，以分批后所有批次的總相似程度最大為目標(biāo)建立數(shù)學(xué)模型。王轉(zhuǎn)等人[6]基于電商配送中心人到貨整箱揀選系統(tǒng)，考慮揀選器具和商品包裝體積，構(gòu)造了以最大化里程節(jié)約量為目標(biāo)的訂單分批模型。王旭坪等人[7]考慮訂單完成期限，建立以最小化平均有效訂單服務(wù)時間為目標(biāo)的訂單分批模型。Jiang Xiaowei[8]考慮帶緩存區(qū)的訂單分批及任務(wù)釋放順序問題，建立以總作業(yè)時間最短為目標(biāo)的訂單分批模型。

在模型求解方法上，大多學(xué)者考慮相似度規(guī)則，設(shè)計啟發(fā)式算法來求解。訂單分批問題是NP 難問題，精確算法難以適應(yīng)實際揀選系統(tǒng)，目前主要有種子算法、節(jié)約算法、數(shù)據(jù)挖掘算法、智能算法等。Tseng 等[9]研究了兩種不同揀選路徑規(guī)則下的9 種種子選取規(guī)則和10種訂單添加規(guī)則的表現(xiàn)。Lam 等[10]給訂單設(shè)置優(yōu)先規(guī)則，根據(jù)優(yōu)先級順序再考慮揀貨箱約束，進(jìn)行訂單合并分批。魏偉[11]利用節(jié)約算法進(jìn)行訂單路徑計算并設(shè)計遺傳算法求解以最短路徑為目標(biāo)的數(shù)學(xué)模型，最后通過仿真驗證其有效性。馬飛[5]用數(shù)據(jù)挖掘中的系統(tǒng)聚類分析方法求解訂單分批模型。吳天行[12]引入“反學(xué)習(xí)”概念，對傳統(tǒng)的蜂群算法加以改進(jìn)，提升求解訂單分批算法的性能。Xiang Xi 等[13]用變鄰域搜索算法求解了其提出的訂單分批模型。邵澤熠等[14]針對傳統(tǒng)K-均值算法中K 值人為確定造成聚類結(jié)果誤差大的缺點，采用密度和最小距離綜合最優(yōu)指標(biāo)確定多個初始聚類中心，并運(yùn)用改進(jìn)遺傳K-均值算法確定最優(yōu)分批數(shù)量，進(jìn)行訂單分批優(yōu)化。Hong S等人[15]考慮了流利式貨架揀選系統(tǒng)中的擁堵問題，建立訂單分批模型對系統(tǒng)中的等待時間進(jìn)行了優(yōu)化。

學(xué)者對訂單分批的研究多考慮揀貨員的揀選時間及揀貨路徑的因素，忽略了任務(wù)在系統(tǒng)中的滯留給訂單響應(yīng)速度帶來的影響。在流利式貨架分區(qū)揀選系統(tǒng)中，任務(wù)在系統(tǒng)中的滯留會延長訂單響應(yīng)速度，并且給緩存區(qū)造成一定壓力，進(jìn)而增加揀選系統(tǒng)的空間成本。

學(xué)者對儲位指派策略的研究，忽略了貨架高低對揀貨員揀取帶來的影響，當(dāng)貨品存放至不同層數(shù)時，會導(dǎo)致不同的揀取時間，當(dāng)訂單行數(shù)增加時，可以優(yōu)化的空間非常大。Petersen 等人[16]比較了分類存儲和隨機(jī)存儲，考慮了類的數(shù)量，發(fā)現(xiàn)分類存儲比隨機(jī)存儲節(jié)約揀貨員的行走時間。李曉春[17]研究了流利式貨架分區(qū)揀選系統(tǒng)中，在揀貨員揀貨速度不同的情況下，通過對品項在各分區(qū)間儲位的安排以平衡各分區(qū)揀貨員的作業(yè)量，提出了儲位指派算法。但在電商背景下，商品變化比較頻繁，商品周轉(zhuǎn)率易隨季節(jié)變動，定位存儲的管理成本較大。

在分區(qū)揀選系統(tǒng)中，揀貨員之間互相影響，訂單分批問題不僅要考慮訂單分批結(jié)果，還要考慮分批后的任務(wù)釋放順序。相同的訂單分批結(jié)果，當(dāng)任務(wù)釋放順序不同時，系統(tǒng)的處理效率會有很大差異。流利式貨架作為快速揀選區(qū)的常用貨架，提升倉庫整體揀貨效率和訂單響應(yīng)速度非常重要。由于其布局的特殊性，無需考慮路徑帶來的影響，普通貨架中的訂單分批策略是否適應(yīng)流利式貨架值得討論。

本文考慮流利式貨架分區(qū)揀選系統(tǒng)中相鄰區(qū)域互相影響的特點，考慮減少相鄰區(qū)域作業(yè)時間的差值（Minimize the sum of the differences of working time between any adjacent areas）以減少揀貨員在交接處的等待時間和貨物在系統(tǒng)中的滯留時間，以所有相鄰區(qū)域作業(yè)時間差值之和最小和訂單分批數(shù)量最小為目標(biāo)，建立多目標(biāo)規(guī)劃數(shù)學(xué)模型，此模型用MSD 表示，并用改進(jìn)的遺傳算法求解訂單分批結(jié)果及任務(wù)釋放順序，對流利式貨架分區(qū)揀選系統(tǒng)進(jìn)行優(yōu)化。

在儲位指派方式上，本文從揀貨員揀取的便捷性出發(fā)，將周轉(zhuǎn)頻率較高的貨品存放至流利式貨架中揀貨員最容易揀取的層數(shù)，以減少總體揀貨時間，提出分類隨機(jī)指派策略。

2 問題描述

流利式貨架分區(qū)揀選系統(tǒng)就是將流利式貨架劃分出多個揀選區(qū)域進(jìn)行作業(yè)，相鄰區(qū)域處設(shè)置有緩存區(qū)，在整個揀選過程中，各個揀選區(qū)域大小保持不變的揀選系統(tǒng)。由于不等分區(qū)在實際場景中應(yīng)用較少，且分區(qū)方案受多種因素影響，本文將研究場景設(shè)定為隨機(jī)存儲下的等分區(qū)接力式揀選系統(tǒng)，對于不等分區(qū)揀選系統(tǒng)，本文研究方法同樣適用。

流利式貨架分區(qū)揀選系統(tǒng)中，分區(qū)大小相同，且在揀選過程中大小不變，每個區(qū)內(nèi)有一名揀貨員，每個揀貨員負(fù)責(zé)相應(yīng)區(qū)域的揀選作業(yè)，如圖2 所示，揀選作業(yè)方向從左至右，區(qū)域2 的揀貨員相對于區(qū)域1 為下游揀貨員，相對于區(qū)域3 為上游揀貨員，相鄰區(qū)域交接處設(shè)有交接緩存區(qū)（Interface buffer）。每一名揀貨員從左側(cè)緩存區(qū)或任務(wù)釋放端領(lǐng)取任務(wù)，推著揀貨箱（Container）揀完相應(yīng)區(qū)域的任務(wù)后，將揀貨箱放至下游的緩存區(qū)或任務(wù)完成端，之后空手返回上游的緩存區(qū)領(lǐng)取新任務(wù)，如果緩存區(qū)無待揀選任務(wù)則靜止等待，直到有任務(wù)出現(xiàn)。每個揀貨員配有手持終端，任務(wù)開始時，手持終端掃描箱子上的二維碼，提取任務(wù)，任務(wù)完成后，再次掃描二維碼，確認(rèn)完成當(dāng)前區(qū)域的任務(wù)。

系統(tǒng)中涉及到的時間如下：

任務(wù)開始時間：每個區(qū)域的揀貨員開始新任務(wù)，完成手持終端與揀貨箱任務(wù)綁定工作的時間，即揀選前的準(zhǔn)備工作時間；

揀選時間：揀貨員讀取任務(wù)，尋找待揀選商品，揀取商品放至揀貨箱的時間；

前進(jìn)行走時間：揀貨員在有揀選任務(wù)時，在所負(fù)責(zé)區(qū)域內(nèi)推著揀貨箱向下游前進(jìn)的時間；

任務(wù)完成時間：揀貨員完成任務(wù)后，將揀貨箱放至緩存區(qū)，并進(jìn)行設(shè)備操作的時間；

返回行走時間：揀貨員空手返回至上游緩存區(qū)的時間；

等待時間：揀貨員返回至上游緩存區(qū)時，沒有待揀選任務(wù)，進(jìn)而靜止等待的時間；

作業(yè)時間：揀貨員開始任務(wù)到完成任務(wù)返回出發(fā)點的所有時間，即工作時間。

在串行揀選中，同一個任務(wù)依次進(jìn)入每個揀選區(qū)域，不同區(qū)域每個人揀選的任務(wù)是不一樣的，每個任務(wù)經(jīng)過每個區(qū)域都會產(chǎn)生任務(wù)開始時間、揀選時間、前行行走時間、任務(wù)完成時間和返回行走時間，即當(dāng)前任務(wù)在當(dāng)前區(qū)域的作業(yè)時間。揀貨員在系統(tǒng)中的等待和貨物在系統(tǒng)中的滯留時間幾乎不可避免，不僅造成了時間的浪費(fèi)，也會造成揀貨員工作負(fù)荷的不平衡，如何減小所有揀貨員完成任務(wù)的總時間，減少人員在交接處的等待消耗以提高系統(tǒng)效率，降低人員成本，是管理者迫切需要解決的問題；如何降低任務(wù)在系統(tǒng)中的滯留時間以縮短任務(wù)的履行時間，提高訂單響應(yīng)速度，是提高顧客滿意度的迫切需要。

3 模型構(gòu)建

3.1 模型假設(shè)

基于對流利式貨架分區(qū)揀選系統(tǒng)的作業(yè)特點分析，模型假設(shè)如下：

（1）貨架中儲位大小相同，且同種商品只存在貨架一處；

（2）揀貨員的任務(wù)熟練程度相同，由于每層貨架揀選的便捷程度不同，每層貨物的揀取時間不同；

（3）揀貨員的揀貨行走速度和空手行走速度視為相同且恒定，忽略加速時間和減速時間；

（4）貨品補(bǔ)充及時，不會缺貨；

（5）揀貨員一次揀取動作只揀取一個訂單中一個品項；

（6）每個訂單中每種SKU數(shù)量為1；

（7）訂單不能分割，也不能插單；

（8）每個訂單中所含商品的總體積不超過揀貨箱容積；流利式貨架揀選的訂單非顧客原始訂單，當(dāng)待揀選訂單總體積超過揀貨箱容積時，訂單不再進(jìn)行分批；

（9）不超過揀貨箱最大容積限制的任務(wù)都可以放進(jìn)揀貨箱進(jìn)行揀選，本文忽略商品的形狀及三維，在設(shè)置揀貨箱容積時，會考慮將最大揀貨箱容積限制的設(shè)定數(shù)值小于揀貨箱的實際容積。

圖2 分區(qū)揀選系統(tǒng)作業(yè)過程示意圖

模型參量如下：

I 表示訂單總數(shù)，i=1,2,…,I ；

B 表示流利式貨架分區(qū)數(shù)量，z=1,2,…,B；

m 表示貨架層數(shù)；

nz表示第z 區(qū)最后一列的編號，n0=0；

f 表示揀貨位編號，圖3是一個m 為4的貨位編號順序；

Vmax表示揀選設(shè)備最大容量；

Vf表示第f 個儲位處所存取商品的單位體積；

PTzj表示第z 個區(qū)內(nèi)的揀貨員揀選第j 批任務(wù)的揀選時間；

ptf表示第f 個儲位處所存取商品的單位揀選時間；

決策變量如下：

J 表示訂單合并批次數(shù)量，j=1,2,…,J ；

圖3 流利式貨架儲位編號順序

3.2 模型建立

在流利式貨架中，人員的總行走時間與所有任務(wù)的路徑長度和速度相關(guān)，速度相同且恒定的情況下，減小任務(wù)數(shù)量可以縮減人員行走時間；減小相鄰區(qū)域作業(yè)時間的差值可以縮減人員在系統(tǒng)中的等待時間或貨物在系統(tǒng)中的滯留時間，以此縮減完成任務(wù)的總時間，提高系統(tǒng)效率。所以，本文以相鄰區(qū)域作業(yè)時間差值之和最小和訂單分批數(shù)量最小為目標(biāo)，建立流利式貨架分區(qū)揀選系統(tǒng)的數(shù)學(xué)模型。

Objective：

Subject to：

式（1）為最小化分批數(shù)量；式（2）為最小化所有相鄰區(qū)域作業(yè)時間差值的和，由于相鄰區(qū)域的任務(wù)開始時間、前行行走時間、任務(wù)完成時間和返回行走時間相同，故在公式中相互抵消；式（3）為J 的取值范圍；式（4）為第z 個區(qū)的揀貨員揀選第j 批任務(wù)的揀貨時間；式（5）表示一個訂單只能分到一個批次里，即訂單不能分割；式（6）為揀貨箱的容量約束，每一個揀貨任務(wù)中商品的總體積不能超過揀貨箱最大容量。約束（6）保證了目標(biāo)函數(shù)（1）在最小化的過程中不會出現(xiàn)不可行解。這是一個多目標(biāo)0-1整數(shù)規(guī)劃模型。

3.3 問題特點

本文提出的訂單分批模型與一般的訂單分批問題相比，有以下特點：

（1）兩個目標(biāo)的處理問題。在模型中，目標(biāo)2 是( J-1) ×( B-1) 個差值的和，所以目標(biāo)1 中J 的最小化將體現(xiàn)在目標(biāo)2 中，兩者不是獨立的兩個目標(biāo)。因此，在求解過程中如何處理兩個目標(biāo)之間的關(guān)系直接影響解的收斂過程。求解多目標(biāo)問題的方法主要有：主要目標(biāo)法、統(tǒng)一目標(biāo)法、分層序列法、Pareto 法等。本文中，由于兩個目標(biāo)有相關(guān)性，量級也不同，較難判定權(quán)重，難以歸一化處理，且一個目標(biāo)在另一個目標(biāo)中有所體現(xiàn)，因此考慮對兩個目標(biāo)設(shè)置優(yōu)先級，用分層序列法求解。分層序列法首先根據(jù)目標(biāo)的重要程度進(jìn)行排序，每次都在前一目標(biāo)的最優(yōu)解內(nèi)，尋找下一目標(biāo)的最優(yōu)解，直到最后求出共同的最優(yōu)解。訂單分批數(shù)量J 會直接影響揀貨員的行走距離，進(jìn)而影響總完成時間，所以優(yōu)先目標(biāo)1，在目標(biāo)1每次達(dá)到最優(yōu)的情況下，尋找令目標(biāo)2差值之和最小的個體。

（2）解的結(jié)構(gòu)復(fù)雜。流利式貨架分區(qū)揀選系統(tǒng)中，相鄰揀貨員的作業(yè)時間差值會影響貨物在系統(tǒng)中的滯留和揀貨員在系統(tǒng)中的等待，因此訂單分批之后的任務(wù)釋放順序非常重要。訂單分批結(jié)果及任務(wù)釋放順序都會影響目標(biāo)2 差值的大小，在算法求解過程中，既要得到訂單分批結(jié)果，又要得到任務(wù)釋放順序。

（3）模型目標(biāo)對優(yōu)化指標(biāo)的客觀反映。本文的目標(biāo)是最小化分批數(shù)量和最小化相鄰區(qū)域的作業(yè)時間差值，兩者都不直接是反映倉庫揀貨效率及訂單響應(yīng)度的指標(biāo)，但是通過減少作業(yè)時間的差值可以縮小揀貨員的作業(yè)總完成時間和任務(wù)的平均履行周期。

4 求解MSD模型的改進(jìn)遺傳算法

這種場景下的訂單分批問題，類似于多目標(biāo)裝箱問題，除了考慮使用的箱子數(shù)最小，還要考慮縮短相鄰區(qū)域作業(yè)時間差值。從文獻(xiàn)來看，研究多目標(biāo)裝箱問題的文獻(xiàn)不多，可參考的算法較少。但是遺傳算法在訂單分批問題的研究中應(yīng)用廣泛，充分證明了它在解決訂單分批問題上的可行性，且遺傳算法有很強(qiáng)的全局搜索能力和較強(qiáng)的魯棒性，所以本文設(shè)計了遺傳算法求解所提出的MSD訂單分批數(shù)學(xué)模型。

4.1 個體編碼及解碼方式

采用實數(shù)編碼方式，訂單數(shù)為I ，則染色體為I 以內(nèi)整數(shù)的隨機(jī)排列?？紤]揀貨箱容積限制，按排列順序進(jìn)行分批。用一個實例來表述：假設(shè)訂單個數(shù)為20，每個訂單都可計算出其商品總體積，訂單編號為1到20之間的整數(shù)，則染色體編碼為20以內(nèi)整數(shù)的隨機(jī)排列，如圖4所示，圖中第一行為一個染色體排列。

解碼過程如下：按照染色體排列，根據(jù)圖4 第二行中每個訂單對應(yīng)的商品總體積。將貨品依次進(jìn)行分批，當(dāng)待分批訂單不能加入到當(dāng)前批次時，此訂單成為一個新的批次，不限定訂單的批次數(shù)。假設(shè)揀貨箱容積為15，計算此染色體所需分批次數(shù)。訂單18 為第一個批次，訂單8的體積加上訂單18大于15，所以不能分入一批，訂單8 為第二批，訂單14 的體積4.87 加上7.76 小于15，則訂單14與訂單8為第2批，訂單6的體積4.36加上4.87，再加上7.76 大于15，則訂單6 為第3 批，依次對每個訂單進(jìn)行分批，得到訂單分批結(jié)果及任務(wù)釋放順序，如圖5所示，案例共分11批。

這種編碼方式下，任意產(chǎn)生一組排列都是可行解，一組排列對應(yīng)一種訂單分批結(jié)果和任務(wù)釋放順序，有效解空間為I!。

初始種群生成采用隨機(jī)生成的方式，隨機(jī)生成一定數(shù)量的染色體，每個染色體是I 以內(nèi)整數(shù)的隨機(jī)排列。

許多算法中采用的限定產(chǎn)生特定批次數(shù)的編碼方式，會產(chǎn)生不可行解，并且會引導(dǎo)種群向每批任務(wù)揀貨箱容積利用率高的方向進(jìn)化，忽略了任務(wù)釋放順序的優(yōu)化及接力式揀選系統(tǒng)的特點。本文采用的編碼方式，雖然初始隨機(jī)產(chǎn)生的染色體對應(yīng)的訂單分批數(shù)量較多，但是多數(shù)染色體對應(yīng)的每批任務(wù)總體積相差較小，這樣就會在遺傳過程中很好地利用任務(wù)均衡性的優(yōu)點，以減少差值。同時，目標(biāo)函數(shù)中最小化訂單分批次數(shù)的目標(biāo)也會引導(dǎo)種群向揀貨箱容積利用率高的方向進(jìn)化。

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

適應(yīng)度函數(shù)在算法設(shè)計中，直接影響算法的進(jìn)化方向和解的質(zhì)量。本文的多目標(biāo)問題采用分層序列法求解訂單分批結(jié)果及任務(wù)釋放順序，由于目標(biāo)2為最小化( J-1) ×( B-1) 個相鄰區(qū)域作業(yè)時間差值的和k（時間以秒為單位，k 為大于1的整數(shù)），每個差值和J 的縮小都會降低總差值k，因此優(yōu)先目標(biāo)1，在目標(biāo)1每次達(dá)到最小的情況下，尋找目標(biāo)2的最優(yōu)解。為了保留k 較小個體的優(yōu)秀基因結(jié)構(gòu)，又保證J 向最小化的方向進(jìn)化，設(shè)計了以下適應(yīng)度函數(shù)。

步驟1 計算所有待分批訂單的商品總體積，除以揀貨箱的最大容積Vmax，向上取整得到這批訂單所需的理論最小分批數(shù)量Jmin。

步驟2 計算每個染色體所需的訂單分批數(shù)量J 、訂單分批結(jié)果及任務(wù)釋放順序，方法如4.1節(jié)中介紹，案例中J=11，訂單分批結(jié)果及任務(wù)釋放順序如圖5。

步驟3 通過訂單分批結(jié)果及任務(wù)釋放順序計算每個染色體對應(yīng)的所有相鄰區(qū)域作業(yè)時間差值，再求和得到k。

步驟4 適應(yīng)度計算公式如式（7）所示：

將訂單分批數(shù)量J 放在指數(shù)位置，將差值k 放在底數(shù)位置，這樣當(dāng)適應(yīng)度比較時，J 較小的染色體會占據(jù)主要優(yōu)勢，被選擇的幾率更大。當(dāng)k 相同時，會優(yōu)先選擇J 較小的個體，J 相同時，會優(yōu)先選擇k 小的個體。這樣在選擇過程中，優(yōu)先了目標(biāo)1，便于在目標(biāo)1最小的情況下，尋找k 最小的個體，也給k 較小但是J 沒有達(dá)到最小的個體進(jìn)化空間，保留其令k 值小的優(yōu)秀基因結(jié)構(gòu)，使得算法在向揀貨箱容積利用率高的方向進(jìn)化。

4.3 選擇策略

遺傳算法中，根據(jù)適應(yīng)度值對每個個體進(jìn)行操作。遵循“適者生存”的原則，適應(yīng)度越高的個體，越容易被選中進(jìn)入下一代。

本文結(jié)合精英保留策略和輪盤賭的方法作為新的選擇策略。先用輪盤賭的方法選出交叉?zhèn)€體進(jìn)行交叉；經(jīng)過交叉與變異之后，再進(jìn)行精英保留策略；父代和子代分別通過適應(yīng)度排序，選取父代x%的優(yōu)秀個體和子代的優(yōu)秀個體組成新的種群，即用父代x%的優(yōu)秀個體替換掉子代相同數(shù)量的較差個體。

這樣優(yōu)秀個體也可以參與交叉、變異，為產(chǎn)生更優(yōu)秀的基因結(jié)構(gòu)提供可能，也可以在組成新的種群時保留歷史最優(yōu)個體，使算法盡快收斂。

4.4 交叉算子

輪盤賭的選擇操作完成之后，算法通過交叉算子產(chǎn)生新的個體。交叉是形成新個體的重要步驟，也是遺傳算法不同于其他進(jìn)化算法的重要特征。

圖4 訂單數(shù)量為20的一組訂單排列及對應(yīng)的商品總體積

圖5 訂單分批結(jié)果及任務(wù)釋放順序

通過編碼方式可知，一個解內(nèi)部整數(shù)的順序調(diào)整可以變化訂單分批方式和任務(wù)釋放順序，每個整數(shù)是不能重復(fù)的且不可遺漏的，基于此考慮采用基于映射的交叉方式，隨機(jī)選擇兩個點，兩個切入點之內(nèi)的部分保留，并形成映射關(guān)系，將兩端與其相同的基因替換為形成映射關(guān)系的基因。由于在交叉變異之后還會有父代的精英保留操作，所以交叉概率設(shè)置為1，以增強(qiáng)群體中新結(jié)構(gòu)的引入，也不用擔(dān)心改良基因的丟失速度。在交叉過程中，隨機(jī)選擇交叉點和中間段的交叉長度。

例如，圖6為兩條染色體，隨機(jī)選擇兩個交叉點，假定選取第4與第5個基因之間為第一個交叉點，第11與第12 個基因之間為第二個交叉點，兩個交叉點將每個染色體分成三段，如圖7所示；形成三對映射關(guān)系：（11，4，10，12，14）；（18，6）；（9，2）；經(jīng)過映射變換后新的染色體如圖8所示。

圖6 交叉前的染色體

圖7 取交叉點后的染色體

圖8 交叉完的染色體

4.5 變異算子

變異操作是指通過改變?nèi)旧w本身的基因值來生成新的個體，給個體增添新的基因結(jié)構(gòu)，提高了群體多樣性，可以提高算法的局部搜索能力，有效地避免算法的早熟現(xiàn)象，是遺傳算法中非常重要的步驟。

根據(jù)解的特點，采用隨機(jī)兩點變異，也就是交換變異。參與變異的個體數(shù)等于種群大小乘以交叉概率，每個待變異個體隨機(jī)選擇兩個點進(jìn)行交換，形成新的個體。如圖9所示，第1行是變異前的染色體，將第5個基因和第14個基因交換，形成第二行的新染色體。

圖9 變異前的染色體和變異后的染色體

5 實例分析

本文將MSD的訂單分批方法與以最小化訂單分批數(shù)量為目標(biāo)的單目標(biāo)分批方法、先到先服務(wù)訂單分批方法進(jìn)行對比，驗證MSD訂單分批方式的優(yōu)化效果，并將改進(jìn)的遺傳算法與基于節(jié)約原則的種子算法對比，驗證改進(jìn)遺傳算法求解MSD方法的效果。

種子算法在訂單分批問題中應(yīng)用廣泛，由于本文的研究背景是流利式貨架，用基于節(jié)約原則的種子算法（Seed algorithm based on saving principle）求解MSD數(shù)學(xué)模型，選取種子的方法及訂單累加原則要考慮流利式貨架分區(qū)揀選系統(tǒng)的特點。選取種子的方法為：計算每個訂單在每個區(qū)作業(yè)時間的標(biāo)準(zhǔn)差，選擇標(biāo)準(zhǔn)差最小的訂單作為種子訂單；累加訂單方式為：節(jié)約原則，選取剩余訂單池中與種子訂單合并后，所有相鄰區(qū)域作業(yè)時間差值之和減小量最大的訂單進(jìn)行累加。種子訂單采取不斷更新模式，每次并入種子訂單都更新種子。在累加過程中，考慮揀貨箱最大容積約束，不能再添加訂單時，將當(dāng)前種子作為新的一批任務(wù)，重新選取新種子。由于計算差值時，要將所有訂單進(jìn)行分批，因此除去已分批訂單，將剩余訂單按體積降序排列計算差值之和k 。在算法過程中，加入優(yōu)秀個體保留原則，每次累加訂單，都將當(dāng)前最優(yōu)個體與歷史個體比較，選取最優(yōu)個體作為新的歷史最優(yōu)個體，此算法結(jié)果用M-SDSP表示。

先到先服務(wù)訂單分批（First Come First Served）是按訂單到達(dá)時間先后順序，考慮揀貨設(shè)備容積約束進(jìn)行分批，其靈活性高、簡單、快速，可以隨時插單，被廣泛應(yīng)用于現(xiàn)實場景中，是一種經(jīng)典的訂單分批方法，其結(jié)果用FCFS表示。

以最小化訂單分批數(shù)量（Minimize Quantity of Order Batching）為目標(biāo)的模型，類似求解將一定數(shù)量的物品放至箱子求最小箱子數(shù)量的一維裝箱問題，其目標(biāo)函數(shù)為最小化分批數(shù)量，考慮揀貨箱容積約束和訂單不能分割。采用經(jīng)典的裝箱問題算法——降序首次適配算法（First Fit Decreasing）求解，其結(jié)果用MQOB表示。

本文提出的以最小化相鄰區(qū)域作業(yè)時間差值之和與最小化訂單分批數(shù)量為目標(biāo)的MSD訂單分批數(shù)學(xué)模型，用前一章設(shè)計的遺傳算法GA 進(jìn)行求解，其結(jié)果用M-GA表示。

基于MATLAB R2015a開發(fā)環(huán)境，設(shè)計實驗背景和參數(shù)，考慮在不同分區(qū)數(shù)量下，分析比較不同方法或算法的結(jié)果，采用仿真計算的方法求出各種方法下的各指標(biāo)值，對結(jié)果進(jìn)行比較和分析。

5.1 實驗參數(shù)與評價指標(biāo)

流利式貨架常用的布局有直線型揀選線和U 型揀選線，本文選取直線型布局進(jìn)行研究，研究結(jié)果對U 型布局同樣適用。選用的流利式貨架為4 層，在揀選方向，分別等分為3區(qū)，4區(qū)，5區(qū)進(jìn)行不同場景的實驗。圖2是分區(qū)數(shù)量為4的流利式貨架布局，儲位共有4層，100列，總長50 m，400 個儲位即存放400 種SKU，存儲方式采用隨機(jī)存儲，儲位編號分布如圖3所示。

由于流利式貨架一般進(jìn)行揀選頻率較高的商品揀選，故將存在貨架中的400 種SKU，按揀選頻率分成A類，B 類，C 類，種類數(shù)占比為1∶1∶2。隨機(jī)生成10 組訂單進(jìn)行實驗，每組訂單200 個，每個訂單包含1～5 種SKU，每種SKU數(shù)量為1件，商品體積都在0.1～6 L之間。

由于揀貨員揀取每層貨架上貨物的便捷程度不同，經(jīng)查找資料，揀貨員揀取的便捷程度從上往下依次是第三層，第二層，第一層，第四層，故本文設(shè)置揀貨員揀取第一層至第四層中每件商品的時間依次是14 s，12 s，10 s，16 s。

揀貨員在揀選時的行走速度為0.5 m/s，返回時的行走速度為1 m/s，每個區(qū)域的任務(wù)開始時間和任務(wù)完成時間為7.5 s，揀貨箱最大容量為100 L。

本文提出的MSD訂單分批方法考慮縮小揀貨員的等待時間和貨物的滯留時間，進(jìn)而縮短所有任務(wù)的總完成時間和平均履行周期。因此選取以下指標(biāo)衡量各方法或算法的表現(xiàn)：

所有任務(wù)的完成時間CT ：從0 s開始任務(wù)計時，到CT 時所有任務(wù)結(jié)束，即最后一批任務(wù)離開揀選系統(tǒng)的時刻，亦是完成所有揀選任務(wù)的時間。

所有任務(wù)的平均滯留時間RT ：所有任務(wù)在緩存區(qū)的滯留時間，當(dāng)揀貨員還未返回至緩存區(qū)時，上游揀貨員已將任務(wù)放至緩存區(qū)，貨物就會滯留直至下游揀貨員返回取走；貨物滯留數(shù)量影響到交接緩存區(qū)的容量，如果滯留貨物較多，則需要更多的緩存空間，影響倉庫的布局，增加設(shè)備和空間成本。

所有任務(wù)的平均履行周期FT ：每批任務(wù)從進(jìn)入揀選系統(tǒng)到離開揀選系統(tǒng)的時間為任務(wù)的履行周期，計算所有任務(wù)履行周期的平均值。

所有揀貨員的等待時間之和WT ：所有人完成整個揀選過程中的等待時間，以此來衡量人員的時間浪費(fèi)。

5.2 實驗過程與結(jié)果分析

M-SDSP 通過不斷選取新種子和累計訂單得到訂單分批結(jié)果及任務(wù)釋放順序；FCFS 方式由于訂單到達(dá)順序有很大的隨機(jī)性，故隨機(jī)生成100 種到達(dá)順序，考慮揀貨箱最大容量約束，進(jìn)行訂單分批，得到不同指標(biāo)結(jié)果，求得100種到達(dá)順序下各指標(biāo)值的平均值。由于訂單的商品總體積確定，F(xiàn)FD算法是將訂單按商品總體積降序排列，考慮揀貨箱容積約束，將待揀選訂單依次添加至編號最小的批次里，所以在商品總體積都不相等的情況下，MQOB 方法的結(jié)果是一定的。本文提出的M-GA方法，在遺傳算法部分，經(jīng)過多次變換參數(shù)，調(diào)整遺傳算法策略，對比了不同參數(shù)下的結(jié)果和時間，最終確定遺傳算法的參數(shù)如下：種群大小為50，交叉概率為1，變異概率為0.3，精英保留數(shù)量為父代的20%。算法運(yùn)行得到滿意解，求得滿意解的各指標(biāo)值，每組訂單運(yùn)行10次，求各指標(biāo)值的平均值。得到滿意解后仿真計算求各指標(biāo)值的方法如圖10所示。

計算10組訂單的指標(biāo)值，表1展示了一組訂單在不同方法下的各指標(biāo)值，時間指標(biāo)均四舍五入為整數(shù)。計算每組訂單下，M-GA 相對于M-SDSP、FCFS 和MQOB各指標(biāo)的優(yōu)化率，取10 組訂單各指標(biāo)優(yōu)化率的平均值得到表2。

圖10 滿意解求各指標(biāo)值的流程圖

表1 1組訂單的各指標(biāo)值

表2 10組訂單M-GA相對其他方法各指標(biāo)的平均優(yōu)化率%

從表1 可以看出，M-GA 在所有任務(wù)的完成時間CT ，在系統(tǒng)中的滯留時間RT ，平均履行周期FT 和揀貨員在系統(tǒng)中的等待時間WT 等指標(biāo)中，均不同程度小于M-SDSP、MQOB和FCFS的指標(biāo)值。FCFS方法的訂單分批數(shù)量均多于M-SDSP、MQOB和M-GA，這是由于FCFS方法中訂單到達(dá)隨機(jī)，在揀貨箱容量約束下，訂單分批次數(shù)不能完全達(dá)到最小批次數(shù)。

從表2可以看出，M-GA相對于M-SDSP、MQOB和FCFS 方法，在不同分區(qū)數(shù)量下，所有任務(wù)的完成時間CT 平均優(yōu)化率達(dá)到2%～8%，在系統(tǒng)中的滯留時間RT的平均優(yōu)化率達(dá)到34%～68%，平均履行周期FT 的平均優(yōu)化率達(dá)到8%～19%，揀貨員在系統(tǒng)中的等待時間WT 的平均優(yōu)化率達(dá)到15%～75%?？梢缘贸觯罕疚奶岢龅腗SD 方法在各項指標(biāo)中，均優(yōu)于先到先服務(wù)訂單分批方法和以最小化訂單分批數(shù)量為目標(biāo)的訂單分批方法；并且設(shè)計的改進(jìn)遺傳算法M-GA優(yōu)于基于節(jié)約原則的種子算法M-SDSP。

相比兩種傳統(tǒng)的訂單分批模型，本文提出的考慮減小相鄰區(qū)域時間差值的訂單分批數(shù)學(xué)模型在達(dá)到最小分批數(shù)量的情況下，減小了相鄰區(qū)域作業(yè)時間差值之和，進(jìn)而縮短了揀貨員的等待時間WT 和貨物在系統(tǒng)中的滯留時間RT ，任務(wù)的平均履行周期FT 和所有任務(wù)的完成時間CT 也相應(yīng)減少。

通過以上案例可以看出，在分區(qū)揀選系統(tǒng)中，相鄰區(qū)域作業(yè)時間的差值不能完全等同于揀貨員的等待時間WT 和貨物在系統(tǒng)中的滯留時間RT ，但降低差值之和可以降低WT 和RT ，縮短任務(wù)完成時間CT ，進(jìn)而提高揀貨員的工作效率。

實驗結(jié)果表明，揀貨員人數(shù)的增加，加快了揀貨作業(yè)進(jìn)程，減少了所有任務(wù)的完成時間，進(jìn)而提升了系統(tǒng)效率；但人力成本也會增加，區(qū)域之間作業(yè)時間的差異也會增加揀貨人員作業(yè)的不平衡性，造成更多貨物滯留與人員等待上的時間浪費(fèi)。管理者需要在增加系統(tǒng)效率的收益與控制人員成本、降低時間消耗的付出之間權(quán)衡，結(jié)合各方面因素，找到一個合適的分區(qū)數(shù)量進(jìn)行空間布局。

6 儲位指派策略優(yōu)化

貨架高低會影響揀貨員揀取貨物的便捷性。貨架不同層存儲的貨物揀取時間不同，從資料中得出，第三層貨物最容易揀取，因此考慮揀選頻率較高的商品存儲在第三層，揀選頻率較低的貨品存儲在底層或第四層，每層內(nèi)部隨機(jī)存儲，增強(qiáng)存儲的靈活性，如圖11 所示，從上往下分別存儲C 類、B 類、A 類、C 類。根據(jù)其特點稱其為分類隨機(jī)存儲，其正視示意圖如圖12所示。

圖11 流利式貨架分類隨機(jī)存儲側(cè)視示意圖

圖12 分類隨機(jī)存儲側(cè)視示意圖

在前一章中采用了隨機(jī)存儲的指派方式，隨機(jī)存儲是流利式貨架中較為常見的存儲方式，本文旨在隨機(jī)存儲上進(jìn)行優(yōu)化。設(shè)計實驗比較隨機(jī)存儲和分類隨機(jī)存儲兩種儲位指派方式在各指標(biāo)上的表現(xiàn)。在兩種儲位指派方式下，用本文提出的考慮相鄰區(qū)域揀選時間差值的MSD 訂單分批方法計算前文生成的10 組訂單數(shù)據(jù)在3區(qū)、4區(qū)、5區(qū)情況下的各指標(biāo)值。

為了更清楚看到儲位指派的效果，增加兩項指標(biāo)，第一是任務(wù)平均理想履行時間DT ，即任務(wù)在系統(tǒng)中無滯留的時間，是每個區(qū)域揀貨員的任務(wù)開始時間、揀選時間、人員的前進(jìn)行走時間和任務(wù)完成時間之和，可以衡量人員在系統(tǒng)中的有效工作時間，分析儲位指派方式在揀貨時間上的優(yōu)化效果；第二是揀貨員工作時間的標(biāo)準(zhǔn)差SD，通過計算每個揀貨員在其負(fù)責(zé)區(qū)域的工作時間（不包含等待時間），得到揀貨員工作時間的標(biāo)準(zhǔn)差，以衡量揀貨員的工作負(fù)荷平衡。

表3展示了1組訂單在不同儲位指派方式下用M-GA求得的各項指標(biāo)值，計算分類隨機(jī)存儲相對于隨機(jī)存儲各指標(biāo)的優(yōu)化率，計算10 組實驗各指標(biāo)優(yōu)化率的平均值得到表4。

表3 1組訂單在不同指派方式下的各指標(biāo)值

表4 分類隨機(jī)存儲相對于隨機(jī)存儲各指標(biāo)的平均優(yōu)化率%

從表3 中可以看出，第一組訂單在不同分區(qū)數(shù)量下，分類隨機(jī)存儲在所有任務(wù)的完成時間CT 、理想履行時間DT 、平均履行周期FT 和揀貨員工作時間的標(biāo)準(zhǔn)差SD 均優(yōu)于隨機(jī)存儲。從表4 可以看出，分類隨機(jī)存儲相對于隨機(jī)存儲，所有任務(wù)的完成時間CT 優(yōu)化了8%～10%，理想履行時間DT 優(yōu)化了10%左右，所有任務(wù)的平均履行周期FT 優(yōu)化了20%左右，揀貨員工作時間的標(biāo)準(zhǔn)差SD 優(yōu)化了22%～49%。由于任務(wù)平均理想履行時間DT 的縮短并不能縮短相鄰區(qū)域作業(yè)時間的差值，故揀貨員的等待時間WT 和貨物的滯留時間RT不一定被優(yōu)化，但因為其縮短了所有任務(wù)的揀選的時間，因而提高了整體的運(yùn)行效率，使得分類隨機(jī)存儲整體表現(xiàn)優(yōu)于隨機(jī)存儲。

儲位指派方式會影響每個區(qū)域的揀貨時間，進(jìn)而影響相鄰區(qū)域的作業(yè)時間差異。分類隨機(jī)指派方式考慮將揀選頻率較高的商品存放至揀貨員最易揀取的層數(shù)，從根本上減少了每個區(qū)域的揀貨時間，提升了系統(tǒng)效率，這種思想會在訂單規(guī)模較大的情況下表現(xiàn)得更明顯，從而對整個倉庫的運(yùn)行產(chǎn)生比較重要的影響。

7 結(jié)束語

流利式貨架作為揀選周轉(zhuǎn)頻率較高貨品的常用貨架，其揀選效率的提高具有很重要的實際意義。本文考慮流利式貨架揀選系統(tǒng)的特點，提出以最小化相鄰區(qū)域作業(yè)時間差值之和與最小化訂單分批數(shù)量為目標(biāo)的訂單分批模型，相比傳統(tǒng)的先到先服務(wù)訂單分批和以最小化訂單分批數(shù)量為目標(biāo)的單目標(biāo)訂單分批方法，在所有任務(wù)的完成時間、總滯留時間、平均履行周期和所有揀貨員的等待時間指標(biāo)上，均表現(xiàn)優(yōu)秀。將本文的改進(jìn)遺傳算法與基于節(jié)約原則的種子算法對比，驗證了本文算法的求解效果。分區(qū)揀選系統(tǒng)需要考慮相鄰揀貨員之間的影響，所以本文提出的訂單分批模型不僅要考慮分批結(jié)果，還要考慮任務(wù)釋放順序。在遺傳算法設(shè)計中，也考慮了這一點。

儲位指派優(yōu)化中，提出的分類隨機(jī)指派方式充分考慮了揀貨員操作的便捷性，從揀貨人員的角度出發(fā)，在不增加揀貨員作業(yè)節(jié)奏的同時，整體縮減揀貨時間。這種將揀選頻率較高的貨品存放至揀貨主體最容易揀取層數(shù)的這種思想也可以應(yīng)用到更多揀選場景中。

在揀選系統(tǒng)中，本文的揀選主體是揀貨員，隨著機(jī)器人技術(shù)的普及，本文的研究成果也可以應(yīng)用到機(jī)器人揀選中。

本文研究的流利式貨架分區(qū)揀選系統(tǒng)中，揀貨員不可跨出自己的區(qū)域幫助其他揀貨員進(jìn)行揀選，未來可以對工作人員跨區(qū)協(xié)同揀貨進(jìn)行深入研究。