基于K-Means聚類算法的配送中心物流成本分析

馬大奎， 陳 銘 （廣東電網(wǎng)公司電網(wǎng)規(guī)劃研究中心，廣東 廣州 510663）

配送中心作為供應(yīng)鏈的關(guān)鍵組成部分，一直受到企業(yè)界和學(xué)術(shù)界的重視。配送中心對(duì)供應(yīng)鏈的影響主要來(lái)自于兩個(gè)方面：一是配送中心本身操作效率，二是配送中心地址的選擇。對(duì)于物流配送中心選址問(wèn)題，對(duì)不同的模型要求，傳統(tǒng)的研究方法主要有整數(shù)規(guī)劃法、圖上作業(yè)法[1]、重心法[2]、鮑莫爾一沃爾夫法 （Baumol-Wolfe）[3]、運(yùn)輸規(guī)劃法、仿真方法等。前人已經(jīng)提出許多基于精確值的選址方法，利用數(shù)學(xué)規(guī)劃方法[4,5]確定最理想的地址,Tompkins和White[6]用偏好理論將所有主觀因素兩兩比較從而為主觀因素賦予了權(quán)重值。Spohrer和Kmak[7]提出了一種權(quán)重因素分析方法將定量的數(shù)據(jù)和定性的評(píng)價(jià)值結(jié)合在一起，用以從多個(gè)備選項(xiàng)中選擇合適的地址。Stevenson[8]提出了一種選擇最好地址的價(jià)值量分析方法。國(guó)內(nèi)學(xué)者對(duì)于配送中心選址研究也取得了一定的成就，提出了一些配送中心選址的新方法。西南交通大學(xué)的劉海燕、李宗平、葉懷珍[9]的論文 《物流配送中心選址模型》利用的是混合整數(shù)規(guī)劃法，長(zhǎng)沙交通學(xué)院的陳曦、傅明[10]的論文 《GIS環(huán)境下的物流配送中心選址模型與算法研究》采用的是基本遺傳算法，張培林，魏巧云[11]的論文 《物流配送中心選址模型及其啟發(fā)式算法》中采用的是啟發(fā)式方法，馬正元，黃斌[12]的論文 《Hopfield人工神經(jīng)網(wǎng)絡(luò)在物流配送中心選址優(yōu)化中的應(yīng)用》中應(yīng)用的是神經(jīng)網(wǎng)絡(luò)，此外，還有的采用模擬退火算法，模糊控制方法等。

1 K-means聚類算法原理

K-means算法[13]首先隨機(jī)選取K個(gè)點(diǎn)作為初始聚類中心，然后計(jì)算各個(gè)樣本到聚類中心的距離，把樣本歸到離它最近的那個(gè)聚類中心所在的類。常用的聚類準(zhǔn)則函數(shù)Jc定義如下：

其中Zk為第k個(gè)聚類中心，）為樣本到對(duì)應(yīng)聚類中心距離，聚類準(zhǔn)則函數(shù)Jc即為各類樣本到對(duì)應(yīng)聚類中心距離的總和，這里）為歐式空間的距離，這個(gè)準(zhǔn)則試圖找出令平分誤差函數(shù)最小的k個(gè)劃分，使得生成的結(jié)果簇盡可能地緊湊和獨(dú)立。

該算法的框架如下： （1）給出n個(gè)混合樣本分成m類，令I(lǐng)=1，選取k個(gè)初始聚類中心Zk（）I； （2）計(jì)算每個(gè)樣本到聚類中心的距離d（ Xi,Zk（I ））,i=1,2,…,n,k=1,2,…,m， 如果滿足則 Xi=wj； （3） 計(jì)算m個(gè)新的聚類中心（4） 判斷則 I =I+1， 返回 （2）， 否則，算法結(jié)束。

該算法中，整個(gè)聚類過(guò)程的時(shí)間復(fù)雜度為O nm（）d ，n指樣本點(diǎn)個(gè)數(shù)，m是指定的聚類個(gè)數(shù)，d樣本點(diǎn)的維數(shù)。其中將每個(gè)樣本分到離它最近的聚類中心的復(fù)雜度是新的分類產(chǎn)生以后計(jì)算新的聚類中心的時(shí)間復(fù)雜度是

2 模型建立

