“貨到人”揀選系統在現代化的電商物流自動倉庫中的運用日益廣泛,其揀選效率較人工倉更具優勢,但長期經營發現,其揀選成本也更高。根據相關調查發現,影響揀選成本的主要因素就是機器人的有效工作率,即搬運貨架行走時間與機器人總運行時間的比值。所以,如何通過優化訂單揀選順序來減少機器人的排隊等候時間,提升其有效工作率,成了“貨到人”揀選系統提升揀選效率亟待解決的問題。
目前,與電商物流倉儲揀選作業有關的研究主要集中于揀貨路徑優化和訂單分配方面。于浩洋 (2019) 采用遺傳算法求解人工揀貨方式的電子商務配送中心的揀選路徑優化問題,結果證實路徑優化后能有效地減少實際行走路徑[1]。胡金昌 (2016) 研究了基于改進K-Means算法的“貨到人”揀選系統中多層穿梭車分揀系統的訂單分配策略,得出聚類比不聚類訂單分配策略平均能減少料箱出入庫次數40%以上的結論[2]。王迪 (2018) 系統地將訂單分批、批次分配和排序與揀選路徑聯合起來分析,并建立混合整數規劃模型求解[3]。吳穎穎等 (2016) 針對“貨到人”揀選系統的訂單排序優化問題,以訂單耦合因子為模型參數,提出改進的K-Means聚類算法對揀選系統訂單排序進行優化,結果表明訂單排序優化后揀選效率提高15.9%[4]。建立訂單排序優化模型時多以訂單處理時間為目標函數,張貽弓等 (2008) 以總揀選時間最短為目標函數,應用最大最小蟻群算法求解模型[5]。
通過文獻綜述可知,對電商物流倉儲揀選作業的研究已有較為全面的理論和方法探索,但多數研究僅限于對“人到貨”模式下訂單揀選路徑及訂單分批進行優化,少數針對“貨到人”模式下揀選優化也是以總路徑最短或總揀選時間最短為目標函數,這兩個目標更多強調的是整體最優對實際工作的指導意義有限。本文基于“貨到人”揀選系統,將機器人搬運貨架次數最少作為目標函數,以節約算法的思想計算訂單之間的耦合度,根據耦合度采用K-Means聚類算法對訂單排序進行優化,減少機器人無效工作時間,具體指導實際工作,進一步提升揀選效率。
K-Means聚類是一種動態聚類的算法,它是給出一個初始的聚類結果,即把所有數據分成K類,然后通過一定的方法,完善優化此聚類結果,不斷迭代,最后得出一個最優結果[6]。它具有快速、簡單,對大數據集聚類有較高的效率并且具有可伸縮性,且時間復雜度近于線性,適合挖掘大規模數據集等優點。
電子商務物流的訂單具有較強的動態波動性,而對于這種有大量變體的多簇聚類問題,K-Means聚類算法具有較好的適應性。
在電商物流倉儲揀選過程中,由于系統給同時進行揀選作業的波次安排的貨架揀選次序缺乏合理性,所以當出現多個揀選站臺某一時刻均需要某一個貨架進行揀選作業時,后揀選該貨架的揀選站臺會產生大量等待時間,這是造成揀選效率低下,揀選成本過高的重要原因。根據文獻調研發現,在對訂單進行合理分批之后能有效減少貨架的搬運次數。因此,需制定更為合理的貨架揀選次序,來優化機器人的排隊次序,最終提高系統的揀選效率,降低揀選成本。
實際生產中存在多種復雜因素影響優化效果,為保證模型的可行性和正確性,做出以下假設: (1) 一種商品對應一個貨架的一個儲位; (2) 一個訂單至少包含一個品項; (3) 同一訂單不允許分割; (4) 搬運過程中不存在堵塞情況; (5) 搬運過程中機器人電量充足; (6) 機器人運行速度一致; (7) 不考慮缺貨和緊急插單等情況。
為了更簡便地描述訂單排序過程,對相關參數定義及符號說明表示如下。
N:訂單品項所包含的總貨架數,N=1, 2, 3,…,n;
P:訂單分批得到的總批次數,P=1, 2, 3,…,p, q;
t:揀選站臺序數,t=1, 2, 3,…s;
K:揀選次序,K=1, 2, 3…,k;
γαks:波次α被分配至第s個揀選站臺且揀選次序為k, a=1, 2, 3…, q;
γpks:每個波次被分配至一個揀選站臺,且在該揀選站臺有唯一的揀選次序。
假設系統中每個揀選站臺最多觸發5個移動貨架的揀選任務,當一個貨架正在揀選時,其余的貨架依次排隊等候揀選,等候揀選的貨架數量稱為緩存容量。本文根據波次單的耦合度來進行劃分波次單,將耦合度大的波次分配在同一個揀選站臺,將波次單的排隊順序轉化為貨架搬運次數的問題,把相似度高的波次安排在相鄰的揀選次序上,以貨架搬運次數來量化波次單的排隊優化程度,即以節約貨架搬運次數最多為目標函數建立數學模型。
當第p個波次和第q個波次的耦合因子較大,兩者放置于揀選緩存區上的共需貨箱較多。如果將p、q分配至一個揀選站臺且揀選次序先后排列,即先揀選波次p,揀選完成后立即揀選波次q。則當兩者有共需的貨架時,完成波次p的揀選任務后,共需貨架進入緩存區等待波次q的揀貨,可避免重復出入拆零區,有效減少機器人進出拆零區次數,提高移動貨架準時到達率,減少機器人的搬運時間和搬運距離。
目標函數
約束條件
其中:目標函數 (1) 表示所有波次揀選完節約的貨架搬運次數最大,約束條件 (2) 表示波次α是否被分配至第s個揀選站臺以及揀選次序是否為k。如果是,取值為1,否取值為0; (3) 表示每個波次被分配至一個揀選站臺,且在該揀選站臺有唯一的揀選次序; (4) 表示每個揀選次序僅包含一個波次。
節約算法的提出是為了解決運輸問題,根據客戶的地理位置以及客戶和客戶之間的距離,通過將兩個或兩個以上的客戶合并同時配送,來計算節約的運輸里程,從而找出節約里程最多的客戶合并方式[6]。在安排波次單的揀選順序時可以運用節約算法的思想,根據不同訂單需要搬運的共同貨架數,計算兩兩揀選波次的耦合度對波次單進行初步排序。
將按耦合度排序得到的波次單運用K-Means聚類算法求解波次單揀選順序,算法步驟如下:
(1) 計算兩兩波次單的耦合度,并按耦合度大小降序排序,Np1≥Np2≥Np3≥Np4≥…≥Np (P-1) 。
(2) 為每個揀選站臺隨機設置初始波次單作為聚類中心點。
(3) 搜索揀選站臺S中揀選順序為k的波次p,并比較其他未被分配的波次q之間的耦合度Npq的大小,選擇Npq最大的波次q,將其分配至p波次之后揀選。
(4) 不斷重復步驟 (3) ,直至所有訂單分配完畢。
在MATLAB中隨機生成揀選站臺和波次單來進行仿真驗證,每個揀選站臺的緩存容量都為4。通過不斷變換波次單的數量,來計算機器人搬運貨架的次數。
對波次單排序優化前后的出入庫次數進行對比分析。分別以兩種情況進行分析: (1) 波次單順序揀選; (2) 波次單排序優化。隨著波次單數量不斷增加,兩種情況下三組數據的移動貨架搬運次數如圖1所示。隨著波次單數量的增加三組數據采用波次單排序優化后,移動貨架的搬運次數均有效減少。
分別以揀選18、30、42個波次單為例,作為數據一、數據二、數據三,在MATLAB中進行仿真,得到最終需要的移動貨架搬運次數如表1所示。
表1 移動貨架搬運次數對比表 下載原表
三組數據在波次單排序優化后移動貨架搬運次數優化程度與按順序揀選相比分別優化了20.8%、23.4%、25.8%。由于數據是系統隨機生成,揀選每個波次單所需的移動貨架可能分布較廣,導致不同波次單之間的耦合度較實際數據而言更小。所以實際生產中其優化程度隨波次單數量的增加會更明顯。
通過上述仿真驗證結果,對分批的訂單按照改進K-Means聚類算法進行訂單揀選排序后,能夠有效減少機器人搬運貨架次數,與不進行排序優化相比,搬運貨架次數減少了20%-30%,同時減少機器人無效工作時間,達到了提升揀選效率,降低揀選成本的目的。
綜上,通過把波次單的排隊順序轉化為貨架搬運次數的問題,以貨架搬運次數最少為目標函數,利用節約算法的思想對K-Means聚類算法進行改進后,應用于電商物流倉儲揀選作業的訂單分批波次單揀選排序優化,建立數學模型并求解,根據仿真結果,驗證了運用改進k-means聚類算法使機器人搬運貨架次數得到有效減少,提升了揀選效率,降低了揀選成本。
上一篇: 德邦物流倉儲管理發展的問題與對策研究
下一篇: 信息化技術在物流倉儲管理方面的應用