兩種聚類模型在城市垃圾清運路徑規劃中的應用

王　龍，劉世于，胡建波

(重慶交通大學 機電與汽車學院，重慶 404100)

兩種聚類模型在城市垃圾清運路徑規劃中的應用

王龍，劉世于，胡建波

(重慶交通大學 機電與汽車學院，重慶 404100)

摘要:基于廣東省深圳市南山區的實地調查，提出了一種新的城市垃圾處理設備的分布設計和清運方案。在廚余垃圾處理設備的分布設計時，建立了兩種數學模型，即最短距離聚類模型和k-Means聚類模型。通過對兩者的比較得出k-Means聚類模型更適合垃圾清運路徑的規劃。本文提出的方法對解決深圳市南山區垃圾處理的路徑規劃具有較高的準確性，可用于全國其他各大城市的垃圾處理方案設計中。

關鍵詞：城市垃圾處理；最短距離聚類； k-Means聚類法；路徑規劃

中圖分類號：O159

文獻標志碼：碼：A

文章編號：號：2095-4824(2015)03-0026-06

收稿日期：2015-03-21

作者簡介：王龍(1989-)，男，河南澠池人，重慶交通大學機電與汽車學院碩士研究生。

Abstract：Based on the fieldwork in Nanshan District, Shenzhen city, Guangdong province, this paper proposes a new distribution design for waste disposal equipments and removal programs. For achieving the distribution design for waste disposal equipments, two mathematical models, namely the shortest distance clustering model and k-Means clustering model are established. By comparing the two models, it is shown that the k-Means clustering method is more suitable to path planning for urban waste disposal. The proposed method shows more accurate for waste disposal in Nanshan District, Shenzhen city, and can be applied to the waste disposal program project in the major cities across the country.

劉世于(1990-)，男，黑龍江哈爾濱人，重慶交通大學機電與汽車學院碩士研究生。

胡建波(1989-)，男，四川遂寧人，重慶交通大學機電與汽車學院碩士研究生。

垃圾分類化收集與處理不僅有利于減少垃圾的產生，有益于環境保護，而且有利于資源回收與再利用，是一項重要的城市綠色工程。我國大城市，如北京、上海、重慶和深圳，已經開展了垃圾分類化處理，并且取得了一定成效，但垃圾分類化進程中仍然面臨許多問題，其中垃圾處理設備的選址是非常關鍵的問題之一。合理地進行垃圾處理設備的選址，不僅可以減少垃圾處理設備的總費用，而且能減少垃圾的二次污染。垃圾站選址屬于鄰避型(不受歡迎型)設施選址問題[1]，需要綜合考慮廚余設備本身處理垃圾的能力和如何盡量減少污染排放。

目前，國內外學者主要用線性優化建立多目標方程得出最優選址位置。如栗娜和李珍萍建立的垃圾站對居民的影響和垃圾站建設運營成本均極小化的雙目標選址問題數學模型[2]；賈傳興等[3]選用集合覆蓋模型對中轉站的位置進行初步優化,確定了垃圾中轉站的待選點。在此基礎上,運用整數規劃構建整個城市垃圾收運系統費用現值最小模型,對城市垃圾中轉站的初步規劃進行二次優化,從待選點中選出垃圾中轉站的最優組合。另外還有一些學者用模糊綜合評判方法進行垃圾站的選址。如劉云斌使用模糊綜合評判系統進行城市生活垃圾填埋場選址[4]。然而，這些方法不能直接表達結果的優劣，更反映不出城市垃圾的聚集性和緊湊性，只是單純用一些量化目標來對結果進行評價。鑒于此，本文采用聚類算法對城市垃圾清運路徑規劃問題進行研究，方法簡單易用，并取得了較好的效果。

垃圾處理設備的選用問題取決于垃圾點的位置分布和垃圾數量，是一個非線性規劃問題，無法建立精確的模型。因此，本文采用最短距離聚類模型和k-Means 聚類模型來確定大型廚余垃圾處理設備的數量，利用中位點選址優化模型和Matlab編程求解廚余垃圾處理設備的位置分布。對于垃圾清運路線的設計，本著效益最大化和路程最小化原則，采用k-Means聚類方法將垃圾轉運站劃分成若干個區域，然后利用TSP(Traveling Salesman Problem)模型和下山逐點搜索法確定垃圾的最優運輸路線。

