改進遺傳算法求解訂單分批優化模型

馮愛蘭，王晨西，孔繼利

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

2.北京郵電大學 現代郵政學院，北京100876

1 引言

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

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

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

圖1 流利式貨架分區揀選系統場景

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

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

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

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

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

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

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

2 問題描述

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

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

系統中涉及到的時間如下：

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

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

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

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

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

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

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

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

3 模型構建

3.1 模型假設

基于對流利式貨架分區揀選系統的作業特點分析，模型假設如下：

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

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

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

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

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

（6）每個訂單中每種SKU數量為1；

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

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

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

圖2 分區揀選系統作業過程示意圖

模型參量如下：

I 表示訂單總數，i=1,2,…,I ；

B 表示流利式貨架分區數量，z=1,2,…,B；

m 表示貨架層數；

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

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

Vmax表示揀選設備最大容量；

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

PTzj表示第z 個區內的揀貨員揀選第j 批任務的揀選時間；

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

決策變量如下：

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

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

3.2 模型建立

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

Objective：

Subject to：

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

3.3 問題特點

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

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

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

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

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

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

4.1 個體編碼及解碼方式

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

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

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

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

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

4.2 適應度函數

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

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

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

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

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

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

4.3 選擇策略

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

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

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

4.4 交叉算子

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

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

圖5 訂單分批結果及任務釋放順序

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

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

圖6 交叉前的染色體

圖7 取交叉點后的染色體

圖8 交叉完的染色體

4.5 變異算子

變異操作是指通過改變染色體本身的基因值來生成新的個體，給個體增添新的基因結構，提高了群體多樣性，可以提高算法的局部搜索能力，有效地避免算法的早熟現象，是遺傳算法中非常重要的步驟。

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

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

5 實例分析

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

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

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

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

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

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

5.1 實驗參數與評價指標

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

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

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

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

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

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

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

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

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

5.2 實驗過程與結果分析

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

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

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

表1 1組訂單的各指標值

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

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

從表2可以看出，M-GA相對于M-SDSP、MQOB和FCFS 方法，在不同分區數量下，所有任務的完成時間CT 平均優化率達到2%～8%，在系統中的滯留時間RT的平均優化率達到34%～68%，平均履行周期FT 的平均優化率達到8%～19%，揀貨員在系統中的等待時間WT 的平均優化率達到15%～75%。可以得出：本文提出的MSD 方法在各項指標中，均優于先到先服務訂單分批方法和以最小化訂單分批數量為目標的訂單分批方法；并且設計的改進遺傳算法M-GA優于基于節約原則的種子算法M-SDSP。

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

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

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

6 儲位指派策略優化

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

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

圖12 分類隨機存儲側視示意圖

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

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

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

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

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

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

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

7 結束語

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

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

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

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