秦 馨，趙劍道，任 楠

（1.北京機械工業(yè)自動化研究所，北京 100120；2.北自所（北京）科技發(fā)展有限公司，北京 100120）

0 引言

近年來，在新經(jīng)濟發(fā)展環(huán)境下，市場逐漸變得多元化，消費需求因此開始向多樣化進(jìn)行轉(zhuǎn)變，商品的供應(yīng)訂單也隨之呈現(xiàn)出碎片化、零散化的趨勢。越來越多的企業(yè)傾向于通過一個集訂單處理、倉儲管理、揀貨配送于一體的物流配送中心來提高整體物流供應(yīng)鏈的供應(yīng)效率。而在配送中心的所有作業(yè)中，揀貨作業(yè)的自動化程度相對很難提高，作業(yè)時間占據(jù)比重較大，是制約整個物流配送流程效率的關(guān)鍵因素。因此為了提高倉儲運作效率、縮短事務(wù)處理時間與降低物流成本，如今物流中心進(jìn)行配送管理最重要的目標(biāo)之一是規(guī)劃合理的揀貨方法。而在對揀貨作業(yè)流程進(jìn)行控制優(yōu)化的策略中，選擇合理的訂單分批方法是最有效且最關(guān)鍵的研究重點之一。

1 訂單分批

訂單分批是指將大批量的訂單按照一定的規(guī)則和方法進(jìn)行統(tǒng)一的分類整合，最終形成不同批次，每一個批次都包含多個訂單，然后按照不同的批次合并來進(jìn)行貨物分揀作業(yè)。訂單分批通過縮短整體的揀選路徑、減少貨物的搬運次數(shù)，顯著的提高了揀選效率、節(jié)省了勞動力、減少了揀選成本。

早期的訂單分批問題研究主要根據(jù)項目應(yīng)用經(jīng)驗進(jìn)行優(yōu)化，一般按照某種固定的優(yōu)先級來確定分批策略，最為常用的為先到先分批策略。這種傳統(tǒng)策略沒有考慮訂單之間的相似性，效率優(yōu)化效果有限。隨著訂單數(shù)目的增加，在揀選方式上，大部分學(xué)者開始采用啟發(fā)式算法對這一方向進(jìn)行了深入的研究，例如種子算法、包絡(luò)算法、節(jié)約算法、k-means算法及其各種組合算法。但是這些算法或受初始訂單的選擇影響較大，分批效果不穩(wěn)定，或?qū)τ唵蔚谋旧韺傩钥紤]不足。而且大部分研究都是針對“人工揀貨”的應(yīng)用場景，對于“貨到人”模式的適用性不足，因此對“貨到人”揀選系統(tǒng)的訂單分批優(yōu)化策略值得探究。

本文基于“貨到人”的實際應(yīng)用場景，采用基于凝聚型聚類算法的訂單分批策略，以最小化貨物搬運次數(shù)為目標(biāo)構(gòu)建了訂單分批問題的數(shù)學(xué)模型，通過計算相似系數(shù)，在一定的約束條件下得到了有效的分批結(jié)果。

2 模型與假設(shè)

假設(shè)某段時間內(nèi)存在N個訂單Xi（i=1，2，…，n）需要進(jìn)行分揀作業(yè)，其中，每個訂單中有若干個品項，相同品項的存儲位置視為同一儲位。現(xiàn)根據(jù)貨到人系統(tǒng)的實際工作場景，無需考慮人員或設(shè)備的行走距離以及不同貨物間的儲位關(guān)聯(lián)程度，所有訂單的揀選時間和揀選距離與訂單品項的搬運次數(shù)可近似于線性相關(guān)，同時每個揀選工位可同時揀選的訂單數(shù)固定。因此，本文中訂單分批的總目標(biāo)為，在每個訂單不允許分割且每批揀選訂單數(shù)固定的情況下，將N個訂單進(jìn)行分批揀選，使得分批后貨物總的搬運次數(shù)最少。假設(shè)每批訂單數(shù)固定為C，分批后的批次總數(shù)為T，第j批訂單的搬運次數(shù)為Lj，總的搬運次數(shù)為L。則該訂單分批問題建立的數(shù)學(xué)模型為：