1　兩種不同的聚類模型

深圳市南山區的垃圾分為廚余垃圾、可回收垃圾、有害垃圾和其他不可回收垃圾。城市垃圾將從各小區的垃圾站運往附近的垃圾轉運站，在垃圾轉運站進行分類后，廚余垃圾運往廚余垃圾處理中心，可回收垃圾在垃圾轉運站進行分類再利用，有害垃圾和不可回收垃圾運往填埋場或垃圾焚燒廠處理。簡而言之，南山區的垃圾的清運工作包括收集清運和中轉清運兩個階段。收集清運使用60輛2.5噸的收集汽車將南山區中每個小區產生的垃圾運到各自臨近的垃圾中轉站；而中轉清運使用16輛載重10噸的拖車將中轉站已經分類好的垃圾轉運到各自的處理中心。

1.1　最短距離聚類模型

1.1.1 模型表示

將把每一個轉運站看成一類，依次記為G1，G2，…，G38，構造38個轉運站間的距離矩陣D：

然后以距離矩陣D為基礎，利用最短距離方法聚類。

最短距離聚類法是在原來的m×m距離矩陣的非對角元素中找出 ，把分類對象歸并為一個新類，然后按比較后的最小距離來計算原來各類與新類之間的距離，這樣就得到一個新的(m-1)階的距離矩陣；再從新的距離矩陣中選出最小者，把兩者歸并成新類；再計算各類與新類的距離，這樣一直下去，直至各分類對象被歸并為一類為止。

1.1.2　最短距離聚類算法

最短距離聚類模型的算法流程如下[5]：

Step 1：在距離矩陣D的非對角元素中找出距離最短的兩個類Gp和Gq，并為一新類Gr。

Step 2：然后按計算公式

(1)

計算原來各類與新類之間的距離，得到一個新的37階的距離矩陣。

Step 3：轉至Step 1，直到各分類對象被歸為一類為止。

1.1.3　最短距離聚類模型求解

以所給衛星地圖的直角坐標系，測出38個垃圾轉運站的相對坐標，結果如表1。

表1 　垃圾轉運站位置的相對坐標

基于以上分析和最短距離聚類算法流程，把38個垃圾轉運站點劃分為3類，聚類數量主要通過大、小型廚余垃圾的處理量和廚余垃圾總量進行劃分。通過計算發現，廚余垃圾總量需要兩個大型廚余設備和若干個小型廚余設備?？紤]到經濟性和合理性，且大型廚余設備污染更少，因此把38個站點劃分成3類。具體做法是利用Matlab中的pdist函數和squareform函數將坐標轉化為距離矩陣[6]，并利用linkage和cluster函數進行最短距離聚類，通過對最短距離聚類譜系圖的繪制(見圖1)，得到表2的分類結果。

表2　垃圾轉運站分類結果

圖1　最短距離聚類譜系圖

根據表2，可以得出：一區建立92臺小型設備；二區建立2臺大型設備和8臺小型設備；三區建立138臺小型設備。在不考慮運費的情況下，計算出總費用為15 440萬元

1.2　k-Means 聚類模型

1.2.1　k-Means 聚類基本思路

根據輸入的聚類參數k，將事先輸入的n個數據對象劃分為 k個聚類，使得所獲得的聚類滿足如下條件：同一聚類中的對象相似度較高，而不同聚類中的對象相似度較小。聚類相似度利用各聚類中對象的均值進行計算的。

1.2.2 k-Means 聚類算法

k-Means 聚類算法的基本流程如下：

Step 2：對數據集中的每個樣本點xi，計算其與各個聚類中心cj的歐式距離并獲取其類別標號：

(2)

Step 3：按下式重新計算3聚類中心

(3)

Step 4：重復Step 2和Step 3，直到達到最大迭代次數為止。

1.2.2 k-Means聚類模型求解

