“貨到人”訂單分批揀選作業優化研究

鄒 煒，趙洪鑾，李曉君，宿夢夢

（山東建筑大學 計算機科學與技術學院，山東 濟南 250101）

0 引言

隨著電商行業的迅速發展，電商企業需要處理數量眾多且種類繁雜的訂單，物流行業也面臨著巨大壓力。訂單揀選作業時間約占總作業時間的30%～40%，揀選作業成本約占到總作業成本的60%。為加快訂單揀選作業速度和降低揀選作業所需成本，研究主要集中在訂單分批、揀選路徑、倉儲布局和儲位規劃四個方面。訂單分批通過將多張訂單組合在一個批次，可以有效縮短揀選時間；合理規劃的揀選路徑可以快速完成訂單揀選任務、減少重復行走；倉儲布局決定了倉庫中貨架如何擺放，行走通道如何分布，影響著揀選路徑的行駛總距離；儲位規劃是將出入庫頻率高的貨物存放在倉庫入口附近，遵循上輕下重的原則。

目前，訂單揀選作業方式正從“人到貨”向“貨到人”方向發展。在傳統的“人到貨”揀選作業中，揀貨員推動揀貨小車進入倉庫的存儲區，根據訂單信息將所需商品揀選出來。“人到貨”訂單揀選作業方式需要大量的揀貨員，存在揀貨效率低、準確度低、人工成本高等問題。“貨到人”揀選作業通過AGV 小車或機器人等設備搬運移動貨架到揀選臺，揀貨員在揀選臺依據訂單信息對移動貨架中的商品進行揀選，提高了訂單揀選作業的效率和準確度，降低了人工成本，并且消除了“人到貨”訂單揀選模式對揀貨員工作經驗的高度依賴。在“貨到人”訂單揀選作業模式下，移動貨架搬運前需要根據訂單信息對訂單進行合理分批，減少貨架搬運次數，提高訂單揀選效率。因此，如何實現訂單分批是本文研究的重點。

總結相關文獻發現，國內外求解訂單分批的模型方法主要有兩種，第一種是求解以最小化貨架搬運次數為目標的訂單分批數學模型，第二種是求解以最大化訂單相似度為目標的訂單分批數學模型。張彩霞在“貨到人”模式下以AGV 小車搬運貨架的總次數最少為目標建立數學模型，通過節約算法對模型進行求解，與不分批的訂單搬運貨架次數相比提高了33%；徐冉建立了以貨架搬運次數最少為目標的訂單分批模型，使用相似性規則實現初始訂單分批，然后對初始訂單分批采用變鄰域搜索算法進行優化；秦馨以搬運貨架總次數最少為目標，通過設計遺傳算法對訂單分批進行求解，完成訂單揀選作業；王旭坪運用固定時間窗規則，同時考慮了相似度和訂單緊急程度等多個因素，構建數學模型進行求解；韋超豪對訂單分批優化使用了Canopy 算法和K-means 聚類算法來對訂單進行聚類，求解訂單分批結果；邵澤熠、董寶力構建了以訂單相似度最高為目標的分批揀選優化模型，并采用改進遺傳K-means 算法進行求解；馬廷偉、朱友瓊也根據訂單相似度建立訂單分批模型。

本文以貨架搬運總次數最少為目標建立數學模型，首先根據訂單之間的關聯性，最大化訂單間相似度并求解訂單分批模型，然后采用螢火蟲算法優化訂單初始分批結果，進而得到最終訂單分批求解結果。

1 問題描述

貨到人模式下的訂單分批問題可以描述為：倉庫中有X種商品，存儲在Y 個貨架上，每個貨架的儲位數量有S 個，儲位只能擺放一種商品。在離線狀態下，已知訂單信息和商品擺放在貨架的具體位置，如何對M 張訂單進行合理分批，才能使機器人搬運貨架次數最少。

為簡化問題，對貨到人訂單揀選作業模式下訂單分批問題作出下列假設：

（1）離線狀態下訂單信息均已知，如倉庫中訂單數量、商品種類、商品存儲在貨架的具體位置。

（2）單個訂單不可分割，每個訂單只允許存放在一個批次內。

（3）訂單所需商品不存在缺貨的情況。

