基于改進(jìn)的K-means聚類的多區(qū)域物流中心選址算法①

魯玲嵐， 秦江濤

(上海理工大學(xué) 管理學(xué)院，上海 200093)

區(qū)域配送中心配送規(guī)模較大，用戶較多，是物流中重要節(jié)點. 其合理的物流規(guī)劃不僅關(guān)系到是否能達(dá)到資源利用的效益最大化，滿足客戶的物流需求，保證物流時效性，也決定著投入物流成本的高低. 多區(qū)域物流配送中心選址需確定配送中心最佳數(shù)目、位置及覆蓋范圍. 聚類算法將一整個區(qū)域劃分，以此來確定配送中心數(shù)目以及其覆蓋范圍，非常適用于多配送中心的選址問題. 諸如K-means的聚類算法通常用于多區(qū)域配送中心的選址，但它們的初始聚類中心是隨機的，易陷入局部極小解，且K值不同導(dǎo)致聚類效果各異[1]，并且有些城市地處偏僻，常被作為噪音數(shù)據(jù)排除，最主要的是由于山川、河流的阻礙，兩地之間的歐式距離并不能用來衡量實際的運輸距離.

1 目前主要K-means聚類劃分方法綜述

K-means聚類算法技術(shù)較為成熟，操作便捷，經(jīng)常被用于選址中對區(qū)域的劃分上. 考慮到該聚類方法對區(qū)域劃分時存在的劣勢，許多學(xué)者對該聚類方法進(jìn)行了改進(jìn). 朱培芬結(jié)合密度的思想，在可選范圍中優(yōu)先考慮邊緣點，具有良好的全局收斂性[2]，但并未科學(xué)衡量距離因子，也未曾考慮物流需求等重要影響因子. 谷煒提出兩階段K-means聚類算法，在傳統(tǒng)K-means聚類后，通過不斷迭代來檢驗是否滿足配送時間最少的收斂條件，最終確定聚類結(jié)果[3]，避免了算法陷入局部最優(yōu)，但不斷的迭代大大增加了算法的運算時間. 于曉寒考慮到河流、公路等地理障礙，以“障礙距離”為差異度量標(biāo)準(zhǔn)，站點工作量為約束，提出基于障礙距離的約束聚類算法[4]，但距離并不是簡單的空間距離，雖其在抽象意義上是同質(zhì)的，但諸如城市這樣實質(zhì)的經(jīng)濟主體，距離明顯包含了更多的非空間因素.

本文針對選址的實際情況，以城市經(jīng)濟引力模型為基礎(chǔ)，考慮到距離的“非空間因素”，重新定義了對象間度量距離的因子. 同時把密度的思想引入K-means算法以解決K值不確性問題，并提出類內(nèi)差分均值的概念確定最優(yōu)聚類數(shù). 借助改進(jìn)的K-means聚類算法完成西北地區(qū)物流網(wǎng)絡(luò)的劃分，實現(xiàn)分區(qū)后，分別在這些區(qū)域中利用重心法對配送中心進(jìn)行最終的確定. 并通過和傳統(tǒng)K-means聚類結(jié)果對比，來驗證改進(jìn)后方法更優(yōu).

2 改進(jìn)的K-means聚類算法和重心法

2.1 改進(jìn)K-means聚類對區(qū)域劃分

(1) 將密度思想引入K-means算法

基于傳統(tǒng)K-means算法易受噪聲和孤立點影響的事實，本文將密度的思想引入K-means算法來確定k個聚類中心. 不僅可以避免噪聲數(shù)據(jù)干擾，而且可以有效降低算法時間復(fù)雜度. 考慮到M維空間的n維數(shù)據(jù)點Xi(i=0,1,2,···,n-1) 其基本思路如下：計算每個數(shù)據(jù)點Xi的密度. j=0,1,2···n-1. ra為正數(shù)，定義為該點的領(lǐng)域半徑，取當(dāng)i取一個值時，k=0,1,2,···,n-1，Xi的密度指標(biāo)記為Di具體計算公式如下：