將測出的38個垃圾轉運站的坐標值利用Matlab中的pdist函數和squareform函數將坐標轉化為距離矩陣，并利用k-Means函數進行最短距離聚類[7]，聚類結果如表3所示。

表3　垃圾轉運站的k-Means分類結果

根據k-Means分析結果，建議在一區建立一個大型設備；二區建立一個大型設備；三區建立一個大型設備和14個小型設備。在不考慮運費的情況下，計算出總費用為13 867萬元。

1.3　兩種聚類結果的比較

使用最短距離聚類得到的大型設備過于集中在二區，出現扎堆現象，分布不合理，容易導致二區的大型設備不能全力工作，而一區和三區小型設備太多，容易導致大量的污染，因而經濟效益低下。使用k-Means聚類法得到的三個小區的設備在整體上分布比較平均，分類比較集中，各個小區分別配備一套大型設備，總體經濟效益比最短距離聚類方法更好，污染更少。

通過對兩種方案的比較，從兩方面可以看出 k-Means聚類法的優點。

1)最短距離聚類僅僅將距離相近的多個地方劃分同一類，缺乏整體的平均性，容易造成扎堆現象，無法使兩個聚類群獨立起來，類與類之間區別不明顯，容易導致分類結果的不合理性。

2)k-Means聚類法采用迭代方法能使整個分布更緊湊，迭代次數越多，分類越集中，最終能得到緊湊且獨立的簇，且同一聚類中的對象相似度較高。本算法確定的k 個劃分到達平方誤差最小。當聚類密集且類與類之間區別明顯時，分類效果較好。對于大數據集，該算法具有相對較好的可伸縮和計算效率。

通過上述分析，最短聚類所得的規劃結果總費用較多，因此本文建議采用k-Means聚類算法的結果作為最優方案。

2　中位點選址優化模型

根據垃圾轉運站的最終聚類結果和廚余垃圾處理設備的分布設計，首先用高精地圖測出每一個垃圾轉運站vi至各個站點vj的最短路徑長度dij(i，j = 1，2，…)，求出三類內部的距離矩陣：

(4)

然后建立模型確定每一類內部廚余垃圾處理中心的位置。

以距離和各轉運站的廚余垃圾量乘積之和為運行成本，以成本值為目標函數確定垃圾處理設備的具體位置?？紤]目標函數

(5)

式中：At=[a(v1)，a(v2)…a(vn)]為每類中各站點的載荷矩陣(廚余垃圾量)。

以每一類內部為約束條件，以各垃圾轉運站點的載荷加權，用Matlab中的矩陣運算求得每一個站點至各個站點的最短路徑長度的加權和，最后得出3個大型廚余垃圾處理設備位置。表4是垃圾轉運站最終聚類結果。

表4　垃圾轉運站最終聚類結果

3　焚燒垃圾的清運路線

3.1　車輛分配模型求解

由于車輛有限，本文先將16輛車分給三類垃圾的運輸，為此建立加權載荷模型求解垃圾站車輛的分配，模型如下：

(6)

式中：xij表示觀測值；Dij表示觀測值的對應權數；αi表示權算術平均數(即預測值)。運輸廚余垃圾的拖車所占比率為：

(7)

運輸焚燒垃圾的拖車所占比率：

(8)

運輸填埋垃圾的拖車所占比率：

(7)

運輸焚燒垃圾的拖車所占比率：

(8)

運輸填埋垃圾的拖車所占比率：

(9)

采用加權載荷法求解不同類型運輸車輛的分配情況，結果如表5所示。

3.2　垃圾清運路徑規劃

TSP模型是路運輸問題的最為典型的一個模型，它的全稱是TravelingSalesman Problem(TSP)，中文稱作旅行商問題[8]。TSP模型描述如下：在給出的一個頂點網絡(有向或無向)，要求找出一個包含所有頂點的具有最小耗費環路。任何一個包含網絡中所有n個頂點的環路被稱作一個回路。在旅行商問題中，要設法找到一條最小耗費的回路。

表5　垃圾轉運站車輛分配結果

TSP模型數學表達式如下：