目標(biāo)函數(shù)：

約束條件：

目標(biāo)函數(shù)式(1)表示訂單分批后，每批訂單搬運貨物次數(shù)總和最小，Lj為第j批訂單的搬運貨物次數(shù)（即為同一批中各個訂單合并后所有品項的搬運次數(shù)，同一品項按照搬運一次計算）。約束條件式(2)表示每個訂單在分批后只允許在其中一個批次出現(xiàn)，既不能分割訂單，也不能重復(fù)分配訂單。式(3)表示訂單分批后每一批訂單數(shù)量為固定值，前T-1批訂單數(shù)量為C個，第T批訂單數(shù)量不大于C個。式(4)為訂單分批結(jié)果，xij表示訂單Xi的分批結(jié)果，若該訂單分配到第j批中，取值為1；若不存在，則取值為0。

3 算法

聚類算法是一種常見的分類算法，已經(jīng)大量應(yīng)用于自然科學(xué)和社會科學(xué)等不同的領(lǐng)域中，如統(tǒng)計學(xué)、信息檢索、生物學(xué)和機器學(xué)習(xí)等。不同于決策樹、支持向量機等分類算法，聚類是一種典型的非監(jiān)督型的學(xué)習(xí)算法，是對于已經(jīng)獲取的沒有預(yù)先進(jìn)行標(biāo)記和確定其類別的數(shù)據(jù)，根據(jù)數(shù)據(jù)本身的相似性來將樣本分到不同的組別，盡可能使得每組內(nèi)的數(shù)據(jù)之間是相似的（相關(guān)的），而不同組的數(shù)據(jù)之間是不同的（不相關(guān)的）。同一組內(nèi)的數(shù)據(jù)間相似性越高，距離越小，不同組間的數(shù)據(jù)差別越大，距離越大，聚類效果就越好。

本文采取的聚類算法為凝聚型層次聚類，也稱為合并型聚類算法，是一種自底向上的算法。它是從每個點作為一個個體簇開始，然后重復(fù)地將兩個最靠近的簇合并為一個，直到獲取滿意的聚類結(jié)果為止。凝聚型層次聚類的算法原理是：

1）定義簇的鄰近性概念，計算鄰近度矩陣；

2）Repeat；

3）將鄰近度最高的兩個簇合并為一個簇；

4）按照最新的簇的劃分來進(jìn)行鄰近度計算，確定其鄰近性；

5）Until僅剩下符合要求的簇。

訂單分批問題的聚類分析就是通過一定的鄰近度計算，將所有訂單分成不同的批次，然后對每一批的訂單進(jìn)行集中揀選，其目的是減少貨物的搬運次數(shù)。

3.1 特征向量

鄰近度的計算可以通過特征向量來實現(xiàn)。在訂單分批問題中，每一個訂單包含多個貨物品項，每一個品項的儲存位置已知。由于本文的訂單分批基于貨到人系統(tǒng)，人無需去貨架中行走揀選貨物，而且在自動化倉庫的出庫模式下，每次只能搬運一種貨物出庫，因此在進(jìn)行鄰近度計算時，不需要考慮不同品項儲存位置之間的相似性以及行走距離的遠(yuǎn)近。

利用訂單中包含的貨物種類來生成每個訂單的特征向量，將每一個品項定義為特征向量的一個維度，根據(jù)單個訂單中是否包含該品項定義該維度的值。假設(shè)定義總的貨物品項數(shù)目為m，每種貨物索引為Ij（j=1，2，…，m），Vi為訂單Xi（i=1，2，…，n）的特征向量，則定義：

