貨到人系統揀選訂單分批處理策略問題研究

范繼東

（南京醫藥股份有限公司，江蘇 南京 210000）

1 引言

隨著拆零比例的持續上升，如何解決醫藥流通行業的拆零揀選問題成為主要問題。“貨到人”系統由于能夠降低勞動強度、提升人員作業效率，作為新型揀選方式正在日益為各家醫藥流通企業所重視，多層穿梭車系統作為其中典型的代表，由于其存儲密度大、揀選效率高等特點，正為各家醫藥流通企業所采用。多層穿梭車系統在應對大量訂單的情況下，巷道端頭的料箱提升機成為影響整個系統效率的瓶頸點之一。本文針對多層穿梭車系統中“貨到人”揀選系統中如何利用訂單揀選分批策略，實現整體效率提升的問題，提出了基于k-means算法的細分批算法，以最小化貨箱總出入庫次數為目標，建立了考慮分批結果聚類程度的訂單分批數學模型，實現可控聚類程度的訂單分批，在同樣的業務情況下，有效的降低了“貨到人”揀選系統對提升機作業效率的要求。

2 問題分析

訂單揀選是影響物流配送中心作業效率的重要因素。在“貨到人”揀選系統中，貨箱出入庫頻率是影響揀選效率的關鍵因素，當出入庫較頻繁時，對設備的性能要求較高，設備難以滿足要求或成本較高。因此，降低貨箱出入庫頻率是影響揀選效率的重要因素。

訂單分批是把多張訂單集合成一批，進行批次揀選作業。通過訂單分批，可以把相似度高的訂單合并在同一批次中，這樣相當于把每批次訂單中的同一商品品項匯總后，再分配到每一個顧客訂單，可以有效的降低貨箱的出入庫次數，提高揀選效率。對于訂單分批問題，常見的有三種分批方法：

（1）按時間窗分批：首先固定一個時間長度，從某個時間點開始，將該時間窗長度內到達的訂單分到同一個批次。

（2）固定訂單量分批：固定一個訂單批量，將按照先后順序到達的訂單一次分到該批次，直到達到容量限制，開始下一個批次的分批。

（3）智能型分批：根據待分批訂單的結構特點、使用特點的算法對訂單揀選合理分批。

前兩種方法屬于先到先服務的方式，沒法降低訂單對提升機的作業要求，所以本文采用智能算法進行訂單分批。當待分批訂單的數量很大時，由于現有智能分批算法的計算復雜度較高，會導致求解訂單分批結果的時間過長，增加揀選等待時間，有必要設計一種低復雜度的算法，用于大批量訂單的分批，在計算速度較快的前提下實現大批量訂單到小批量訂單的轉換。此外，揀選效率和訂單的聚類程度不一定成正比。在醫藥揀選中，根據GSP的要求，必須對藥品進行批號批次管理，在確定訂單分批后，將貨箱出庫到揀選臺進行揀選，由于同一批次中的訂單相似度較高，同一批次中的某個藥品原料箱有可能被多個訂單需要，就會造成分揀時很多揀選臺都在等待某個原料箱的情況，從而導致揀選等待時間過長。所以并非聚類程度越高，總揀選時間越短，還要考慮訂單分批的聚類程度對后續揀選臺揀選時間的影響。