?連通圖H，其頂點集合A，頂點間距離集為

(10)

目標函數：

(11)

約束條件為：

決策變量：

如果xij=0，從i到j無通路；如果xij=1，從i到j有通路。

圖2　焚燒垃圾運輸路線圖

本文首先利用k-Means聚類方法將38個垃圾轉運站點分成16塊，記為P集合，然后采用TSP模型對P集合的垃圾運轉路徑進行搜索得出焚燒垃圾運輸路線分別如圖2所示。

本文將三類內部的垃圾站點分別采用k-Means聚類方法分成3塊，并記為P1、P2、P3集合，然后采用與處理P集合同樣的處理方法對 P1、P2、P3進行處理，得出廚余垃圾的運輸路線，結果分別如圖3—圖5所示。

圖3　一區的廚余垃圾運輸路線

圖4　二區的廚余垃圾運輸路線

圖5　三區的廚余垃圾運輸路線

4　模型的有效性分析與建議

針對城市垃圾清運路徑規劃問題，本文提出了兩種聚類模型，主要優點包括：

(1)對于廚余垃圾處理設備的分配問題，分別提出了最短距離聚類模型和k-Means聚類模型，通過比較得出最優解決方案，避免只采用一種方案而導致規劃結果不準確。

(2)對于廚余設備的分配問題，本文將廚余垃圾的轉運量和轉運站到處理中心的距離作為兩個重要因素進行分析建模，能較好地解決廚余設備的選址問題，避免了問題的復雜化。

(3)把TSP模型運用到垃圾運輸問題上，能有效地解決近距離垃圾轉運的重疊問題，從而能有效減少資金投入。

然而，提出的模型仍然存在許多不足之處，主要表現在如下兩個方面：

(1)對于垃圾轉運站聚類問題，本文考慮的因素較少，沒有考慮交通因素、占地費用以及每個地方垃圾量的不確定性等因素，因此所得的結果不夠準確。

(2)對于運輸中汽車的分配問題，由于提供的數據有限，沒有充分考慮汽車運輸時的排隊問題，容易導致汽車分配不夠合理。

4　模型的有效性分析與建議

本文在對城市生活垃圾收運系統各個環節進行深入分析的基礎上，結合現代物流理論，以經濟最優化為目標，提出了城市垃圾收運系統的優化方法和數學模型，在較準確地解決深圳市南山區垃圾處理問題上，具有一定的通用性，可以推廣到全國各大城市的垃圾處理方案設計中以及特定情況下的貨物運輸問題中。

[參考文獻]

[1]Hakimi S L, Hakimi S L. Optimum locations of switching centers and the absolute centers and medians of a graph[J]. Operations Research, 1964, 12(3):450-459.

[2]栗娜,李玲萍.垃圾站選址問題的數學模型及應用[J].物流技術,2011,30(12):135-137.

[3]賈傳興, 彭緒亞, 劉國濤,等. 城市垃圾中轉站選址優化模型的建立及其應用[J].環境科學學報, 2006, 26:1927-1931.

[4]劉云斌.城市生活垃圾填埋場選址模糊綜合評判系統[D].成都:西南交通大學,2004.

[5]趙靜,但琦.數學建模與數學實驗[M].北京: 高等教育出版社,2004.

[6]黃雍檢,賴明勇.MATLAB語言在運籌學中的應用[M].湖南: 湖南大學出版社,2005.

[7]王祝文,劉菁華,任莉.基于K均值動態聚類分析的地球物理測井巖性分類方法[J].東華理工大學學報：自然科學版, 2009, 32(2):152-156.

[8]吳翊,吳孟達,成禮智.數學建模的理論與實踐[M].長沙: 國防科技大學出版社,2009.

Application of Two Clustering Models in Path Planning for Urban Waste Disposal

Wang Long，Liu Shiyu，Hu Jianbo

(InstituteofMechanicalandAutomobile,ChongqingJiaotongUniversity,Chongqing404100,China)

Key Words：urban waste disposal; shortest distance clustering model; k-Means clustering model; path planning

(責任編輯：張凱兵)