3.2 鄰近度

鄰近度是對兩個對象相關(guān)性的量化描述，兩個數(shù)據(jù)越相似，鄰近度越高。聚類算法中，鄰近性度量的選擇與計算非常重要，對聚類的效果好壞有著極大的影響。目前最為常用的鄰近性度量計算方法是基于歐幾里得距離和余弦相似性。

3.2.1 歐幾里得距離

歐幾里得距離也稱歐氏距離，是一個通常采用的兩點間的距離定義，表示在多維空間之中這兩個點之間的真實距離，兩個對象之間的歐氏距離越大，則相似性越低。使用歐氏距離計算任意兩個訂單間鄰近性的公式為：

其中，vik，vjk分別表示第i、j個訂單所對應(yīng)的特征向量之中第k維的特征值。

3.2.2 余弦相似性

余弦相似性是通過計算兩個向量所形成的夾角余弦值的大小來衡量它們之間的鄰近性，鄰近性越高的兩個對象，它們的余弦相似性越接近于1，鄰近度越低，他們的余弦相似性越接近零。余弦相似性的值是和向量本身的長度無關(guān)的，只和向量的指向方向相關(guān)。使用余弦相似性計算任意兩個訂單間鄰近性的公式為：

其中，vik，vjk分別表示第i、j個訂單所對應(yīng)的特征向量之中第k維的特征值。

3.3 算法流程

根據(jù)以上分析以及鄰近性度量系數(shù)的選擇，使用聚類算法進(jìn)行訂單分批的具體算法流程如下：

1）根據(jù)每個訂單所包含的品項，推導(dǎo)每個訂單的特征向量Vi。

2）根據(jù)訂單的特征向量計算出每兩個訂單之間的相似系數(shù)sij。

3）將所有的相似系數(shù)sij倒序排列，若存在相同的相似系數(shù)，則按照兩個訂單共同品項和總品項的數(shù)量進(jìn)行排序。

4）選取相似系數(shù)最大的兩個訂單合并為同一訂單，判斷新訂單是否滿足約束條件，若不滿足，選擇下一個sij，直到滿足所設(shè)定的約束條件，計算新訂單的特征向量。

5）判斷新訂單包含訂單數(shù)是否達(dá)到一批訂單上限，若沒有，將新訂單并入原有的訂單數(shù)據(jù)，若達(dá)到上限，將分配完成的一批訂單輸出，然后重復(fù)第2）、3）、4）步，直到所有訂單分批結(jié)束。

4 仿真

4.1 實驗方案

實驗數(shù)據(jù)來源于隨機生成的2000個訂單數(shù)據(jù)，根據(jù)測試需要，只選取其中的訂單號和包含品項的信息。其中，總的品項數(shù)量定義為50種，依據(jù)現(xiàn)實使用場景，單個訂單包含品項數(shù)基本集中在2～20種之間，訂單分批后每批訂單的數(shù)量固定為5個。將2000個訂單中每200個訂單分為一組，共隨機分為10組。

本文采用基于聚類算法的分批策略進(jìn)行研究，衡量該算法在訂單分批問題中的優(yōu)化效果，并且分別采用歐幾里得距離和余弦相似性進(jìn)行相似系數(shù)的計算，比較在使用聚類算法來進(jìn)行訂單分批時，不同的鄰近度計算方法在這一問題應(yīng)用中的優(yōu)劣。并且為了更好的驗證本文提出的聚類算法在訂單分批問題中的優(yōu)勢，將相同的數(shù)據(jù)分別采用不分批的策略和先到先分批的策略進(jìn)行計算，作為本文所提出算法的對照參考組。

每次實驗都從10組數(shù)據(jù)（每組數(shù)據(jù)包含200個訂單）中分別隨機抽取20、50、100、150、200個訂單來進(jìn)行分批計算，然后將10組數(shù)據(jù)的計算結(jié)果取其平均值作為最終分批結(jié)果。