根據(jù)式(1)獲取所有樣本點的密度指數(shù)，按照從大到小的順序排列，選取前k個數(shù)據(jù)點作為聚類中心.

(2) 基于經(jīng)濟引力模型對距離的定義

在度量兩個城市之間相似度的過程中，把距離的概念僅定義為兩個城市間的空間距離是不可取的，為了更科學(xué)的衡量距離且更加有效的運用于實際情況，本文以居民可支配收入作為衡量城市間的經(jīng)濟引力因子，交通運輸時間作為衡量城市間的距離因子. 相應(yīng)的公式如下：

式(2)中MiMj分別為城市i 和城市j的居民人均可支配收入指標(biāo). 居民人均可支配收入是衡量居民消費能力的重要指標(biāo)，在消費性支出中包括食品煙酒、衣著、居住、生活用品以及其他用品和服務(wù). 隨著科技的進(jìn)步，出現(xiàn)了越來越多樣化的消費渠道. 這里主要考慮線上和線下消費. 在物流網(wǎng)絡(luò)建設(shè)不完善的地區(qū)，居民線上消費遇到較大限制，消費被迫轉(zhuǎn)到線下，這些地區(qū)物流需求遠(yuǎn)遠(yuǎn)不及實際的消費需求，用居民的可支配收入來衡量物流需求更為現(xiàn)實. Dij為城市i和城市j的交通距離，本文以車輛在兩座城市之間行駛一趟的交通時間來衡量. u作為調(diào)節(jié)物流網(wǎng)絡(luò)劃分時受地區(qū)居民消費水平影響的程度. 一般來說，u越大，則說明在區(qū)域物流網(wǎng)絡(luò)劃分時，各地區(qū)的居民消費水平的吸引力占主導(dǎo)地位，城市間的距離因素被較大程度的弱化; 反之u越小，則認(rèn)為各地區(qū)的居民消費水平影響較弱，城市間的距離因素主導(dǎo)地位越強; u為0時，距離等價于歐式距離.

(3) k值的確定

聚類的目的是使同一類的樣本點間相似度高，而不同類間相似度低. 為精確測量聚類結(jié)果，進(jìn)一步確定k值. 本文采用計算類內(nèi)差分均值的評估方法. 計算樣本點與各自聚類中心的距離之和的平均值. 值越小，總的聚類距離越小，類間相似度越高，聚類效果越好; 反之，值越大，聚類距離越大，類間相似度越低，聚類效果越差. 用內(nèi)類差均值的方法衡量最佳聚類個數(shù)，以達(dá)到修建最少的配送中心實現(xiàn)最大區(qū)域的覆蓋.

2.2 重心法

重心法是一種簡單可行的選址方法，通常用于解決連續(xù)點的單個配送中心選址問題，其唯一的決策依據(jù)是運輸成本. 應(yīng)用時，它對候選位置沒有任何限制，在已知各個備選地點的位置、物流需求量、各個備選地點的直線距離的前提下，運用重心法可以很好地確定配送中心的位置. 其運算方便，計算速度快，通過幾次迭代就能計算出理論位置. 但此種方法只適用于確定單一配送中心，對于確定多個配送中心的選址問題，此法并不適用[5].

3 多區(qū)域配送中心選址模型

針對多區(qū)域配送中心選址問題，本文采用目前比較主流的兩階段模型：第一階段把所有的需求點劃分為若干個配送區(qū)域，第二步階段選取相應(yīng)區(qū)域中最佳配送中心[6-8]. 借助該模型的選址步驟，本文首先用改進(jìn)的k-means聚類對區(qū)域進(jìn)行劃分，確定需建立配送中心的個數(shù)以及其配送范圍. 然后運用重心法在劃分的區(qū)域中選取合適的配送中心位置.

3.1 基于改進(jìn)的K-means聚類對區(qū)域劃分

本文運用MyEclipse Professional 2014軟件，采用JAVA語言，在Win10 64位系統(tǒng)環(huán)境下運行.其中按照樣本大小和聚類個數(shù)k值的關(guān)系，這里n為樣本的大小. 具體操作步驟如下：

