□ 朱友瓊，唐 思

(西南科技大學 經(jīng)濟管理學院，四川 綿陽 621010)

1 引言

目前，與電商物流倉儲揀選作業(yè)有關的研究主要集中于揀貨路徑優(yōu)化和訂單分配方面。于浩洋(2019)采用遺傳算法求解人工揀貨方式的電子商務配送中心的揀選路徑優(yōu)化問題，結果證實路徑優(yōu)化后能有效地減少實際行走路徑[1]。胡金昌(2016)研究了基于改進K-Means算法的“貨到人”揀選系統(tǒng)中多層穿梭車分揀系統(tǒng)的訂單分配策略，得出聚類比不聚類訂單分配策略平均能減少料箱出入庫次數(shù)40%以上的結論[2]。王迪(2018)系統(tǒng)地將訂單分批、批次分配和排序與揀選路徑聯(lián)合起來分析，并建立混合整數(shù)規(guī)劃模型求解[3]。吳穎穎等(2016)針對“貨到人”揀選系統(tǒng)的訂單排序優(yōu)化問題，以訂單耦合因子為模型參數(shù)，提出改進的K-Means聚類算法對揀選系統(tǒng)訂單排序進行優(yōu)化，結果表明訂單排序優(yōu)化后揀選效率提高15.9%[4]。建立訂單排序優(yōu)化模型時多以訂單處理時間為目標函數(shù)，張貽弓等(2008)以總揀選時間最短為目標函數(shù)，應用最大最小蟻群算法求解模型[5]。

通過文獻綜述可知，對電商物流倉儲揀選作業(yè)的研究已有較為全面的理論和方法探索，但多數(shù)研究僅限于對“人到貨”模式下訂單揀選路徑及訂單分批進行優(yōu)化，少數(shù)針對“貨到人”模式下揀選優(yōu)化也是以總路徑最短或總揀選時間最短為目標函數(shù)，這兩個目標更多強調(diào)的是整體最優(yōu)對實際工作的指導意義有限。本文基于“貨到人”揀選系統(tǒng)，將機器人搬運貨架次數(shù)最少作為目標函數(shù)，以節(jié)約算法的思想計算訂單之間的耦合度，根據(jù)耦合度采用K-Means聚類算法對訂單排序進行優(yōu)化，減少機器人無效工作時間，具體指導實際工作，進一步提升揀選效率。

2 問題描述與模型構建

2.1 K-Means聚類算法特點

K-Means聚類是一種動態(tài)聚類的算法，它是給出一個初始的聚類結果，即把所有數(shù)據(jù)分成K類，然后通過一定的方法，完善優(yōu)化此聚類結果，不斷迭代，最后得出一個最優(yōu)結果[6]。它具有快速、簡單，對大數(shù)據(jù)集聚類有較高的效率并且具有可伸縮性，且時間復雜度近于線性，適合挖掘大規(guī)模數(shù)據(jù)集等優(yōu)點。

電子商務物流的訂單具有較強的動態(tài)波動性，而對于這種有大量變體的多簇聚類問題，K-Means聚類算法具有較好的適應性。

2.2 問題描述

在電商物流倉儲揀選過程中，由于系統(tǒng)給同時進行揀選作業(yè)的波次安排的貨架揀選次序缺乏合理性，所以當出現(xiàn)多個揀選站臺某一時刻均需要某一個貨架進行揀選作業(yè)時，后揀選該貨架的揀選站臺會產(chǎn)生大量等待時間，這是造成揀選效率低下，揀選成本過高的重要原因。根據(jù)文獻調(diào)研發(fā)現(xiàn)，在對訂單進行合理分批之后能有效減少貨架的搬運次數(shù)。因此，需制定更為合理的貨架揀選次序，來優(yōu)化機器人的排隊次序，最終提高系統(tǒng)的揀選效率，降低揀選成本。

2.3 模型假設與參數(shù)定義

2.3.1 模型假設

在課堂教學中，教師只有把學生的學習情緒調(diào)動起來，才能構建良好的課堂氣氛，才能使學生在認知的過程中產(chǎn)生愉悅感，并激起和發(fā)展他們的智力?，F(xiàn)代教育理論認為，只有良好的教學策略，才能達到良好的教學效果。而如何調(diào)動學生的學習情緒，對教師而言，是具有藝術性的教學策略。

實際生產(chǎn)中存在多種復雜因素影響優(yōu)化效果，為保證模型的可行性和正確性，做出以下假設：①一種商品對應一個貨架的一個儲位；②一個訂單至少包含一個品項；③同一訂單不允許分割；④搬運過程中不存在堵塞情況；⑤搬運過程中機器人電量充足；⑥機器人運行速度一致；⑦不考慮缺貨和緊急插單等情況。

2.3.2 參數(shù)定義

為了更簡便地描述訂單排序過程，對相關參數(shù)定義及符號說明表示如下。

N:訂單品項所包含的總貨架數(shù)，N=1,2,3,…,n；

P:訂單分批得到的總批次數(shù)，P=1,2,3,…,p,q；

t:揀選站臺序數(shù)，t=1,2,3,…s；

K:揀選次序，K=1,2,3…,k；

γαks:波次α被分配至第s個揀選站臺且揀選次序為k，a=1,2,3…,q；

γpks:每個波次被分配至一個揀選站臺，且在該揀選站臺有唯一的揀選次序。

2.4 模型構建

