基于改進的K-means聚類的多區域物流中心選址算法①

魯玲嵐， 秦江濤

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

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

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

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

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

2 改進的K-means聚類算法和重心法

2.1 改進K-means聚類對區域劃分

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

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

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

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

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

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

(3) k值的確定

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

2.2 重心法

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

3 多區域配送中心選址模型

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

3.1 基于改進的K-means聚類對區域劃分

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

1) 存儲數據，對數據進行歸一化處理.

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

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

5)結束，輸出最優聚類結果.

3.2 重心法對單一區域配送中心選址

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

4 評估模型建立

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

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

5 實例分析

5.1 數據來源與處理

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

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

表1 城鎮每日物流需求量以及所需配送車輛量化表

5.2 改進方法選址求解

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

表2 前10城市密度

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

確定最佳聚類個數后，根據改進的K-means算法聚類，當k=6時，聚類結果如表3所示.

圖1 3～8個聚類的類內差分均值

表3 k=6時的城市分區結果

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

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

5.3 結果評估

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

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

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

6 結論

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