范繼東

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

1 引言

隨著拆零比例的持續(xù)上升，如何解決醫(yī)藥流通行業(yè)的拆零揀選問(wèn)題成為主要問(wèn)題?！柏浀饺恕毕到y(tǒng)由于能夠降低勞動(dòng)強(qiáng)度、提升人員作業(yè)效率，作為新型揀選方式正在日益為各家醫(yī)藥流通企業(yè)所重視，多層穿梭車(chē)系統(tǒng)作為其中典型的代表，由于其存儲(chǔ)密度大、揀選效率高等特點(diǎn)，正為各家醫(yī)藥流通企業(yè)所采用。多層穿梭車(chē)系統(tǒng)在應(yīng)對(duì)大量訂單的情況下，巷道端頭的料箱提升機(jī)成為影響整個(gè)系統(tǒng)效率的瓶頸點(diǎn)之一。本文針對(duì)多層穿梭車(chē)系統(tǒng)中“貨到人”揀選系統(tǒng)中如何利用訂單揀選分批策略，實(shí)現(xiàn)整體效率提升的問(wèn)題，提出了基于k-means算法的細(xì)分批算法，以最小化貨箱總出入庫(kù)次數(shù)為目標(biāo)，建立了考慮分批結(jié)果聚類(lèi)程度的訂單分批數(shù)學(xué)模型，實(shí)現(xiàn)可控聚類(lèi)程度的訂單分批，在同樣的業(yè)務(wù)情況下，有效的降低了“貨到人”揀選系統(tǒng)對(duì)提升機(jī)作業(yè)效率的要求。

2 問(wèn)題分析

訂單揀選是影響物流配送中心作業(yè)效率的重要因素。在“貨到人”揀選系統(tǒng)中，貨箱出入庫(kù)頻率是影響揀選效率的關(guān)鍵因素，當(dāng)出入庫(kù)較頻繁時(shí)，對(duì)設(shè)備的性能要求較高，設(shè)備難以滿足要求或成本較高。因此，降低貨箱出入庫(kù)頻率是影響揀選效率的重要因素。

訂單分批是把多張訂單集合成一批，進(jìn)行批次揀選作業(yè)。通過(guò)訂單分批，可以把相似度高的訂單合并在同一批次中，這樣相當(dāng)于把每批次訂單中的同一商品品項(xiàng)匯總后，再分配到每一個(gè)顧客訂單，可以有效的降低貨箱的出入庫(kù)次數(shù)，提高揀選效率。對(duì)于訂單分批問(wèn)題，常見(jiàn)的有三種分批方法：

（1）按時(shí)間窗分批：首先固定一個(gè)時(shí)間長(zhǎng)度，從某個(gè)時(shí)間點(diǎn)開(kāi)始，將該時(shí)間窗長(zhǎng)度內(nèi)到達(dá)的訂單分到同一個(gè)批次。

（2）固定訂單量分批：固定一個(gè)訂單批量，將按照先后順序到達(dá)的訂單一次分到該批次，直到達(dá)到容量限制，開(kāi)始下一個(gè)批次的分批。

（3）智能型分批：根據(jù)待分批訂單的結(jié)構(gòu)特點(diǎn)、使用特點(diǎn)的算法對(duì)訂單揀選合理分批。

前兩種方法屬于先到先服務(wù)的方式，沒(méi)法降低訂單對(duì)提升機(jī)的作業(yè)要求，所以本文采用智能算法進(jìn)行訂單分批。當(dāng)待分批訂單的數(shù)量很大時(shí)，由于現(xiàn)有智能分批算法的計(jì)算復(fù)雜度較高，會(huì)導(dǎo)致求解訂單分批結(jié)果的時(shí)間過(guò)長(zhǎng)，增加揀選等待時(shí)間，有必要設(shè)計(jì)一種低復(fù)雜度的算法，用于大批量訂單的分批，在計(jì)算速度較快的前提下實(shí)現(xiàn)大批量訂單到小批量訂單的轉(zhuǎn)換。此外，揀選效率和訂單的聚類(lèi)程度不一定成正比。在醫(yī)藥揀選中，根據(jù)GSP的要求，必須對(duì)藥品進(jìn)行批號(hào)批次管理，在確定訂單分批后，將貨箱出庫(kù)到揀選臺(tái)進(jìn)行揀選，由于同一批次中的訂單相似度較高，同一批次中的某個(gè)藥品原料箱有可能被多個(gè)訂單需要，就會(huì)造成分揀時(shí)很多揀選臺(tái)都在等待某個(gè)原料箱的情況，從而導(dǎo)致揀選等待時(shí)間過(guò)長(zhǎng)。所以并非聚類(lèi)程度越高，總揀選時(shí)間越短，還要考慮訂單分批的聚類(lèi)程度對(duì)后續(xù)揀選臺(tái)揀選時(shí)間的影響。

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