假設系統(tǒng)中每個揀選站臺最多觸發(fā)5個移動貨架的揀選任務，當一個貨架正在揀選時，其余的貨架依次排隊等候揀選，等候揀選的貨架數(shù)量稱為緩存容量。本文根據(jù)波次單的耦合度來進行劃分波次單，將耦合度大的波次分配在同一個揀選站臺，將波次單的排隊順序轉(zhuǎn)化為貨架搬運次數(shù)的問題，把相似度高的波次安排在相鄰的揀選次序上，以貨架搬運次數(shù)來量化波次單的排隊優(yōu)化程度，即以節(jié)約貨架搬運次數(shù)最多為目標函數(shù)建立數(shù)學模型。

當?shù)趐個波次和第q個波次的耦合因子較大，兩者放置于揀選緩存區(qū)上的共需貨箱較多。如果將p、q分配至一個揀選站臺且揀選次序先后排列，即先揀選波次p，揀選完成后立即揀選波次q。則當兩者有共需的貨架時，完成波次p的揀選任務后，共需貨架進入緩存區(qū)等待波次q的揀貨，可避免重復出入拆零區(qū)，有效減少機器人進出拆零區(qū)次數(shù)，提高移動貨架準時到達率，減少機器人的搬運時間和搬運距離。

目標函數(shù)

(1)

約束條件

其中：目標函數(shù)(1)表示所有波次揀選完節(jié)約的貨架搬運次數(shù)最大，約束條件(2)表示波次α是否被分配至第s個揀選站臺以及揀選次序是否為k。如果是，取值為1，否取值為0；(3)表示每個波次被分配至一個揀選站臺，且在該揀選站臺有唯一的揀選次序；(4)表示每個揀選次序僅包含一個波次。

3 基于節(jié)約算法的改進K-Means聚類

3.1 節(jié)約算法

節(jié)約算法的提出是為了解決運輸問題，根據(jù)客戶的地理位置以及客戶和客戶之間的距離，通過將兩個或兩個以上的客戶合并同時配送，來計算節(jié)約的運輸里程，從而找出節(jié)約里程最多的客戶合并方式[6]。在安排波次單的揀選順序時可以運用節(jié)約算法的思想，根據(jù)不同訂單需要搬運的共同貨架數(shù)，計算兩兩揀選波次的耦合度對波次單進行初步排序。

3.2 改進 K-Means聚類算法

將按耦合度排序得到的波次單運用K-Means聚類算法求解波次單揀選順序，算法步驟如下：

①計算兩兩波次單的耦合度，并按耦合度大小降序排序，Np1≥Np2≥Np3≥Np4≥…≥Np(P-1)。

②為每個揀選站臺隨機設置初始波次單作為聚類中心點。

③搜索揀選站臺S中揀選順序為k的波次p，并比較其他未被分配的波次q之間的耦合度Npq的大小，選擇Npq最大的波次q，將其分配至p波次之后揀選。

④不斷重復步驟(3)，直至所有訂單分配完畢。

4 仿真驗證

4.1 實驗過程

在MATLAB中隨機生成揀選站臺和波次單來進行仿真驗證，每個揀選站臺的緩存容量都為4。通過不斷變換波次單的數(shù)量，來計算機器人搬運貨架的次數(shù)。

圖1 排序揀選和順序揀選仿真結果

對波次單排序優(yōu)化前后的出入庫次數(shù)進行對比分析。分別以兩種情況進行分析：①波次單順序揀選；②波次單排序優(yōu)化。隨著波次單數(shù)量不斷增加，兩種情況下三組數(shù)據(jù)的移動貨架搬運次數(shù)如圖1所示。隨著波次單數(shù)量的增加三組數(shù)據(jù)采用波次單排序優(yōu)化后，移動貨架的搬運次數(shù)均有效減少。

4.2 優(yōu)化效果對比

分別以揀選18、30、42個波次單為例，作為數(shù)據(jù)一、數(shù)據(jù)二、數(shù)據(jù)三，在MATLAB中進行仿真，得到最終需要的移動貨架搬運次數(shù)如表1所示。

表1 移動貨架搬運次數(shù)對比表

三組數(shù)據(jù)在波次單排序優(yōu)化后移動貨架搬運次數(shù)優(yōu)化程度與按順序揀選相比分別優(yōu)化了20.8%、23.4%、25.8%。由于數(shù)據(jù)是系統(tǒng)隨機生成，揀選每個波次單所需的移動貨架可能分布較廣，導致不同波次單之間的耦合度較實際數(shù)據(jù)而言更小。所以實際生產(chǎn)中其優(yōu)化程度隨波次單數(shù)量的增加會更明顯。

4.3 結果分析

通過上述仿真驗證結果，對分批的訂單按照改進K-Means聚類算法進行訂單揀選排序后，能夠有效減少機器人搬運貨架次數(shù)，與不進行排序優(yōu)化相比，搬運貨架次數(shù)減少了20%-30%，同時減少機器人無效工作時間，達到了提升揀選效率，降低揀選成本的目的。

5 結論

綜上，通過把波次單的排隊順序轉(zhuǎn)化為貨架搬運次數(shù)的問題，以貨架搬運次數(shù)最少為目標函數(shù)，利用節(jié)約算法的思想對K-Means聚類算法進行改進后，應用于電商物流倉儲揀選作業(yè)的訂單分批波次單揀選排序優(yōu)化，建立數(shù)學模型并求解，根據(jù)仿真結果，驗證了運用改進k-means聚類算法使機器人搬運貨架次數(shù)得到有效減少，提升了揀選效率，降低了揀選成本。