4.2 實驗結(jié)果分析

實驗采用了基于歐幾里得距離的聚類算法、基于余弦相似性的聚類算法、先到先分批的策略和不分批策略四種方案進(jìn)行計算，對比驗證不同方案的揀選效率。通過計算分批問題的目標(biāo)函數(shù)值，即所有訂單品項總的搬運次數(shù)作為衡量分揀效率的指標(biāo)。對10組數(shù)據(jù)的實驗結(jié)果計算其平均值如表1所示。由表1可得，在不同規(guī)模的數(shù)據(jù)集下，不采用訂單分批策略的方案最終的品項搬運次數(shù)最高；采用先到先分批策略進(jìn)行訂單分批后，搬運次數(shù)有所下降；而基于聚類算法的分批策略，使得訂單總的搬運次數(shù)最少。因此，基于聚類算法的分批策略在訂單分揀作業(yè)中，對揀選效率有著很大提升。

表1 分揀作業(yè)總的搬運次數(shù) 單位：次

圖1為不同的分批策略下，最終的貨物搬運次數(shù)與不分批策略搬運次數(shù)的比值。由圖1可得，在不同規(guī)模的訂單數(shù)據(jù)集下，先到先分批策略對于揀選效率的優(yōu)化效果比較穩(wěn)定，在65%～70%之間，而隨著訂單規(guī)模的增加，基于聚類算法的分批策略對揀選作業(yè)的優(yōu)化效果有著顯著提高，當(dāng)訂單數(shù)達(dá)到200個時，貨物搬運次數(shù)可降至不分批策略的50%左右。其中，不論訂單規(guī)模的大小，采用余弦相似性計算鄰近度的聚類算法在揀選效率的優(yōu)化上都要更優(yōu)于基于歐氏距離的聚類算法。

圖1 分批策略與不分批策略的搬運次數(shù)比

本文研究的訂單分批問題是基于實際應(yīng)用場景的，因此在減少訂單總的搬運次數(shù)的基礎(chǔ)上，應(yīng)當(dāng)考慮訂單分批的算法計算時間，這同樣影響著訂單揀選的效率。對10組實驗的計算時間計算其平均值如圖2所示。由圖2可得，對于不同規(guī)模的訂單，先到先分批策略的計算時間沒有明顯變化，看忽略不計；而隨著訂單規(guī)模的增加，聚類算法的計算時間增加較明顯，其中，基于余弦相似性的聚類算法所消耗的時間始終少于基于歐氏距離的聚類算法，且隨著訂單數(shù)的增加，兩種算法計算時間的差距也在逐步增加。

圖2 訂單分批計算時間

5 結(jié)語

本文在自動化倉庫“貨到人”模式的應(yīng)用場景下，針對訂單分批問題，構(gòu)造了以最小化訂單品項總的搬運次數(shù)為目標(biāo)函數(shù)的數(shù)學(xué)模型，并且搭建了基于鄰近度度量的聚類算法模型，與不分批的策略和傳統(tǒng)的采用先到先分批的策略相比，大大減少了貨物搬運次數(shù)，有效的提高了訂單揀選效率，雖然分批算法的計算時間相比較而言有所增加，但仍控制在250s以內(nèi)，與自動化倉庫貨物的搬運時間相比存在著較大的差據(jù)，因此可忽略不記。而且，在進(jìn)行鄰近度計算時，提出了使用歐幾里得距離和余弦相似性兩種不同的相似系數(shù)的計算方法，其中，采用余弦相似性作為鄰近度的聚類算法無論在提高揀選效率方面還是縮短計算時間方面表現(xiàn)都更加優(yōu)秀。

本文主要針對“貨到人”模式下的自動揀選，分揀人員不必在貨架間行走，無需考慮行走距離和揀選路徑的選擇，未來可對“人到貨”模式下的揀選作業(yè)進(jìn)行進(jìn)一步的研究。