（4）同一個貨架的每一層只存放一種商品，不同層可以存放不同商品。

（5）不存在緊急插單的情況。

（6）每個批次內所有的訂單數量不大于揀選臺周轉貨架的儲位數。

數學模型中參數和變量定義如表1 所示。

表1

2 訂單分批模型建立

為提高“貨到人”訂單揀選作業效率，將多個訂單進行分批處理，機器人依據訂單分批處理結果和已知的訂單信息將移動貨架搬運到揀選臺完成訂單揀選作業。以貨架搬運次數最少為目標建立訂單分批數學模型，首先按照最大化相似度對訂單進行分批，然后設計螢火蟲算法對初始訂單分批結果進行優化，減少貨架總搬運次數。

目標函數：最小化貨架搬運總次數：

約束條件：

決策變量：

公式（1）是訂單分批數學模型的目標函數，即最小化貨架總搬運的次數；公式（2）約束了每個訂單只能存放在一個批次內；公式（3）約束了每個批次內的貨架只能進行一次或零次搬運，不能重復搬運貨架；公式（4）約束了每個訂單批次內所包含的訂單數量，不允許超過揀選臺的儲位數P；公式（5）約束了每個訂單包含的商品種類不超過所屬批次含有的商品種類數；公式（6）至公式（8）是決策變量，取值都為0 或1，當取值為1 時，符合條件，公式（6）判斷訂單Z 是否被劃分到訂單批次N 中；公式（7）判斷訂單批次N 是否搬運貨架Y；公式（8）判斷訂單批次N 是否包含商品X。

3 基于訂單相似度的訂單分批求解

根據已知的訂單信息和商品擺放在貨架的具體位置，按照訂單相似度規則劃分多個訂單，將訂單相似度最大的訂單組合在同一個批次內實現訂單分批，多個訂單劃分在同一個批次，可以有效減少貨架所需搬運的次數。Xiang Xi 等（2018）提出了一種訂單相似度計算方法，本文也使用該計算方法：

訂單相似度O=每個訂單內部的相似度O1+兩個訂單之間的相似度O2

每個訂單內部的相似度是指訂單包含的商品在同一個貨架上的商品對數，兩個訂單之間的相似度是指將任意兩個訂單的商品組合在一起，計算在同一個貨架上的商品對數。

訂單相似度計算方法舉例說明：每個貨架可以存放五種商品，每個貨架按商品編號1-5，6-10，11-15，16-20……依次存放商品，有2 張訂單A={12,17,18,27}，B={11,13,26,28,30}，計算訂單A、B 的訂單相似度：O1={17,18}=1，O1={11,13}、{26,28}、{26,30}、{28,30}=4，O2={11,12}、{11,13}、{12,13}、{17,18}、{26,27}、{26,28}、{26,30}、{27,28}、{27,30}、{28,30}=10，O=O1+O1+O2=1+4+10=15。原本未分批時訂單A、B 需要搬運貨架為3+2=5 次，依據訂單相似度最大劃分為同一批次訂單后，需要搬運貨架3 次，減少了2 次貨架搬運。

將A={60,12,58,45,89}，B={56,97,47,59,33}，C={6,85,100,34}，D={24,91,21,10,7}，E={94,77,93,70}，F={92,95,90,68}6個訂單進行分批，通過計算訂單相似度可以分成3 批訂單n={A,B}，n={C,D}，n={E,F}，進行分批前貨架需要搬運貨架21次，分批后需要搬運貨架17 次，節約了4 次。分批過程如圖1 所示：

圖1 訂單分批過程

訂單相似度求解訂單分批問題的步驟：

Step1：根據已知的訂單信息，貨架的位置信息和揀選臺周轉貨架儲位數決定每個批次內包含訂單數量的最大限度；

Step2：計算所有訂單之間的相似度，構建訂單相似度矩陣；

Step3：找到訂單相似度矩陣中值最大對應的訂單m、m；

Step4：判斷m、m是否屬于已有訂單批次集合，如果是則將訂單m或m分別添加至對應的訂單批次中，否則將訂單m、m劃分為同一批次，構建新的訂單批次；

Step5：在構建訂單批次的同時要判斷是否滿足周轉貨架儲位數P 的限制，如果是則繼續添加新訂單，否則刪除超出限制的訂單，將被刪除的訂單構建成新的訂單批次；