本章采用基于K-means聚類的基本原理，劃分一級(jí)配送中心及其區(qū)域，需要根據(jù)需求點(diǎn)的地理位置進(jìn)行聚類，這樣的目的是為了確定銷售區(qū)域后，在每個(gè)銷售區(qū)域建立相應(yīng)的配送中心，取代點(diǎn)對(duì)點(diǎn)配送，從而達(dá)到降低配送成本的目的。

在聚類確定配送中心的位置時(shí)，采用總體配送距離為評(píng)價(jià)指標(biāo)來(lái)對(duì)配送中心的個(gè)數(shù)及位置進(jìn)行確定。建立數(shù)學(xué)模型如下：

其中，S——所有需求點(diǎn)的集合，Gi——第i個(gè)配送區(qū)域，Dij——配送中心i到需求點(diǎn)j的距離，D*i——配送中心i到工廠的距離，dj——需求點(diǎn)j的年需求量，fj——需求點(diǎn)j的配送頻率，F(xiàn)i——工廠到配送中心i配送頻率；δij關(guān)于工廠到配送中心i配送頻率Fi的確定是根據(jù)經(jīng)濟(jì)批量模型 （EOQ）[14]進(jìn)行理論分析得到的：

其中，C1——單位車輛的存儲(chǔ)成本，配送區(qū)域的訂貨成本，配送區(qū)域銷售旺季的需求量，配送區(qū)域正常銷售季節(jié)的需求量，i為配送區(qū)域銷售淡季的需求量，配送區(qū)域銷售旺季的時(shí)間，配送區(qū)域正常銷售季節(jié)的時(shí)間，i配送區(qū)域銷售淡季的時(shí)間。

3 配送中心位置確定

對(duì)于已確定的Gi配送區(qū)域來(lái)說(shuō)，配送中心的位置對(duì)于整個(gè)配送的運(yùn)輸距離是十分重要的，主要通過(guò)計(jì)算工廠到每個(gè)配送中心的距離以及配送中心到相鄰的配送點(diǎn)的距離，找出距離之和最短的做為配送中心，并可以確定相應(yīng)的配送區(qū)域。該方法數(shù)學(xué)表示如下： （1）首先作為Gi的配送中心位置，它到Gi內(nèi)其他點(diǎn)的距離記為Dij，它的工廠的距離記為計(jì)算距離，此時(shí)為該Gi區(qū)域產(chǎn)生的總的運(yùn)輸距離（3）判斷Min（ Tem ） ， 如果是最小值，則將該點(diǎn)記做Gi的配送中心位置， 否則，返回 （2） 重新計(jì)算。 則，返回 （2） 重新計(jì)算。

4 配送中心個(gè)數(shù)及配送區(qū)域確定

在確定配送中心的個(gè)數(shù)時(shí)，首先確定配送中心個(gè)數(shù)的范圍，將該范圍內(nèi)的配送中心都進(jìn)行聚類分析，得到相應(yīng)的運(yùn)輸距離，然后找到使運(yùn)輸距離最小的配送中心個(gè)數(shù)，從而使配送中心的個(gè)數(shù)的確定更具有科學(xué)依據(jù)，并且對(duì)所得結(jié)果進(jìn)行深入的分析，使之更符合實(shí)際情況。

具體求解步驟如下：

（1）設(shè)置參數(shù)：配送中心個(gè)數(shù)k的取值范圍，k∈［1,n ］ ，迭代評(píng)價(jià)指標(biāo)ε=20km； （2）初始化聚類中心，即從s中隨機(jī)選擇k個(gè)點(diǎn)c1,c2,…,ck作為k個(gè)聚類集合的中心點(diǎn)； （3）以c1,c2,…,ck為中心點(diǎn)進(jìn)行集合劃分，劃分的原則是：如果則將xi劃分到Gj中； （4）計(jì)算每個(gè)劃分區(qū)域Gi產(chǎn)生的配送距離Tem（ k,i）=Dij+D*i，其中，Tem（ k,i）——配送中心個(gè)數(shù)為k時(shí)第i個(gè)配送區(qū)域的配送距離，D*i——配送區(qū)域中心點(diǎn)ci到工廠的距離，Dij——ci到配送區(qū)域Gi內(nèi)其它點(diǎn)距離之和； （5）計(jì)算所有配送區(qū)域總配送里程Tem（k ） 表示配送中心個(gè)數(shù)為k時(shí)的總配送里程； （6）根據(jù)劃分區(qū)域計(jì)算新的中心點(diǎn)其中： i,j=1,2,…,k， n為i集合中Gi的點(diǎn)的個(gè)數(shù)； （7）如果則當(dāng)前配送中心個(gè)數(shù)為k的計(jì)算結(jié)束，令k=k+1，返回 （2）重新計(jì)算直到k=125，當(dāng)前中心點(diǎn)為聚類劃分的結(jié)果；否則令返回 （3）重新進(jìn)行計(jì)算； （8）判斷min（ Te m （ k）），可以得到最小配送距離的配送中心個(gè)數(shù)k*，相應(yīng)的可以得到該配送方式下的配送區(qū)域G,G,…,G，每個(gè)配送區(qū)域的配送中心

