吳天行，郭 鍵

（北京物資學(xué)院，北京 101149）

基于圖論的聚類算法在訂單分批問題中的應(yīng)用

吳天行，郭 鍵

（北京物資學(xué)院，北京 101149）

首先闡述了傳統(tǒng)的基于相似巷道的訂單分批模型的原理，然后根據(jù)圖論和聚類分析的相關(guān)原理，建立了基于圖論的聚類算法訂單分批模型，最后通過一個實際的算例，以最小揀選路徑為目標(biāo)函數(shù)，分別對未分批訂單、基于巷道相似性分批的訂單和基于圖論的聚類算法分批的訂單結(jié)果進行了比較，從而論證了該算法的有效性。

揀選作業(yè)；訂單分批；圖論；聚類分析

1 引言

物流揀選作業(yè)是按照客戶的需求，將一種或多種存儲貨物取出重新組合整理并安放在特定位置的一系列的作業(yè)活動，該活動涵蓋了拆包和再次包裝。合理的揀選作業(yè)可以極大地提高物流活動的運作效率[1]。在揀選作業(yè)中，訂單分批策略一直以來都備受研究者的關(guān)注。國外學(xué)者Van den berg就提出進行訂單分批對降低揀選路徑長度和人力物力的消耗具有重要作用。而國內(nèi)學(xué)者李詩珍也認(rèn)為，對減少揀貨作業(yè)總時間影響最大的活動就是分批策略[2]。

在訂單分批問題中，采用聚類分析的方法對訂單進行分批是目前比較常用的方法，該方法的主要原理是通過一系列的相關(guān)準(zhǔn)則，將符合這一準(zhǔn)則的相關(guān)訂單合并成為一類訂單，其主要目的是減小訂單揀選的總路徑，提高訂單揀選效率，從而降低總揀選成本。

訂單分批中常以相似度作為分批準(zhǔn)則，訂單相似度也就是訂單之間的相似性。相似度主要劃分為兩大類，即特征向量和相似系數(shù)。在特征向量中，常作為劃分依據(jù)的主要有儲位特征向量和坐標(biāo)特征向量。而在相似系數(shù)中，常用的劃分依據(jù)主要有儲位相似系數(shù)、面積相似系數(shù)和巷道相似系數(shù)[3]。目前應(yīng)用最為廣泛的就是基于巷道相似系數(shù)的訂單分批策略。

2 基于巷道相似系數(shù)的訂單分批策略

利用聚類分析法進行訂單分批作業(yè)的核心就是確定兩個訂單之間的相似程度，根據(jù)相似程度來判斷是否將這兩個訂單合成一批進行揀選。訂單間的巷道相似度是進行訂單是否合成一批常用的指標(biāo)，即依據(jù)兩個訂單所具有的相同巷道數(shù)的多少進行度量。

兩個訂單間所擁有共同巷道數(shù)比例的公式為:

其中Sij為巷道相似系數(shù)，Ci和Cj表示訂單i和j中商品分布的巷道集合。

根據(jù)上述巷道相似系數(shù)的公式，可以建立基于聚類算法的訂單分批數(shù)學(xué)模型。設(shè)：

式（2）是在形成批量的訂單中, 同一批中的兩兩訂單相似系數(shù)之和最大。式（3）表示一個訂單只允許在一批中完成。式（4）表示只有在第j批訂單已經(jīng)存在的情況下，訂單i才可以分批到j(luò)批中[4]。式（5）、式（6）表示每批訂單所含有的品類數(shù)總的重量和容積不可以超過揀貨車的載重量和容積。

該算法的本質(zhì)仍然屬于節(jié)約算法，核心依然是確定最小的訂單揀選路徑，從而提高物流揀選效率。不同點是分批時的依據(jù)由原本的最大節(jié)約量改為巷道的最大相似系數(shù)。該算法的基本思想簡述如下：

（1）計算出所有的兩兩訂單間的相似系數(shù)Sij。

（2）將計算出的相似系數(shù)按照從大到小的順序排列。

（3）將最大的相似系數(shù)的訂單合成為一批，如果有多個相似系數(shù)相同的訂單，則選擇訂單中品類最多的訂單合成為一批，并且判斷是否滿足約束條件，如不滿足則轉(zhuǎn)至步驟（5）。

（4）將已經(jīng)合成的訂單作為新產(chǎn)生的訂單，對新的訂單重新計算巷道相似系數(shù)進行分批。

（5）將最后仍沒有分批的訂單作為單獨訂單自成一批，停止。

3 基于圖論的訂單分批策略

3.1 圖論的相關(guān)概念