WANGY[1]針對多層穿梭車倉儲系統的任務調度問題，根據穿梭車和升降機的運動特性，建立了任務調度的時序數學模型，將穿梭車和升降機之間的任務調度問題轉換為裝配線并行作業問題，并用改進的遺傳算法求解，可以減少總升降機空閑時間和總穿梭車等待時間。吳穎穎[2]為了解決揀選訂單排序問題，定義訂單耦合因子表示兩個訂單之間可放置于揀選緩存中的共用貨箱數量，并以此作為模型參數，以降低貨箱出入庫頻率為優化目標，建立訂單排序優化模型，并提出改進的K-Means聚類算法求解模型。寧方華[3]研究了“貨到人”作業模式下魚骨型布局中的貨位優化問題，按品項的訂購頻次和相關性劃分品項簇，將相關性強且訂購頻次高的品項簇存儲于一個貨架，并以最小化揀選路程為目標建立數學模型；然后設計TS_SC算法求解貨位優化模型，將相關性強的貨架就近存放，從而減少貨架搬運次數，縮短揀選路程，提高作業效率。馬文凱[4]研究了跨巷道多層穿梭車倉儲系統的最優配置問題，綜合考慮客戶對分揀系統的需求以及跨巷道多層穿梭車倉儲系統自身的特點，通過分析系統的配置優化模型，提出啟發式算法，求解使成本最小的系統最優配置，總結歸納出系統配置對系統性能的影響規律。

現有的研究在設計訂單分批算法時，并沒有針對醫藥批號批次管理的要求，考慮聚類程度的影響問題。本文在設計訂單分批算法時，將提出聚類程度指數的概念來衡量訂單分批的聚類程度，兼顧了藥品批號批次管理要求對揀選作業的特殊要求，同時考慮控制聚類程度的訂單分批。

3 模型建立

3.1 模型假設

為了建模的方便，對要研究的“貨到人”揀選系統做了如下假設：

（1）所有訂單的揀選信息在分批前已知；

（2）一個訂單至少包含一個物品；

（3）一個訂單只能被分在一個批次中，不允許分割；

（4）一個原料箱在同一個批次中只能出庫一次；

（5）不考慮缺貨和補貨的情況。

3.2 符號說明

本模型所使用的符號具體含義如下：

N—訂單總數；

On—第n個訂單（n=1,2,...,N）；

K—倉庫中所有品項的種類總數；

M—單個訂單的訂單行上限；

B—訂單總共劃分的批次數（b=1,2,...,B）；

C—每個批次的容量限制；

mn—第n個訂單含有的品項數目（n=1,2,...,N）；

sij—訂單Oi和Oj中相同品項的數量（i,j=1,2,...,N）；

T—貨箱總出入庫次數；

ρb—聚類程度指數；

λ—聚類程度閾值；

Ub—第b批訂單中出現頻率大于1次的所有品項的集合；

3.3 模型數學表達

根據上述問題分析，可以建立如下數學模型：目標函數：

約束條件：

上述模型中，式（1）為目標函數，表示所有貨箱的總出入庫次數最小，總出入庫次數T為所有訂單的品項次和訂單分批所節省的出入庫次數的差值；式（2）約束每個訂單只能分到1個批次中；式（3）為容量約束，表示一個批次的訂單總數不能超過批次的訂單容量限制，式（4）為取值約束，表示決策變量的取值為布爾型，式（5）為聚類程度約束，表示聚類程度指數要滿足設定的閾值條件，式（6）為聚類程度指數的定義，ρb表示第b批訂單中所有品項的重復出現次數和第b批訂單中出現的全部品項次的比值。

3.4 基于k-means的訂單細分批算法

針對上述訂單分批數學模型，設計了基于kmeans算法的改進算法，流程如圖1所示。該算法實現了變聚類中心的訂單分批，其大體思路是：基于訂單之間的相似度進行訂單的合批，每次加入一個訂單后都要對聚類中心進行更新，重新計算相似度來選出其他訂單；針對模型中的聚類程度限制，算法設計了反饋調整，會根據聚類程度限制來改變選擇訂單的優先級，從而改變分批結果的聚類程度。算法的具體步驟如下：

（1）計算所有訂單兩兩之間相同品項的數目sij，構成初始的訂單相似矩陣S0。

（2）將相似矩陣中未分批訂單間的相似度取值按從大到小非重復降序排列。

（3）選擇最大相似度值對應的兩個訂單組合作為聚類的初始訂單批量。

（4）以這兩個初始訂單的組合訂單為基準，比較合并訂單與其他訂單的相似度，得到新的訂單相似矩陣，選擇相似度取值最大的訂單劃入該批次。

