基于K-means算法和集合覆蓋模型的維修站選址

張守京，李夢丹

（西安工程大學 機電工程學院，陜西 西安 710048）

1 引言

目前，我國汽車市場正面臨著總體市場空間不斷擴大的良好機遇，同時汽車工業的高速發展也帶來了售后服務基礎設施的缺乏問題和對售后服務的高需求和個性化要求，使得企業之間的競爭也日益激烈。由于我國汽車售后服務發展滯后，給汽車工業的發展帶來了一定的阻礙。在汽車行業激烈的競爭中，競爭的焦點已不僅僅限于產品和價格，同時，要善于發現和了解顧客需求，創造服務差異化，不斷完善售后服務體系以提高客戶滿意度，因此建立服務站就顯得尤為重要。加快服務站建設對重卡汽車的發展同樣具有十分重要的意義，因此本文在滿足服務需求的基礎上對此展開研究。

選址是一個傳統的話題，涉及方方面面，例如公共設施[1]、售后服務站[2-4]、物流配送中心[5-8]、加油站[9]、充電站[10-11]等設施的選址，合適的選址不僅可以降低成本，同時還可以提高顧客滿意度。維修服務站是售后服務系統的核心部分，因此選擇合適的方法就顯得尤為重要。集合覆蓋模型[12-16]在選址問題中是一種比較常用的模型，可以在成本最小的情況下達到最大的顧客滿意度。該模型可以結合傳統的線性規劃，利用LINDO 軟件求解以及采用科學的評價方法[17]，也可以利用啟發式算法如粒子群算法[18]、聚類算法進行選址[19]，使結果更加具有科學性。新興的數據挖掘[20-21]也可以給選址提供一定的思路，可以結合車聯網信息，利用地理信息系統[22-23]相關軟件直觀的顯示需求地點并進行數據分析。

已經有許多學者對選址做了大量研究，但是基于大數據的維修服務站選址相對較少。許多企業在服務站的建設方面都是依據以往經驗，忽略了需求量與建站數量相一致的原則，這就造成了一定的資源浪費，部分地區設施因需求小而閑置，部分設施因需求大而不能滿足當前維修需求。為滿足用戶需求，建立車聯網大數據信息管理平臺對車輛的運行軌跡以及維修等進行記錄與管理，通過對海量數據的挖掘與分析，歸納客戶需求，將有助于維修服務站的選址。本文利用k-means 算法對車聯網數據進行聚類分析，結合集合覆蓋模型對重卡維修服務站展開選址。

圖1 維修站選址研究流程

2 研究方法及流程

2.1 研究流程

維修站選址，即基于車輛行駛軌跡以及歷史維修記錄等大數據，通過采取數據、分析整理、歸納總結等，選擇合適的維修服務站點，旨在第一時間滿足客戶需求，提高客戶滿意度，打造高標準服務體驗。本文首先對數據進行區域劃分，采用K-means 算法進行聚類，然后在某區域中進行集合覆蓋選址，依此類推，得到全國范圍內的選址方案。研究流程如圖1所示。

2.2 K-means算法區域聚類

本文所要分析的數據量相對較大，屬于空間地理位置信息，因此采用K-means 算法對其進行分析與歸類，將某一區域內距離較近的點劃分為一個區域（即將具有相似特征的點歸為一類）。

K-means 聚類算法是聚類分析在現實應用中最重要的算法，它能夠快速有效地處理較大的數據集合。K-means算法根據聚類的個數K，將已有的數據集劃分成K個簇，算法采用迭代更新的方法，在第一輪中，根據隨機選定的K 個初始中心點將對象集劃分成K 個初始簇，之后根據每個簇的中心迭代重新劃分每個對象所屬的類，而每個簇的平均值將被作為下一輪迭代的中心點，直到中心點不再發生改變，即產生了最后的聚類結果。K 表示類的數量；K-means可以自動分配樣本到不同的類，但是不能決定究竟要分幾個類。K 必須是一個比訓練集樣本數小的正整數。K-means 算法常采用誤差平方和準則函數作為聚類準則函數，定義為:

其中，Mi是類Ci中全部數據對象的均值，p是類Ci中的每個數據對象?？梢钥闯?，Jc是樣本和聚類中心的函數。在樣本集給定的情況下，Jc的值取決于K個聚類中心Mi。Jc描述了n個樣本聚類成K個類型時所產生的總的誤差平方和。顯然，若Jc值越大，說明誤差越大，聚類結果不好，因此尋求使Jc最小的聚類結果，即在誤差平方和準則下的最優結果。

本文利用K-means 算法將全國范圍內的車輛需求點進行聚類分析，在給定K值的情況下，找到一個點使某區域內所有點到達該點的距離最小，該點即為聚類中心。該區域內的點具有一定的相似特征，即該區域內的需求點為一類。

2.3 集合覆蓋模型

在利用K-means 算法對數據進行聚類分析的基礎上，對車輛所行駛的軌跡進行了區域劃分，接下來根據分類結果，在給定的選址區域內使用特定的選址模型求出模型的可行解，并從中選擇最符合目標函數的一組作為模型的最優解，轉化為實際選址問題的結果。以聚類結果中數量最多的一個區域為例，做出區域內選址。維修站的建設目的在于可以快速高效的為行駛的車輛提供各種服務，因此建立的維修站應滿足以下需求：建立的維修站可以滿足全部的需求點，同時考慮顧客滿意度最大，因此考慮使用覆蓋模型進行求解。

對于大多數的覆蓋類選址問題，可以敘述如下：已知需求點集合和潛在的設施點集合，對于給定的服務半徑，①設施點的數量無限制時，要求尋找一種設施點的配置方式，使得使用最少的服務設施以覆蓋所有的需求點；②給定設施點數量時，要求找到一種設施點配置方式，使得其覆蓋的需求點盡可能的多。其中情形一為集合覆蓋問題，而情形二為最大覆蓋問題。為了滿足所有需求點的需求，使服務水平盡可能的達到最大，因此選擇集合覆蓋模型（如圖2所示）進行區域內維修站的選址。

圖2 集合覆蓋模型圖示

覆蓋模型是對已知的一些需求點確定一組服務設施來滿足這些需求點的需求。該模型中，需要確定服務設施的數量和合適的位置。集合覆蓋模型為用最小數量的設施點覆蓋所有需求點。如何確定設施點能夠覆蓋需求點，由于基本覆蓋模型的應用較為廣泛，其符號記法一般也稍有差異，在介紹模型之前，先對部分符號做如下規定：

N—區域中的需求點（車輛停靠點）集合，N={1，2，···，n}；

M—區域中可建立設施的候選點結合，M={1，2，···，m}；

xi為0-1變量，xi=1，在i 點建立設施；xi=0，不在i點建立設施，i∈M；

令sij表示設施點i到需求點j的距離，L表示某設施點最大覆蓋半徑，定義變量yij，滿足

3 實例分析

在產品差異化逐漸縮小的環境下，各類產品致勝的關鍵已經逐漸由質量演變為售后服務，而重型汽車行業體現的尤為明顯。在此基礎上，展開對某重汽維修服務站的選址，確保用戶在最短時間內得到最好的售后維修服務。

3.1 數據預處理

首先進行數據收集與處理。車輛信息包含車輛識別號碼(VIN)、車輛?？奎c以及軌跡的經緯度坐標、高度、行駛里程等，見表1。將汽車的運行以及?？寇壽E作為需求點，在進行聚類時只需考慮經緯度坐標即可達到聚類效果，因此對數據進行剔除，得到目標所需要的數據。

表1 原始數據包含信息

本文選取兩個月的記錄進行數據分析，共包含七萬多條數據，即共需要對76 160 對地理坐標點進行聚類分析。

3.2 區域劃分