Step6：返回，循環上述操作直至所有訂單都被劃分；

Step7：輸出所有訂單批次集合B。

4 基于螢火蟲算法的訂單分批求解

4.1 螢火蟲算法

螢火蟲算法屬于啟發式算法，為模擬螢火蟲在自然界中的發光特性而提出的群體智能優化算法。目前，螢火蟲算法主要有兩種，一種是在2005 年，印度學者K.N.Krishnanand 和D.Ghose 在IEEE 群體智能會議上提出了一種新的群智能優化算法，人工螢火蟲群優化算法（Glowworm Swarm Optimization,GSO）；另一種是在2009 年，劍橋學者Xin-She Yang 根據自然界中螢火蟲的發光行為提出螢火蟲算法（Firefly Algorithm,FA），兩種算法研究思路大體一致，但在實現方式上略有不同。本文采用第二種螢火蟲算法（FA），根據螢火蟲自身所特有的發光和吸引行為等生物特征設計了該算法，螢火蟲個體的亮度和吸引力決定了該螢火蟲的吸引行為，通常螢火蟲亮度由它所處位置的目標函數值決定，螢火蟲亮度越高，它所處的位置也就越好，目標函數值也相對較好，當某個螢火蟲比周圍其他螢火蟲更亮時，更容易吸引其他螢火蟲向自身移動，如果出現多個螢火蟲亮度相同的情況，則螢火蟲進行隨機移動。

為方便螢火蟲算法的實現，Yang Xin-She 提出了以下三條規則：

（1）所有螢火蟲個體不區分雌雄，任意一只螢火蟲都可能被其他螢火蟲所吸引。

（2）對于任意兩只螢火蟲，較亮的螢火蟲會吸引較暗的螢火蟲。如果所有螢火蟲亮度都相同，它們就會進行隨機移動。

（3）螢火蟲個體的亮度受目標函數值影響。

4.2 螢火蟲算法的相關數學定義：

定義1 螢火蟲的相對熒光亮度為：

其中：I是螢火蟲i 的絕對亮度；γ 是光強吸收因子；r是螢火蟲i 和j 之間的歐式距離。

定義2 螢火蟲之間的相對吸引力為：

其中：β為最大吸引力，是光源處，即r=0 時的吸引力，γ、r的意義同上。

定義3 螢火蟲j 被螢火蟲i 吸引，螢火蟲j 的位置更新為：

其中：t 為算法的迭代次數，X()代表螢火蟲j 在第t+1 次迭代的位置；β是螢火蟲i 對螢火蟲j 的吸引力；α 為常數，取α∈[0,1]；rand 是在[0,1]上服從均勻分布的隨機因子。

4.3 螢火蟲算法設計求解

訂單分批問題屬于NP-hard 問題，訂單數量越多，計算量會呈指數增長，對其求精確解十分困難，通常選擇啟發式算法對其進行求解。本文采用螢火蟲算法對訂單分批問題進行求解，得到優化的訂單分批結果。

4.3.1 螢火蟲算法的編碼

本文求解的問題是貨到人訂單揀選作業最小化貨架總搬運次數，結合螢火蟲個體的位置進行編碼求解該問題。建立個體位置與問題解之間的映射關系，采用實數編碼方式，隨機生成系統需要揀選的訂單和商品，使螢火蟲初始分布具有隨機性。

4.3.2 螢火蟲算法的解碼

螢火蟲算法的解碼是算法解空間轉變為實際問題解空間的過程，在解碼的同時要考慮揀選臺周轉貨架儲位數，即訂單批次中含有訂單數量的最大限度。每個螢火蟲的位置都是問題解空間的一個解，對螢火蟲位置進行解碼，計算目標函數值。

4.3.3 螢火蟲算法的個體亮度

訂單分批問題的目標是求解最小化問題，螢火蟲算法的發光亮度設計為每個螢火蟲個體對應的貨架搬運總次數的倒數。螢火蟲亮度的高低決定了所在位置的好壞，影響著螢火蟲個體的移動方向，螢火蟲個體之間的移動距離與吸引力有關，通過迭代更新亮度和吸引力來尋找訂單分批問題的最優解。

