魯玲嵐， 秦江濤

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

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

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

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

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

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

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

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

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

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

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

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

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

(3) k值的確定

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

2.2 重心法

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

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

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

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

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

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

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

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

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

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

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

4 評(píng)估模型建立

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

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

5 實(shí)例分析

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

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

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

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

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

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

表2 前10城市密度

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

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

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

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

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

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

5.3 結(jié)果評(píng)估

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

表4 配送中心選址效果對(duì)比

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

6 結(jié)論

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