1) 存儲數(shù)據(jù)，對數(shù)據(jù)進(jìn)行歸一化處理.

2) 按照式(1)計算城市密度，按密度從大到小的順序排列，取排序前m個城市作為聚類中心候選點.

3) 取前k個候選點作為聚類中心，按照式(2)計算當(dāng)k取不同值時的距離因子，這里u=0.1，當(dāng)u=0.1時，最能科學(xué)均衡經(jīng)濟引力與距離之間的影響力. 按照最小距離原則分配n-k 個城市樣本. 得到種聚類結(jié)果.

5)結(jié)束，輸出最優(yōu)聚類結(jié)果.

3.2 重心法對單一區(qū)域配送中心選址

在上一階段過程中確定了配送中心的個數(shù)以及其覆蓋范圍的問題，但聚類過程中選取的聚類中心僅僅考慮到了城市交通的密度，而未考慮其他因素，不足以認(rèn)為是最合適的配送中心地址. 需結(jié)合單一配送選址模型在各個區(qū)域中對聚類中心進(jìn)行修正，從而確定單一區(qū)域配送中心的最佳位置，本文選取重心法來進(jìn)行此階段工作.

4 評估模型建立

區(qū)域物流中心選址模型是帶有復(fù)雜約束的非線性規(guī)劃模型，在構(gòu)建評估模型時先明確如下假設(shè)：(1) 中心容量總是可以滿足所覆蓋需求點的需求量，并由該中心供應(yīng)的所有單位的需求量確定. (2) 一個需求點僅由一個物流配送中心供應(yīng). (3) 從物流中心到需求點通過零擔(dān)物流的方式進(jìn)行配送，且不考慮裝載的問題，僅以最大車載量進(jìn)行運算. (4) 運輸費用僅由運價、實際運輸路程決定，不考慮裝卸等人工成本. (5) 配送中心每輛車每天僅往需求點配送一趟. 基于以上5條假設(shè)建立衡量選址是否有效的模型. 目標(biāo)函數(shù)是各個配送中心到需求點的運輸費用之和最小，目標(biāo)函數(shù)為：

式(3)中i表示配送中心，其取值為0,1,2,···,k-1,k表示配送中心個數(shù). j為配送中心所供應(yīng)需求點個數(shù)，Ni表示第i個配送中心需求點集合. mij表示配送中心i到需求點j的計費里程，以km為單位. wij表示配送中心i到需求點j運輸貨物的重量，以kg為單位. J表示從配送中心i到需求點j的單位運價，以元/kg*km為單位.

5 實例分析

5.1 數(shù)據(jù)來源與處理

西北地區(qū)地域廣闊，自然資源豐富，但地區(qū)天氣惡劣，城市之間道路險阻較多，交通十分不便，物資運輸上的不便是西北地區(qū)電子商務(wù)的發(fā)展主要阻礙. 本文對西北物流網(wǎng)絡(luò)進(jìn)行研究，由于新疆地區(qū)地域物流管理體制較混亂，機構(gòu)多元化，多采用外包的物流模式，這里主要討論除新疆之外的37個地級市的物流區(qū)域配送中心選址問題. 本次共采集37個城市間交通時間數(shù)據(jù)共703條記錄. 選取甘肅、青海、陜西、寧夏2016年的統(tǒng)計年鑒中選取四省的城鎮(zhèn)居民可支配收入. 并對已有數(shù)據(jù)進(jìn)行了歸一化處理，來消除數(shù)據(jù)量綱的影響.

為驗證方法的正確性和實用性，抽象實驗數(shù)據(jù)為：零擔(dān)運輸?shù)臋C動車輛車身均為5～7米，車載量20 000 kg，平均行駛速度68 km/h. 考慮到西北地區(qū)一體化趨勢日益明顯，可忽略地域的運價費用差異，這里單位運價均定1元/kg*km. 通過城鎮(zhèn)居民可支配收入折算成每日的需求量以及配送所需車輛如表1所示.

表1 城鎮(zhèn)每日物流需求量以及所需配送車輛量化表

5.2 改進(jìn)方法選址求解