（5）重復步驟（4），直到該批次的訂單數達到容量限制，則已得到該批次的初步分批結果。

（6）計算該批次的聚類程度指數ρb，判斷ρb＜λ是否成立，若滿足條件則保留該批次分批結果，同時將該批次的訂單從原始訂單集中剔除，跳轉到步驟（7）；否則重新對該批次進行分批：假設是第i次迭代，則回到步驟（3），選擇排在第i個位置的相似度值，將其對應的兩個訂單組合作為聚類的初始訂單批量，依次計算下去。

（7）得到更新后的未分批訂單集，跳轉到步驟（2），不斷的重復整個過程，直到所有的訂單都完成分批。

4 仿真實驗與結果分析

通過設計仿真實驗，利用MATLAB 仿真軟件編程，對本文提出的兩種訂單分批算法進行分析，仿真環境為MATLAB 2015b，Windows 10操作系統，DELL Inspiron 15，Intel i5-5200U CPU 2.2GHz，4GB RAM。

圖1 細分批算法流程圖

4.1 細分批算法仿真分析

（1）模型參數設置。K=500；N=160，320，480，640，800；M=5；C=16；λ=1（相當于不考慮聚類程度約束）

（2）仿真結果及分析。在MATLAB 中隨機生成訂單數據，將本文的細分批算法與傳統的先到先服務算法（FCFS）進行比較，計算兩種算法在5 種不同訂單批量（N=160，320，480，640，800）下的貨箱出入庫次數，結果見表1。

表1 細分批算法和FCFS算法仿真結果

表1中是5 種不同訂單批量下細分批算法和FCFS 算法求得的貨箱出入庫次數，從表中數據不難看出，本文的細分批算法相比傳統FCFS算法可以有效地降低貨箱出入庫次數，相應的仿真圖如圖2所示。

從圖2中可以看出，在相同訂單數據的情況下，細分批算法的貨箱總出入庫次數總是少于FCFS 算法，且訂單批量越大優勢越明顯，驗證了本文采用的分批算法相比傳統FCFS算法的有效性。

4.2 細分批算法聚類程度約束仿真分析

（1）模型參數設置。K=500；N=160，320，480，640，800；M=5；C=16；λ=1，0.8，0.7，0.6。

（2）仿真結果及分析。本次仿真基于細分批算法，考慮改變聚類程度閾值λ對分批結果的影響，同時記錄每個批次的聚類程度指數和計算的迭代次數，具體結果如下：

①當λ=1 時，由于聚類程度指數的上限為1，所以結果的聚類程度指數永遠不會超過1，相當于在沒有聚類程度限制的前提下求解模型。這種情況下求得的貨箱總出入庫次數=387，詳細結果見表2。

圖2 細分批算法和FCFS算法仿真結果對比圖

表2 細分批算法運行結果（λ=1）

②當λ=0.8 時，貨箱的總出入庫次數=451，詳細結果見表3。

表3 細分批算法運行結果（λ=0.8）

③當λ=0.7 時，貨箱的總出入庫次數=497，詳細結果見表4。

表4 細分批算法運行結果（λ=0.7）

④當λ=0.6 時，由于聚類程度指數過低，所以沒有符合條件的分批結果。

分析上述結果可知，隨著聚類程度指數的降低，貨箱的總出入庫次數增加，這和實際情況是相符合的。同時，聚類程度指數不能無限降低，其下限值和具體的訂單數據有關系。在實際應用中，應該通過綜合分析整個訂單揀選過程，確定最佳的聚類程度指數，作為聚類程度閾值。

5 結論

本文通過設計的基于K-means 的細分批算法，在中小批量訂單的前提下，通過比較細分批算法和傳統FCFS算法的結果，證明了細分批算法相比傳統FCFS算法的有效性；同時考慮聚類程度的限制，分析細分批算法在不同聚類程度閾值時的分批結果，證明該算法可以實現可控聚類程度的訂單分批。