馮愛蘭，王晨西，孔繼利

1.北京科技大學 機械工程學院，北京100083

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

1 引言

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

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

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

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

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

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

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

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

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

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

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

2 問題描述

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

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

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

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

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

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

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

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

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

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

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

3 模型構(gòu)建

3.1 模型假設

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

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

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

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

（4）貨品補充及時，不會缺貨；

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

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

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

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

（9）不超過揀貨箱最大容積限制的任務都可以放進揀貨箱進行揀選，本文忽略商品的形狀及三維，在設置揀貨箱容積時，會考慮將最大揀貨箱容積限制的設定數(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表示揀選設備最大容量；

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

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

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

決策變量如下：

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

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

3.2 模型建立

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

Objective：

Subject to：

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

3.3 問題特點

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

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

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

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

4 求解MSD模型的改進遺傳算法

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

4.1 個體編碼及解碼方式

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

解碼過程如下：按照染色體排列，根據(jù)圖4 第二行中每個訂單對應的商品總體積。將貨品依次進行分批，當待分批訂單不能加入到當前批次時，此訂單成為一個新的批次，不限定訂單的批次數(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 批，依次對每個訂單進行分批，得到訂單分批結(jié)果及任務釋放順序，如圖5所示，案例共分11批。

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

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

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

4.2 適應度函數(shù)

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

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

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

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

步驟4 適應度計算公式如式（7）所示：

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

4.3 選擇策略

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

本文結(jié)合精英保留策略和輪盤賭的方法作為新的選擇策略。先用輪盤賭的方法選出交叉?zhèn)€體進行交叉；經(jī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)生新的個體。交叉是形成新個體的重要步驟，也是遺傳算法不同于其他進化算法的重要特征。

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

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

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

例如，圖6為兩條染色體，隨機選擇兩個交叉點，假定選取第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ù)解的特點，采用隨機兩點變異，也就是交換變異。參與變異的個體數(shù)等于種群大小乘以交叉概率，每個待變異個體隨機選擇兩個點進行交換，形成新的個體。如圖9所示，第1行是變異前的染色體，將第5個基因和第14個基因交換，形成第二行的新染色體。

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

5 實例分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖10 滿意解求各指標值的流程圖

表1 1組訂單的各指標值

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

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

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

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

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

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

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

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

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

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

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

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

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

表3 1組訂單在不同指派方式下的各指標值

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

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

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

7 結(jié)束語

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

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

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

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