K-means算法需要對輸入的數據進行處理，針對?？恳约熬S修點進行選址，則選取行駛軌跡、?？奎c維修點的地理坐標作為輸入數據組，用matlab 進行仿真，車輛運行軌跡可視化如圖3所示。利用kmeans算法對車輛的行駛軌跡、?？奎c等76 160個地理坐標進行聚類劃分，從車輛運行軌跡可以看出，需求點的分布不夠均勻，西北和東北區域相對分散，中部和南部較集中，因此除去東北和西北兩個區域，其他按照四個方位分為四個區域，因此設定初始聚類數目為6，利用K-means算法將全國范圍內的需求點劃分為6 個區域，并用不同的顏色標識，如圖4所示。利用Arcgis工具繪制需求點在地圖上的方位，如圖5所示。

圖3 車輛運行軌跡可視化

圖4 車輛軌跡聚類可視化

圖5 需求點聚類結果可視化

經過迭代計算，在聚類個數為6 的情況下，每一類的聚類中心以及每個區域所含需求點的個數見表2。

表2 聚類結果

可以看出，第三個區域需求點較多，第六個區域需求點較少。通過觀察，選取包含需求點數量最多的區域進行區域內選址。接下來需要考慮所有的需求點，建立合適的模型，考慮約束條件，在選定區域內進行選址，以此類推，在其他區域內選址，做出全國范圍內的維修服務站選址決定。

3.3 區域內維修站選址

維修站的選址采取集合覆蓋模型，要求滿足所有的維修需求，本文考慮距離因素，距離在一定程度上可以反映響應時間、服務水平等因素。選址的首要依據是進行需求分析，車輛經過的任何地方都有可能成為需求點，最終選擇的候選維修站需要滿足在統計內的所有需求點的需求，且維修站數量最少。

按照該企業原有維修數據統計，全國范圍內的臨時維修服務活動大多集中在270 個左右的臨時維修服務站點，企業可接受建立300個左右維修服務站的費用。兩個月內需求點的數量76 160 個，可以得出，一個維修站需要滿足大概260個需求點的維修需求。根據聚類的結果，得出每一個區域所需要建立的維修站數量最多如下：35、65、76、36、40、33 個，總數為285個。利用matlab2018a得到滿足需求的維修站地理坐標。

首先選擇需求點最多的范圍進行集合覆蓋模型選址，以第三個區域為例，主要包括內蒙、河北、山東、吉林、河南等地，得出不同覆蓋半徑下的維修站數量，在滿足費用要求的情況下，建立76 個維修站，維修半徑0.998 4L（地理半徑），可以覆蓋該區域的全部需求點20 336 個，使顧客滿意度最大。76 個維修站坐標見表3，不同覆蓋半徑所需維修站數量變化趨勢如圖6所示，第三區域維修站可視化如圖7所示。

表3 第三區域內設施坐標列表

得出第三個區域內選址地點后，需要對其他五個區域利用聚類算法進行集合覆蓋模型的選址，在滿足成本的要求下，求出各自范圍內維修服務站的數量，完成全國范圍內的選址計劃。最終得到285組地理坐標，部分地理坐標對應實際地理位置見表4。

圖6 不同覆蓋半徑下維修站數量

圖7 第三區域內選址地點可視化

表4 各區域內選址地點呈現

通過對集合覆蓋模型的求解，得出各個區域內維修站的坐標，根據地理信息系統得出實際對應的地點，共得出285個維修站的選址地點。利用ArcGis軟件在全國范圍內的選址結果，如圖8所示。

圖8 全國范圍服務站選址地點可視化

4 結語

維修服務站的選址大多依據經驗進行，對于小范圍小規模的選址具有一定的可行性，但是大范圍連鎖性質的選址以及大批量的建設服務設施必須以科學的方法為依據。

隨著信息技術的發展，大數據的成熟與應用，使得在解決實際問題時有了新的思路。本文結合車聯網大數據中的軌跡信息以及?？啃畔ⅲ瑢⑵渥鳛檫x址所需要考慮的因素，對于大規模的選址具有一定的意義。對于維修服務站選址相似課題，可以將車輛的記錄作為選址的依據。本文所考慮的選址因素較為單一，今后的研究應聚焦于因素的選擇上，比如服務水平、距離成本、運營成本等。此外，應加大信息共享程度，通過車聯網將數據及時反饋，涵蓋的信息應該更加多樣，可以和地理信息系統相結合，及時調整以達到最大的顧客滿意度。