12k*

5 實(shí) 證

國(guó)內(nèi)某汽車制造企業(yè) （為方便計(jì)算，生產(chǎn)和發(fā)運(yùn)地假設(shè)為哈爾濱市）的銷售物流業(yè)務(wù)，旺季情況：每年11月至次年2月為旺季運(yùn)輸，是正常運(yùn)輸運(yùn)力需求的200%；每年5~7月為淡季運(yùn)輸，是正常運(yùn)輸運(yùn)力需求的50%；其他為正常運(yùn)輸；運(yùn)費(fèi)標(biāo)準(zhǔn)：每輛商品車的運(yùn)費(fèi)為1 200元，即1 200元/輛；訂單周期：假設(shè)為2周一次。企業(yè)生產(chǎn)ABCD四種車型，只有A車型不能通過(guò)鐵路運(yùn)輸方式，其他都可以通過(guò)公路、鐵路、水路三種方式運(yùn)輸。具體數(shù)據(jù)如下：

表1 運(yùn)輸設(shè)備數(shù)據(jù)

表2 國(guó)內(nèi)銷售信息 單位：臺(tái)

表3 成本費(fèi)用表

（1）所選城市分布圖

所選城市分布的原則是選擇具有代表性的二級(jí)城市，這些二級(jí)城市能覆蓋全省且消費(fèi)能力較高。從全國(guó)所有省市中選取了125個(gè)城市作為二級(jí)城市，由圖1可以看出，這些城市基本上能覆蓋整個(gè)中國(guó)。

根據(jù)以上的求解步驟，采用matlab編程對(duì)模型求解，求解結(jié)果表明當(dāng)選擇配送中心個(gè)數(shù)為17個(gè)的時(shí)候，所得到的總的運(yùn)輸距離最小，整個(gè)配送距離如圖2所示，由圖可知該求解步驟可以很好地解決K-means聚類方法中的初始聚類中心個(gè)數(shù)難以確定的缺點(diǎn)，通過(guò)變化初始聚類中心的個(gè)數(shù)，可以得到不同聚類中心個(gè)數(shù)下的配送里程，從中找出一個(gè)最優(yōu)的配送方案。

（2）物流成本計(jì)算

圖2 配送中心個(gè)數(shù)與總體運(yùn)輸距離曲線

倉(cāng)儲(chǔ)成本假設(shè)[15]：計(jì)算倉(cāng)庫(kù)面積＝車輛占地面積×寬裕系數(shù)，本問(wèn)題中寬裕系數(shù)取1.2；人員配備：每100平方米配備一個(gè)人員，其工資水平假定每人年薪2萬(wàn)元；倉(cāng)庫(kù)維護(hù)費(fèi)用：每平方米年維護(hù)費(fèi)用為15元；保險(xiǎn)費(fèi)用：倉(cāng)庫(kù)存貨價(jià)值×0.2%；汽車損失費(fèi) （倉(cāng)儲(chǔ)導(dǎo)致的汽車價(jià)值損失）：倉(cāng)庫(kù)存貨價(jià)值×0.3%。

運(yùn)輸成本假定：汽油費(fèi)用：卡車每公里汽油費(fèi)1.1元；汽車修理費(fèi)：運(yùn)輸專用汽車價(jià)值的8%；汽車保險(xiǎn)費(fèi)：運(yùn)輸中車輛的價(jià)值×0.3%；汽車折舊費(fèi)：年折舊率10%；司機(jī)費(fèi)用：每車配備兩司機(jī)，其工資水平每個(gè)司機(jī)年薪2.5萬(wàn)元。

按照上述條件計(jì)算后的點(diǎn)對(duì)點(diǎn)的運(yùn)輸方式成本：327 307 222元；按照優(yōu)化后的配送中心配送方式的運(yùn)輸成本：235 030 995元；成本節(jié)約28.19%，可知，該配送方案經(jīng)濟(jì)可行。