圖論是一門應(yīng)用廣泛且內(nèi)容豐富的學(xué)科，該學(xué)科可以追溯至柯尼斯堡七橋問題[5]。圖論中的圖是由多個給定的點及連接兩點的線所構(gòu)成的圖形，這種圖形通常用來描述某些事物之間的某些特殊關(guān)系，用點代表事物，用連接兩點的線表示相應(yīng)兩個事物間具有的這種關(guān)系[6]。

圖的數(shù)學(xué)含義是指一個有序的三元組(V(G),E(G), ψG)，其中V(G)為非空的頂點集，E(G)為不與V(G)相交的邊集，而ψG是關(guān)聯(lián)函數(shù)，使得G的每一條邊都對應(yīng)于G的無序頂點對uv(未必互異)，簡記為圖G=(V(G),E(G))或G=(V,E)[7]。

各結(jié)點之間存在的相近關(guān)系可以用K近鄰有向圖來加以描述。K近鄰有向圖是指有向圖G=（V，E），結(jié)合點集為V={v1，v2,…,vn}，邊集合為E={e1,e2,…,en}，ei=＜vp, vq＞，vp，vq∈V，i=1，2，…，m，其中ei存在當(dāng)且僅當(dāng)vp是vq的近鄰，ei的方向為vp起始點指向vq的終止點。

在K近鄰有向圖G=（V，E）中，如果對V中的任意兩個結(jié)點vp和vq同時存在邊epq=＜vp,vq＞和eqp=＜vq,vp＞，即為結(jié)點vq和vp互為近鄰，則稱vq和vp為K互鄰居。

K聚類圖是為了區(qū)分K互鄰居和K非互鄰居而建立起來的，具體含義是指圖G，=(V，E，)，結(jié)點集合為V={v1，v2，…,vn}，邊集合為∈V，i=1，2，…，m，其中e，i存在當(dāng)且僅當(dāng)vp是vq的近鄰。通過以上的定義可知K聚類圖是一個無方向的圖，在K聚類圖中所有連同的子圖都是K互鄰居。

3.2 基于圖論的訂單分批算法

基于圖論的訂單分批算法又名N-M算法，該算法的主要原理是首先分析數(shù)據(jù)中的對象,根據(jù)分析尋找所有對象的K近鄰，根據(jù)K近鄰相互關(guān)聯(lián)性構(gòu)造K近鄰有向圖，最后再通過K近鄰有向圖中的K互鄰居關(guān)系建立K聚類圖，發(fā)現(xiàn)數(shù)據(jù)中的自然聚類，從而對訂單進行分批[8]。該算法的具體執(zhí)行步驟如下：

（1）建立K近鄰有向圖。假設(shè)需要分批的訂單里包含n個商品品項，各個商品品項可以表示為如下所示的商品各品項之間的距離矩陣D。

其中d(i,j)為品項i和品項j之間的距離，滿足d(i,j)≥0，d(i,j)=d(j,i)且d(i,i)=0。

得到品項的距離矩陣之后對距離矩陣進行搜索，基于搜索結(jié)果建立K近鄰有向圖。同時將K近鄰有向圖表示為鄰接矩陣的形式，矩陣的元素可以表示為A_G(i, j)。

（2）建立K聚類圖。K聚類圖是由多個K互鄰居的點對構(gòu)成的，K互鄰居的點對相互連結(jié)就形成了K互鄰居關(guān)系子圖，當(dāng)子圖中相互連結(jié)的點僅有一個時，該子圖就變?yōu)楣铝Ⅻc，利用K聚類圖可以將數(shù)據(jù)很好的進行聚類[9]。為了方便計算與存儲，可以將K聚類圖表示為鄰接矩陣的形式，并且記為A_CG，A_CG的元素可以表示為A_CG(i,j)。鄰接矩陣的構(gòu)造如下所示：

（3）遍歷K聚類圖，形成聚類。對K聚類圖進行遍歷，在進行遍歷時應(yīng)使用廣度優(yōu)先搜索算法進行遍歷，利用廣度優(yōu)先搜索算法的基本步驟如下所示：

①?v∈V(G)標(biāo)號l(v)=0，令l=0。

②當(dāng)所有標(biāo)號為l時，與頂點u相關(guān)聯(lián)的邊的端點都已經(jīng)標(biāo)號時，則停止；否則把與頂點u相關(guān)聯(lián)的邊的端點編號編為l+1，并記錄這些邊，令l=l+1，轉(zhuǎn)至②。

（4）根據(jù)聚類的結(jié)果按照分批規(guī)則進行分批。在對K聚類圖進行遍歷后，可以自然形成關(guān)于訂單商品品項的自然聚類，根據(jù)實際問題可以按照如下的分批規(guī)則將訂單進行適當(dāng)?shù)姆峙c調(diào)整，使得其符合實際的訂單分批要求。