現(xiàn)有的研究在設(shè)計(jì)訂單分批算法時(shí)，并沒(méi)有針對(duì)醫(yī)藥批號(hào)批次管理的要求，考慮聚類(lèi)程度的影響問(wèn)題。本文在設(shè)計(jì)訂單分批算法時(shí)，將提出聚類(lèi)程度指數(shù)的概念來(lái)衡量訂單分批的聚類(lèi)程度，兼顧了藥品批號(hào)批次管理要求對(duì)揀選作業(yè)的特殊要求，同時(shí)考慮控制聚類(lèi)程度的訂單分批。

3 模型建立

3.1 模型假設(shè)

為了建模的方便，對(duì)要研究的“貨到人”揀選系統(tǒng)做了如下假設(shè)：

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

（2）一個(gè)訂單至少包含一個(gè)物品；

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

（4）一個(gè)原料箱在同一個(gè)批次中只能出庫(kù)一次；

（5）不考慮缺貨和補(bǔ)貨的情況。

3.2 符號(hào)說(shuō)明

本模型所使用的符號(hào)具體含義如下：

N—訂單總數(shù)；

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

K—倉(cāng)庫(kù)中所有品項(xiàng)的種類(lèi)總數(shù)；

M—單個(gè)訂單的訂單行上限；

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

C—每個(gè)批次的容量限制；

mn—第n個(gè)訂單含有的品項(xiàng)數(shù)目（n=1,2,...,N）；

sij—訂單Oi和Oj中相同品項(xiàng)的數(shù)量（i,j=1,2,...,N）；

T—貨箱總出入庫(kù)次數(shù)；

ρb—聚類(lèi)程度指數(shù)；

λ—聚類(lèi)程度閾值；

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

3.3 模型數(shù)學(xué)表達(dá)

根據(jù)上述問(wèn)題分析，可以建立如下數(shù)學(xué)模型：目標(biāo)函數(shù)：

約束條件：

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

3.4 基于k-means的訂單細(xì)分批算法

針對(duì)上述訂單分批數(shù)學(xué)模型，設(shè)計(jì)了基于kmeans算法的改進(jìn)算法，流程如圖1所示。該算法實(shí)現(xiàn)了變聚類(lèi)中心的訂單分批，其大體思路是：基于訂單之間的相似度進(jìn)行訂單的合批，每次加入一個(gè)訂單后都要對(duì)聚類(lèi)中心進(jìn)行更新，重新計(jì)算相似度來(lái)選出其他訂單；針對(duì)模型中的聚類(lèi)程度限制，算法設(shè)計(jì)了反饋調(diào)整，會(huì)根據(jù)聚類(lèi)程度限制來(lái)改變選擇訂單的優(yōu)先級(jí)，從而改變分批結(jié)果的聚類(lèi)程度。算法的具體步驟如下：

（1）計(jì)算所有訂單兩兩之間相同品項(xiàng)的數(shù)目sij，構(gòu)成初始的訂單相似矩陣S0。

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

（3）選擇最大相似度值對(duì)應(yīng)的兩個(gè)訂單組合作為聚類(lèi)的初始訂單批量。

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

（5）重復(fù)步驟（4），直到該批次的訂單數(shù)達(dá)到容量限制，則已得到該批次的初步分批結(jié)果。

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

（7）得到更新后的未分批訂單集，跳轉(zhuǎn)到步驟（2），不斷的重復(fù)整個(gè)過(guò)程，直到所有的訂單都完成分批。

4 仿真實(shí)驗(yàn)與結(jié)果分析