(1) 確定聚類中心候選點，本文取前10位城市以及相應(yīng)密度，從結(jié)果看出，嘉峪關(guān)、酒泉、西安等作為當(dāng)前交通的樞紐中心，是聚類中心的首選. 在區(qū)域劃分中把密度思想引入是合理有效的. 結(jié)果如表2如下.

表2 前10城市密度

(2) 通過類內(nèi)差分均值評估，繪制曲線圖觀察最適k值. 從折線圖很直觀看出，當(dāng)k=6時，曲線出現(xiàn)拐點，達(dá)到最小值，當(dāng)k=7，8時類內(nèi)差均值小范圍增加，證明當(dāng)建立6個配送中心時物流網(wǎng)絡(luò)已經(jīng)達(dá)到了較好的覆蓋效果. 隨著配送中心的增多，覆蓋效果反而降低. 即當(dāng)37個城市被分為6類時，類間的相似度越高，聚類結(jié)果越好. 如圖1所示.

確定最佳聚類個數(shù)后，根據(jù)改進(jìn)的K-means算法聚類，當(dāng)k=6時，聚類結(jié)果如表3所示.

圖1 3～8個聚類的類內(nèi)差分均值

表3 k=6時的城市分區(qū)結(jié)果

(3) 把每個區(qū)域中城市作為物流服務(wù)需求點，人均可支配收入作為需求量，用重心法修正的配送中心結(jié)果如下，區(qū)域一：張掖，區(qū)域二：寶雞，區(qū)域三：嘉峪關(guān)，區(qū)域四：銅川市，區(qū)域五：共和縣，區(qū)域六：白銀.配送中心地址及其輻射區(qū)域如圖2所示.

圖2 西北四省配送中心地址及其覆蓋城市圖

5.3 結(jié)果評估

本文參照傳統(tǒng)的K-means算法對配送中心選址結(jié)果進(jìn)行對比. 在傳統(tǒng)的K-means算法中把城市之間的直線距離作為相似性度量的因子，以每個城市之間的經(jīng)緯度計算城市距離，設(shè)置k=6，閾值為0.000 001，共迭代50次，得到區(qū)域劃分后，再用重心法選出各個區(qū)域的配送中心. 以式(3)計算運輸成本，實驗結(jié)果如表4所示.

表4 配送中心選址效果對比

從配送中心選址效果對比中可以看出，對比傳統(tǒng)的K-means聚類算法，改進(jìn)后的算法每天可節(jié)約運輸成本41 626 420元，配送時間可節(jié)省30.62小時. 在保證配送時效的同時也節(jié)約了運輸成本，在一定程度上說明改進(jìn)后的算法較傳統(tǒng)的算法在實際中能創(chuàng)造更好的經(jīng)濟效益.

6 結(jié)論

通過本文分析，得出以下結(jié)論：在進(jìn)行區(qū)域劃分時，考慮當(dāng)?shù)氐膶嶋H情況越來越受到學(xué)者們的重視，本文以城市運輸距離與居民消費能力的指標(biāo)相結(jié)合，重新定義了對象間的相似性度量的距離因子，區(qū)域劃分后后，利用重心法對聚類中心進(jìn)行修正，科學(xué)的選出了每個區(qū)域內(nèi)的配送中心，更符合西北地區(qū)發(fā)展的實際情況. 為了驗證改進(jìn)方法的有效性，本文對比傳統(tǒng)Kmeans聚類對區(qū)域進(jìn)行劃分后選址結(jié)果，實驗可知：較傳統(tǒng)的K-means聚類，改進(jìn)后的算法不僅節(jié)省了配送時間，而且大大降低了運輸成本，具有很好的實際運用價值，為西北物流建設(shè)提供了參考. 但本文考慮的是西北地區(qū)這一宏觀的區(qū)域性概念，還有地處偏僻的部落并未考慮在內(nèi)，因此劃分的區(qū)域未能全部覆蓋，想要在西北地區(qū)完成物流的全部覆蓋及其布局，還需要一些發(fā)展的契機，有待以后學(xué)者們?nèi)ヌ剿?