③將已合成的訂單批次剔除原訂單后，對剩余未分批的訂單重新進行聚類，直至分批完成。

4 算例驗證

4.1 算例的基本信息

為了驗證基于圖論的訂單分批算法的科學(xué)性與有效性，下面將以一個實際的訂單分批的例子對該算法進行驗證。該訂單分批的例子將會分別使用未分批的訂單方法、基于相似性的訂單分批算法和基于圖論的訂單分批算法對訂單進行分批，并對分批結(jié)果進行比較和驗證。

為了便于比較和分析，訂單分批的例子取自于文獻[10]中的算例，其倉庫貨物平面圖如圖1所示。

圖1 倉庫貨物平面圖

由圖1可知該倉庫是一個由15排貨架和7條巷道組成的，左下角是倉庫的出入口?，F(xiàn)在已知每一排貨架有15個存儲單位，每一個單位的長度和寬度都為1，巷道的寬度為1。

現(xiàn)有7個需要揀取的訂單，詳細數(shù)據(jù)見表1。

表1 揀選訂單信息表

訂單揀選的要求是在滿足揀選車重量和體積的要求下，如何使揀選的訂單總距離最小。

4.2 未分批的訂單揀選距離

本次算例驗證的揀貨路徑策略采取混合策略，即通過選取穿越策略、返回策略、中點策略、最大間隙策略等使揀貨路徑最短[11]。不對訂單進行分批只需要將備選的7個訂單的總的路程計算出來，并對每個訂單體積和重量是否符合揀選車的要求進行驗證，具體過程見表2。

表2 未分批訂單揀選距離表

4.3 基于巷道相似性的訂單分批揀選距離

利用巷道相似系數(shù)對訂單進行分批，首先要使用式（1）得到巷道的相似系數(shù)，經(jīng)過計算可以得到巷道相似系數(shù)見表3。

表3 巷道相似系數(shù)表

根據(jù)表3可知，將訂單4與訂單6合成一批作為新的訂單，其余的再次計算巷道相似性。由此可以得到新的巷道系數(shù)見表4。

表4 新的巷道系數(shù)表

由表4可知，應(yīng)該將訂單3與訂單5合成為一批，其余的訂單再次計算巷道的相似系數(shù)。

繼續(xù)按照上述的方式進行計算，最后可以得到最終的訂單分批結(jié)果，見表5。

表5 最終訂單分批表

根據(jù)已經(jīng)得到的訂單分批可以計算出基于巷道相似系數(shù)的訂單分批的揀選距離為81+77+98+85=341。

4.4 基于圖論的訂單分批揀選距離

使用基于圖論的訂單分批算法首先應(yīng)該根據(jù)式（8）計算出各訂單內(nèi)商品品項的距離矩陣D1，為了方便說明與計算，現(xiàn)在將原圖轉(zhuǎn)化為按照商品品項標(biāo)號排序的倉庫平面圖，如圖2所示。

圖2 商品品項倉庫布局平面圖

由圖2可知，需要分批的7個訂單一共有25個商品品項，這些商品分別由1到25分別標(biāo)號，以此計算出這7個訂單商品品項的距離矩陣D1。

根據(jù)距離矩陣D1以及式（9）以及式（10），可以得到K聚類圖的鄰接矩陣，這里由于點分布是隨機的，所以K的取值為5。由此可以得到K=5時的鄰接矩陣D2。

根據(jù)得到的K聚類圖的鄰接矩陣進行遍歷，遍歷的方法采用廣度優(yōu)先搜索算法，并利用MATLAB軟件進行求解。

廣度優(yōu)先搜索算法求解的結(jié)果見表6。

表6 求解結(jié)果表

根據(jù)求解結(jié)果可以將表6轉(zhuǎn)化為按照訂單分批的形式，見表7。

表7 原始訂單分批

由于實際情況訂單不允許被拆分，因此需要根據(jù)訂單分批規(guī)則重新進行分批。根據(jù)訂單分批規(guī)則①可以將訂單3、訂單6和訂單7分成一批，新分批的訂單編號位1。根據(jù)分批規(guī)則②可以將訂單1與訂單2合為一批，新分批的訂單編號為2。其余未分批的訂單有訂單4與訂單5，將其重新使用N-M算法進行分批，可以得到表8未分批訂單的商品距離。

表8 未分批訂單商品距離

根據(jù)表8可以得到K聚類圖鄰接矩陣D3。

對矩陣D3使用廣度優(yōu)先搜索算法，當(dāng)K值為3時，可以得到商品品項的分批，即為第1批：1；第2批：2,3,4；第3批：5。根據(jù)以上信息可以得到訂單4與訂單5以商品品項為單位的分批，見表9。