6 對(duì)基于K-means算法優(yōu)化過(guò)程的深入探討

在優(yōu)化的過(guò)程中，由于初始的中心點(diǎn)是隨機(jī)生成的，這樣在聚類的過(guò)程中就有可能使聚類的結(jié)果受到初始隨機(jī)選定的中心的影響而過(guò)早地收斂于次優(yōu)解。所以針對(duì)這個(gè)問(wèn)題在本文中通過(guò)讓程序迭代足夠多次的方法來(lái)減小這方面的誤差，如圖4所示，這是當(dāng)聚類數(shù)為17時(shí)的求解過(guò)程跟蹤曲線，從中可以看到，在迭代的過(guò)程中解的大小有著隨機(jī)分布的特征，但是當(dāng)?shù)銐蚨嗟拇螖?shù)時(shí)，就可以找到一個(gè)相當(dāng)最優(yōu)的解 （此算例在第959次迭代時(shí)找到相對(duì)最優(yōu)解），這也說(shuō)明本文中所使用的方法在實(shí)際中是有效的，而且與遺傳算法等相比相對(duì)經(jīng)濟(jì)了一些。

7 結(jié) 論

（1）通過(guò)以上成本計(jì)算可知，該方法是切實(shí)可行的并且能節(jié)約成本；

（2）和傳統(tǒng)的配送中心選址問(wèn)題相比，將智能算法引入可以更好地解決節(jié)點(diǎn)較多的配送中心選址問(wèn)題；

（3）在采用聚類算法的過(guò)程中，首先通過(guò)配送距離最短的尋優(yōu)方法得到配送中心個(gè)數(shù)，然后再對(duì)配送中心進(jìn)行區(qū)域劃分，更好地解決了K-means算法不能初始聚類中心個(gè)數(shù)問(wèn)題；

（4）當(dāng)然，該算法存在緯度問(wèn)題，當(dāng)問(wèn)題隨著配送中心個(gè)數(shù)增多是，其時(shí)間復(fù)雜度和空間復(fù)雜度呈指數(shù)級(jí)增長(zhǎng)。

[1] 楊海榮.現(xiàn)代物流系統(tǒng)與管理[M].北京：北京郵電大學(xué)出版社，2003:1-81.

[2] 齊二石，趙道致.物流工程[M].北京：中國(guó)科學(xué)技術(shù)出版社，2005:160-167.

[3] 王燕，蔣笑梅.配送中心全程規(guī)劃[M].北京：機(jī)械工業(yè)出版社，2004:83-108.

[4] C.H.Aikens.Facility location models for distribution planning[J].European J.Oper.Res,1985(22):263-279.

[5] J.E.Hodder,M.C.Dincer.A multifactor model for international plant location and financing under uncertainty[J].Comput.&Oper.Res,1986,13(5):601-609.

[6] J.A.Tompkins,J.A.White.Facilities Planning[M].Wiley,New York,1984.

[7] G.A.Spohrer,T.R.Kmak.Qualitative analysis used in evaluating alternative plant location scenarios[J].Indust.Eng,1984(8):52-56.

[8] W.J.Stevenson.Production Operations Management[M].Richard D.Irwin Inc,Illinois,1993.

[9] 劉海燕，李宗平，葉懷珍.物流配送中心選址模型[J].西南交通大學(xué)學(xué)報(bào)，2000(6):311-314.

[10] 陳曦，傅明.GIS環(huán)境下的物流配送中心選址模型與算法研究[J].計(jì)算技術(shù)與自動(dòng)化，2001,20(4):6-9.

[11] 張培林，魏巧云.物流配送中心選址模型及其啟發(fā)式算法[J].交通運(yùn)輸工程學(xué)報(bào)，2003(6):65-68.

[12] 馬正元，黃斌.Hopfield人工神經(jīng)網(wǎng)絡(luò)在物流配送中心選址優(yōu)化中的應(yīng)用[J].組合機(jī)床與自動(dòng)化加工技術(shù)，2003(3):24-26.

[13] 馬漢武.設(shè)施規(guī)劃與物流系統(tǒng)設(shè)計(jì)[M].北京：高等教育出版社，2005:270-274.

[14] 胡運(yùn)權(quán),等.運(yùn)籌學(xué)教程[M].2版.北京：清華大學(xué)出版社，2003.

[15] 韓崗.如何進(jìn)行倉(cāng)儲(chǔ)物料管理[M].北京：北京大學(xué)出版社，2004.