基于聚類算法的訂單分批策略研究

秦 馨，趙劍道，任 楠

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

0 引言

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

1 訂單分批

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

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

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

2 模型與假設(shè)

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

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

約束條件：

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

3 算法

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

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

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

2）Repeat；

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

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

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

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

3.1 特征向量

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

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

3.2 鄰近度

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

3.2.1 歐幾里得距離

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

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

3.2.2 余弦相似性

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

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

3.3 算法流程

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

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

2）根據(jù)訂單的特征向量計(jì)算出每?jī)蓚€(gè)訂單之間的相似系數(shù)sij。

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

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

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

4 仿真

4.1 實(shí)驗(yàn)方案

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

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

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

4.2 實(shí)驗(yàn)結(jié)果分析

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

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

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

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

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

圖2 訂單分批計(jì)算時(shí)間

5 結(jié)語(yǔ)

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

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