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

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

1 K-means聚類算法原理

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

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

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

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

2 模型建立

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

在聚類確定配送中心的位置時，采用總體配送距離為評價指標來對配送中心的個數(shù)及位置進行確定。建立數(shù)學模型如下：

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

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

3 配送中心位置確定

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

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

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

具體求解步驟如下：

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

12k*

5 實 證

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

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

表2 國內銷售信息 單位：臺

表3 成本費用表

（1）所選城市分布圖

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

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

（2）物流成本計算

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

倉儲成本假設[15]：計算倉庫面積＝車輛占地面積×寬裕系數(shù)，本問題中寬裕系數(shù)取1.2；人員配備：每100平方米配備一個人員，其工資水平假定每人年薪2萬元；倉庫維護費用：每平方米年維護費用為15元；保險費用：倉庫存貨價值×0.2%；汽車損失費 （倉儲導致的汽車價值損失）：倉庫存貨價值×0.3%。

運輸成本假定：汽油費用：卡車每公里汽油費1.1元；汽車修理費：運輸專用汽車價值的8%；汽車保險費：運輸中車輛的價值×0.3%；汽車折舊費：年折舊率10%；司機費用：每車配備兩司機，其工資水平每個司機年薪2.5萬元。

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

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

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

7 結 論

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

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

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

（4）當然，該算法存在緯度問題，當問題隨著配送中心個數(shù)增多是，其時間復雜度和空間復雜度呈指數(shù)級增長。

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

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

[3] 王燕，蔣笑梅.配送中心全程規(guī)劃[M].北京：機械工業(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].西南交通大學學報，2000(6):311-314.

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

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

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

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

[14] 胡運權,等.運籌學教程[M].2版.北京：清華大學出版社，2003.

[15] 韓崗.如何進行倉儲物料管理[M].北京：北京大學出版社，2004.