由公式（9）可知，螢火蟲個體的亮度與螢火蟲之間的距離有關，公式（10）中螢火蟲之間的距離采用歐式距離，為方便計算，螢火蟲個體之間的距離定義為計算同一位置上不同數字的總個數之和。舉例說明，如Z=[1,2,1,3,4,1,2,5]、Z=[1,2,3,3,4,1,3,5]，螢火蟲Z、Z之間的距離為R=2，數字不同的位置分別是3 和7。

4.3.4 螢火蟲算法的個體更新

（1）吸引移動

假設螢火蟲i 當前的位置為p，在鄰域范圍內，尋找更亮的螢火蟲j 并計算兩者之間的距離r，記錄所有比螢火蟲i 亮的螢火蟲，找到最亮螢火蟲k 后并朝著螢火蟲k 方向移動一步。在具體實現過程中，亮度較小的螢火蟲為了向更亮的方向移動，通過尋找兩個解中批次不一致的訂單號，按照更亮螢火蟲的解進行更新。

（2）隨機移動

對于鄰域范圍內最亮的螢火蟲k 進行隨機移動，隨機移動就是對不同批次內的兩個訂單進行隨機替換，避免陷入局部最優。舉例說明隨機移動：訂單批次 1={[1,23,5,7]、[2,4,16,8]、[13,6,9,12]}，訂單批次 2={[12,3,26,27]、[11,13,17,18]、[19,10,22,21]}，對訂單批次 1、2 的第2 個訂單進行交換得訂單批次 1={[1,23,5,7]、[11,13,17,18]、[13,6,9,12]}，訂單批次 2={[12,3,26,27]、[2,4,16,8]、[19,10,22,21]}。

4.3.5 螢火蟲算法的終止條件

本文終止條件是判斷是否達到最大迭代次數或存在更優的目標函數值，如果滿足終止條件，則輸出貨架搬運次數、分批批次和訂單批次內所包含的具體訂單，否則繼續迭代。

4.4 訂單分批的實現

螢火蟲算法求解步驟：

Step1：初始化算法參數。設置螢火蟲個體數目m，光強吸收因子γ，最大吸引力β，最大迭代次數max_gen。

Step2：初始化種群。螢火蟲算法的初始種群設置為最大化訂單相似度實現訂單分批的批次集合。

Step3：根據螢火蟲個體的位置信息計算螢火蟲的亮度，即目標函數值貨架搬運總次數。I是各個螢火蟲的最大發光亮度，將螢火蟲按照目標函數值進行排列，找到并記錄當前最優解f及其所在種群中的位置。

Step4：計算螢火蟲之間的距離和相對發光亮度，找到最亮的螢火蟲k,確定螢火蟲的移動方向。

Step5：計算螢火蟲的吸引力并更新螢火蟲的位置信息。

Step7：判斷當前最優解是否滿足揀選臺周轉貨架儲位數P 的限制，如果滿足則繼續執行下一步操作，否則刪除超出限制的訂單。

Step8：當滿足最大迭代次數后，轉Step9，否則轉Step3。

Step9：螢火蟲算法迭代完成，輸出最優解。

求解訂單分批問題的整體流程圖如圖2 所示。

圖2 求解訂單分批模型流程圖

5 實驗結果分析

在Matlab 軟件上進行多組仿真實驗，驗證采用訂單相似度和螢火蟲算法實現訂單分批問題的有效性和可行性。

5.1 實驗參數設置

根據倉庫訂單揀選系統實驗環境設置參數，如表2 所示：

表2

訂單分批實驗可以描述為：在擁有60 個貨架、300 種商品的訂單揀選倉庫中，商品按照1-5，6-10，11-15，16-20，…,56-60 的順序依次存放在60 個貨架上，若干個機器人對移動貨架進行搬運實現訂單分批。現在需要對40 個訂單進行分批，完成揀選作業的訂單分批任務。

5.2 訂單分批模型求解

5.2.1 訂單批次劃分結果

以訂單相似度為劃分依據，建立最小化貨架搬運總次數為目標的數學模型。40 批訂單可以劃分成5 批，貨架搬運次數為69 次；按照原始訂單進行揀選，貨架搬運總次數為160次；與按單揀選搬運貨架總次數相比，優化了56.8%。由于揀選臺處周轉貨架個數為10，所以劃分批次內所含訂單的最大數量為10，批次內所含訂單個數最少為1。為減少貨架搬運總次數，訂單批次內訂單數量越多，訂單分批批次數量越少，從而減少貨架搬運次數。