表9 訂單4與訂單5分批情況

根據(jù)實際情況訂單不允許被拆分，因此根據(jù)訂單分批規(guī)則可以將訂單4與訂單5合為一批訂單。

由此可以得到最后的訂單分批結(jié)果見表10。

表10 訂單分批結(jié)果

根據(jù)訂單分批的結(jié)果可以計算出訂單分批后的總路程為107+125+52=284。

4.5 結(jié)論及分析

根據(jù)以上的計算可以得到利用N-M算法進行訂單分批的結(jié)果最優(yōu)為284。其次是使用巷道相似性的分批算法為341，最差的是不對訂單進行分批的結(jié)果為471。因此可以清楚的看到，對訂單進行分批對于揀選距離的優(yōu)化有著重要的作用，而在訂單分批方法中，基于圖論的訂單分批算法相較于傳統(tǒng)的基于巷道相似性的訂單分批算法有著一定的優(yōu)越性，在實際的訂單分批中應(yīng)當(dāng)考慮使用該種算法。

由兩種訂單分批算法的原理分析可以得知，基于巷道相似性的訂單分批算法是從整體上來進行訂單分批的，該算法是根據(jù)相同的巷道內(nèi)揀選距離一般較短這一原理進行分批，而基于圖論的訂單分批算法是從每一個訂單品項的角度出發(fā)尋找最短路徑，該算法是直接求出訂單商品品項之間的最短揀選路徑再對訂單進行分批的。由此來看基于圖論的訂單分批方法可以更精確的找到訂單之間的最短路徑，從而更有效地進行訂單分批。

由于N-M算法引入了K互鄰居和K聚類圖的概念，根據(jù)K互鄰居確定的訂單分批不需要依據(jù)其他的劃分批次的方法，可以減少因為劃分概念不清造成的聚類錯誤，同時計算中的K值也更適合使用者從底層到高層進行參數(shù)的設(shè)定。

[1]徐強.基于電子標(biāo)簽的配送中心分揀系統(tǒng)的研究與設(shè)計[D].武漢:武漢理工大學(xué)，2008.

[2]曹雪麗.人工揀選作業(yè)中訂單分批處理研究綜述[J].物流技術(shù),2012,(9).

[3]王雪飛.基于分層加權(quán)的多邊形圖形匹配[J].工程圖學(xué)學(xué)報, 2002,(2).

[4]李詩珍.配送中心揀貨作業(yè)優(yōu)化設(shè)計與控制研究[D].成都:西南交通大學(xué),2008.

[5]劉斌.有源網(wǎng)絡(luò)“有向根樹法”的研究及應(yīng)用[D].天津:河北工業(yè)大學(xué),2007.

[6]任媛.關(guān)于圖控制理論的若干問題研究[D].通遼:內(nèi)蒙古民族大學(xué),2013.

[7]張新.圖論在集合論中的應(yīng)用[D].濟南:山東大學(xué),2005.

[8]應(yīng)德全.一種基于圖論的聚類算法 NeiMu[J].計算機工程與應(yīng)用,2009,(3).

[9]應(yīng)曉敏.面向Internet個性化服務(wù)的用戶建模技術(shù)研究[D].長沙:國防科學(xué)技術(shù)大學(xué),2003.

[10]李詩珍.基于聚類分析的訂單分批揀貨模型及啟發(fā)式算法[J].統(tǒng)計與決策,2008,(12).

[11]楊華榮.配送中心揀貨路徑信息采集與處理研究[D].長沙:中南大學(xué),2011.

Application of Graph Theory Based Clustering Algorithm in Order Batching Problem

Wu Tianxing,Guo Jian
(Beijing Wuzi University,Beijing 101149,China)

In this paper,we first elaborated on the working principle of the order batching model based on the traditional channel similarity principle,then according to the graph theory and clustering analysis,built the order batching model using the graph theory based clustering algorithm,and at the end,through an empirical numerical example,compared the order batching result based on channel similarity and based on the clustering algorithm,thus demonstrating the validity of the algorithm developed in this paper.

picking activity;ordering batching;graph theory;clustering analysis

F224;F252.21

A

1005-152X(2017)08-0112-05

2017-07-03

北京市屬高等學(xué)校青年拔尖人才培育計劃項目（CIT&TCD201504052）；北京物資學(xué)院青年運河學(xué)者資助項目；北京物資學(xué)院國家級科研項目培訓(xùn)基金項目

吳天行（1990-），男，河北人，碩士研究生，研究方向：算法與模型優(yōu)化。

doi∶10.3969/j.issn.1005-152X.2017.08.026