通過(guò)設(shè)計(jì)仿真實(shí)驗(yàn)，利用MATLAB 仿真軟件編程，對(duì)本文提出的兩種訂單分批算法進(jìn)行分析，仿真環(huán)境為MATLAB 2015b，Windows 10操作系統(tǒng)，DELL Inspiron 15，Intel i5-5200U CPU 2.2GHz，4GB RAM。

圖1 細(xì)分批算法流程圖

4.1 細(xì)分批算法仿真分析

（1）模型參數(shù)設(shè)置。K=500；N=160，320，480，640，800；M=5；C=16；λ=1（相當(dāng)于不考慮聚類(lèi)程度約束）

（2）仿真結(jié)果及分析。在MATLAB 中隨機(jī)生成訂單數(shù)據(jù)，將本文的細(xì)分批算法與傳統(tǒng)的先到先服務(wù)算法（FCFS）進(jìn)行比較，計(jì)算兩種算法在5 種不同訂單批量（N=160，320，480，640，800）下的貨箱出入庫(kù)次數(shù)，結(jié)果見(jiàn)表1。

表1 細(xì)分批算法和FCFS算法仿真結(jié)果

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

從圖2中可以看出，在相同訂單數(shù)據(jù)的情況下，細(xì)分批算法的貨箱總出入庫(kù)次數(shù)總是少于FCFS 算法，且訂單批量越大優(yōu)勢(shì)越明顯，驗(yàn)證了本文采用的分批算法相比傳統(tǒng)FCFS算法的有效性。

4.2 細(xì)分批算法聚類(lèi)程度約束仿真分析

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

（2）仿真結(jié)果及分析。本次仿真基于細(xì)分批算法，考慮改變聚類(lèi)程度閾值λ對(duì)分批結(jié)果的影響，同時(shí)記錄每個(gè)批次的聚類(lèi)程度指數(shù)和計(jì)算的迭代次數(shù)，具體結(jié)果如下：

①當(dāng)λ=1 時(shí)，由于聚類(lèi)程度指數(shù)的上限為1，所以結(jié)果的聚類(lèi)程度指數(shù)永遠(yuǎn)不會(huì)超過(guò)1，相當(dāng)于在沒(méi)有聚類(lèi)程度限制的前提下求解模型。這種情況下求得的貨箱總出入庫(kù)次數(shù)=387，詳細(xì)結(jié)果見(jiàn)表2。

圖2 細(xì)分批算法和FCFS算法仿真結(jié)果對(duì)比圖

表2 細(xì)分批算法運(yùn)行結(jié)果（λ=1）

②當(dāng)λ=0.8 時(shí)，貨箱的總出入庫(kù)次數(shù)=451，詳細(xì)結(jié)果見(jiàn)表3。

表3 細(xì)分批算法運(yùn)行結(jié)果（λ=0.8）

③當(dāng)λ=0.7 時(shí)，貨箱的總出入庫(kù)次數(shù)=497，詳細(xì)結(jié)果見(jiàn)表4。

表4 細(xì)分批算法運(yùn)行結(jié)果（λ=0.7）

④當(dāng)λ=0.6 時(shí)，由于聚類(lèi)程度指數(shù)過(guò)低，所以沒(méi)有符合條件的分批結(jié)果。

分析上述結(jié)果可知，隨著聚類(lèi)程度指數(shù)的降低，貨箱的總出入庫(kù)次數(shù)增加，這和實(shí)際情況是相符合的。同時(shí)，聚類(lèi)程度指數(shù)不能無(wú)限降低，其下限值和具體的訂單數(shù)據(jù)有關(guān)系。在實(shí)際應(yīng)用中，應(yīng)該通過(guò)綜合分析整個(gè)訂單揀選過(guò)程，確定最佳的聚類(lèi)程度指數(shù)，作為聚類(lèi)程度閾值。

5 結(jié)論

本文通過(guò)設(shè)計(jì)的基于K-means 的細(xì)分批算法，在中小批量訂單的前提下，通過(guò)比較細(xì)分批算法和傳統(tǒng)FCFS算法的結(jié)果，證明了細(xì)分批算法相比傳統(tǒng)FCFS算法的有效性；同時(shí)考慮聚類(lèi)程度的限制，分析細(xì)分批算法在不同聚類(lèi)程度閾值時(shí)的分批結(jié)果，證明該算法可以實(shí)現(xiàn)可控聚類(lèi)程度的訂單分批。