在Matlab 軟件上按照訂單相似度最大實現訂單分批實驗結果如圖3、表3 所示。

表3 訂單分批結果

圖3 訂單相似度方法實現40 個訂單的分批

采用螢火蟲算法對訂單相似度分批結果進行優化，40 個訂單劃分為4 批，優化后貨架搬運總次數為64 次。與初始狀態貨架搬運次數160 次比較，螢火蟲算法優化了60%，與按照訂單相似度劃分實現訂單分批相比，減少了5 次貨架的搬運，優化了7.2%。

在Matlab 上采用螢火蟲算法優化訂單分批實驗結果如圖4、表4 所示。

表4 優化后訂單分批結果

圖4 螢火蟲算法實現40 個訂單的分批

5.2.2 訂單揀選系統參數影響與效果分析

（1）訂單數量對貨架搬運次數的影響

電商行業每天面對的訂單數量具有波動性，訂單揀選系統每天需要處理不同數量的訂單，為了驗證所提方法的有效性，繼續對20 個、40 個、100 個訂單分別進行分批。

分析比較在20、40、100 個訂單按照三種揀選方式實現訂單分批所需貨架搬運次數，如圖5 所示。

通過圖5 可以發現，隨著訂單數量的增加，按單揀選、按訂單相似度揀選和螢火蟲算法揀選實現訂單分批所需搬運的貨架次數逐步提升；訂單數量分別為20、40、100 時，與按單揀選搬運貨架次數相比，以訂單相似度為劃分依據實現訂單分批分別優化了53%、56.8%、55.5%，螢火蟲算法優化實現訂單分批都優化了約60%。發現訂單量從20 到40 之間，優化效率逐步提升，當達到100 時，優化率反而下降了，即當訂單量達到合適值時，可以達到優化效果最大化，提高“貨到人”訂單揀選作業效率。

圖5 不同訂單數量之間分析對比圖

（2）揀選臺處周轉貨架數量對貨架搬運次數的影響

揀選臺處周轉貨架數量決定了訂單批次中包含訂單數量的最大限度，將越多的訂單劃分在同一批次可以減少貨架的重復搬運，所以揀選臺處周轉貨架的數量影響著批次劃分后機器人搬運貨架的次數。為了驗證所提模型的有效性，分別在10、15、30 個周轉貨架上進行實驗，對比分析不同周轉貨架數量所需的貨架搬運次數，尋找二者之間的關系。

如圖6 所示，分別比較使用10、15、30 個周轉貨架個數對實現訂單分批貨架搬運次數的影響。

圖6 不同周轉貨架數量之間分析對比圖

整體來說，在一定的范圍內，隨著周轉貨架數的增加，貨架搬運次數逐漸減少，若超出某一閾值，貨架搬運次數優化效果反而不好。如周轉貨架數增加到30 個時，與訂單相似度所需搬運貨架次數相比，螢火蟲算法優化后貨架搬運次數反而增加，不僅增加了設備成本，還降低了訂單分批作業的效率。因此，合適的周轉貨架數量對于提高“貨到人”訂單揀選作業效率和準確度十分重要。

6 結論

本文研究了關于“貨到人”訂單揀選作業的訂單分批問題，合理有效的訂單分批可以提高訂單揀選作業的效率，通過將多張訂單合并在一個批次內進行揀選，可以減少貨架搬運總次數。以最小化貨架搬運總次數為目標，建立訂單分批數學模型，首先考慮訂單之間的關聯性，以訂單相似度最大為分批依據實現訂單分批，與按單揀選貨架搬運總次數相比優化率可達53%～57%，然后對訂單相似度實現的分批結果進行再優化，采用螢火蟲算法優化訂單批次，與初始貨架搬運次數相比提高了60%，效果十分明顯。經過在Matlab 軟件上進行多組數值實驗，驗證了所提模型的可行性和設計算法的有效性。在以后的工作中，可以考慮與機器人揀選路徑的聯合優化來提高訂單揀選作業的效率和準確性。