兩種聚類(lèi)模型在城市垃圾清運(yùn)路徑規(guī)劃中的應(yīng)用

王　龍，劉世于，胡建波

(重慶交通大學(xué) 機(jī)電與汽車(chē)學(xué)院，重慶 404100)

兩種聚類(lèi)模型在城市垃圾清運(yùn)路徑規(guī)劃中的應(yīng)用

王龍，劉世于，胡建波

(重慶交通大學(xué) 機(jī)電與汽車(chē)學(xué)院，重慶 404100)

摘要:基于廣東省深圳市南山區(qū)的實(shí)地調(diào)查，提出了一種新的城市垃圾處理設(shè)備的分布設(shè)計(jì)和清運(yùn)方案。在廚余垃圾處理設(shè)備的分布設(shè)計(jì)時(shí)，建立了兩種數(shù)學(xué)模型，即最短距離聚類(lèi)模型和k-Means聚類(lèi)模型。通過(guò)對(duì)兩者的比較得出k-Means聚類(lèi)模型更適合垃圾清運(yùn)路徑的規(guī)劃。本文提出的方法對(duì)解決深圳市南山區(qū)垃圾處理的路徑規(guī)劃具有較高的準(zhǔn)確性，可用于全國(guó)其他各大城市的垃圾處理方案設(shè)計(jì)中。

關(guān)鍵詞：城市垃圾處理；最短距離聚類(lèi)； k-Means聚類(lèi)法；路徑規(guī)劃

中圖分類(lèi)號(hào)：O159

文獻(xiàn)標(biāo)志碼：碼：A

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

收稿日期：2015-03-21

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

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-)，男，黑龍江哈爾濱人，重慶交通大學(xué)機(jī)電與汽車(chē)學(xué)院碩士研究生。

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

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

目前，國(guó)內(nèi)外學(xué)者主要用線性?xún)?yōu)化建立多目標(biāo)方程得出最優(yōu)選址位置。如栗娜和李珍萍建立的垃圾站對(duì)居民的影響和垃圾站建設(shè)運(yùn)營(yíng)成本均極小化的雙目標(biāo)選址問(wèn)題數(shù)學(xué)模型[2]；賈傳興等[3]選用集合覆蓋模型對(duì)中轉(zhuǎn)站的位置進(jìn)行初步優(yōu)化,確定了垃圾中轉(zhuǎn)站的待選點(diǎn)。在此基礎(chǔ)上,運(yùn)用整數(shù)規(guī)劃構(gòu)建整個(gè)城市垃圾收運(yùn)系統(tǒng)費(fèi)用現(xiàn)值最小模型,對(duì)城市垃圾中轉(zhuǎn)站的初步規(guī)劃進(jìn)行二次優(yōu)化,從待選點(diǎn)中選出垃圾中轉(zhuǎn)站的最優(yōu)組合。另外還有一些學(xué)者用模糊綜合評(píng)判方法進(jìn)行垃圾站的選址。如劉云斌使用模糊綜合評(píng)判系統(tǒng)進(jìn)行城市生活垃圾填埋場(chǎng)選址[4]。然而，這些方法不能直接表達(dá)結(jié)果的優(yōu)劣，更反映不出城市垃圾的聚集性和緊湊性，只是單純用一些量化目標(biāo)來(lái)對(duì)結(jié)果進(jìn)行評(píng)價(jià)。鑒于此，本文采用聚類(lèi)算法對(duì)城市垃圾清運(yùn)路徑規(guī)劃問(wèn)題進(jìn)行研究，方法簡(jiǎn)單易用，并取得了較好的效果。

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

1　兩種不同的聚類(lèi)模型

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

1.1　最短距離聚類(lèi)模型

1.1.1 模型表示

將把每一個(gè)轉(zhuǎn)運(yùn)站看成一類(lèi)，依次記為G1，G2，…，G38，構(gòu)造38個(gè)轉(zhuǎn)運(yùn)站間的距離矩陣D：

然后以距離矩陣D為基礎(chǔ)，利用最短距離方法聚類(lèi)。

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

1.1.2　最短距離聚類(lèi)算法

最短距離聚類(lèi)模型的算法流程如下[5]：

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

Step 2：然后按計(jì)算公式

(1)

計(jì)算原來(lái)各類(lèi)與新類(lèi)之間的距離，得到一個(gè)新的37階的距離矩陣。

Step 3：轉(zhuǎn)至Step 1，直到各分類(lèi)對(duì)象被歸為一類(lèi)為止。

1.1.3　最短距離聚類(lèi)模型求解

以所給衛(wèi)星地圖的直角坐標(biāo)系，測(cè)出38個(gè)垃圾轉(zhuǎn)運(yùn)站的相對(duì)坐標(biāo)，結(jié)果如表1。

表1 　垃圾轉(zhuǎn)運(yùn)站位置的相對(duì)坐標(biāo)

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

表2　垃圾轉(zhuǎn)運(yùn)站分類(lèi)結(jié)果

圖1　最短距離聚類(lèi)譜系圖

根據(jù)表2，可以得出：一區(qū)建立92臺(tái)小型設(shè)備；二區(qū)建立2臺(tái)大型設(shè)備和8臺(tái)小型設(shè)備；三區(qū)建立138臺(tái)小型設(shè)備。在不考慮運(yùn)費(fèi)的情況下，計(jì)算出總費(fèi)用為15 440萬(wàn)元

1.2　k-Means 聚類(lèi)模型

1.2.1　k-Means 聚類(lèi)基本思路

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

1.2.2 k-Means 聚類(lèi)算法

k-Means 聚類(lèi)算法的基本流程如下：

Step 2：對(duì)數(shù)據(jù)集中的每個(gè)樣本點(diǎn)xi，計(jì)算其與各個(gè)聚類(lèi)中心cj的歐式距離并獲取其類(lèi)別標(biāo)號(hào)：

(2)

Step 3：按下式重新計(jì)算3聚類(lèi)中心

(3)

Step 4：重復(fù)Step 2和Step 3，直到達(dá)到最大迭代次數(shù)為止。

1.2.2 k-Means聚類(lèi)模型求解

將測(cè)出的38個(gè)垃圾轉(zhuǎn)運(yùn)站的坐標(biāo)值利用Matlab中的pdist函數(shù)和squareform函數(shù)將坐標(biāo)轉(zhuǎn)化為距離矩陣，并利用k-Means函數(shù)進(jìn)行最短距離聚類(lèi)[7]，聚類(lèi)結(jié)果如表3所示。

表3　垃圾轉(zhuǎn)運(yùn)站的k-Means分類(lèi)結(jié)果

根據(jù)k-Means分析結(jié)果，建議在一區(qū)建立一個(gè)大型設(shè)備；二區(qū)建立一個(gè)大型設(shè)備；三區(qū)建立一個(gè)大型設(shè)備和14個(gè)小型設(shè)備。在不考慮運(yùn)費(fèi)的情況下，計(jì)算出總費(fèi)用為13 867萬(wàn)元。

1.3　兩種聚類(lèi)結(jié)果的比較

使用最短距離聚類(lèi)得到的大型設(shè)備過(guò)于集中在二區(qū)，出現(xiàn)扎堆現(xiàn)象，分布不合理，容易導(dǎo)致二區(qū)的大型設(shè)備不能全力工作，而一區(qū)和三區(qū)小型設(shè)備太多，容易導(dǎo)致大量的污染，因而經(jīng)濟(jì)效益低下。使用k-Means聚類(lèi)法得到的三個(gè)小區(qū)的設(shè)備在整體上分布比較平均，分類(lèi)比較集中，各個(gè)小區(qū)分別配備一套大型設(shè)備，總體經(jīng)濟(jì)效益比最短距離聚類(lèi)方法更好，污染更少。

通過(guò)對(duì)兩種方案的比較，從兩方面可以看出 k-Means聚類(lèi)法的優(yōu)點(diǎn)。

1)最短距離聚類(lèi)僅僅將距離相近的多個(gè)地方劃分同一類(lèi)，缺乏整體的平均性，容易造成扎堆現(xiàn)象，無(wú)法使兩個(gè)聚類(lèi)群獨(dú)立起來(lái)，類(lèi)與類(lèi)之間區(qū)別不明顯，容易導(dǎo)致分類(lèi)結(jié)果的不合理性。

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

通過(guò)上述分析，最短聚類(lèi)所得的規(guī)劃結(jié)果總費(fèi)用較多，因此本文建議采用k-Means聚類(lèi)算法的結(jié)果作為最優(yōu)方案。

2　中位點(diǎn)選址優(yōu)化模型

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

(4)

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

以距離和各轉(zhuǎn)運(yùn)站的廚余垃圾量乘積之和為運(yùn)行成本，以成本值為目標(biāo)函數(shù)確定垃圾處理設(shè)備的具體位置?？紤]目標(biāo)函數(shù)

(5)

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

以每一類(lèi)內(nèi)部為約束條件，以各垃圾轉(zhuǎn)運(yùn)站點(diǎn)的載荷加權(quán)，用Matlab中的矩陣運(yùn)算求得每一個(gè)站點(diǎn)至各個(gè)站點(diǎn)的最短路徑長(zhǎng)度的加權(quán)和，最后得出3個(gè)大型廚余垃圾處理設(shè)備位置。表4是垃圾轉(zhuǎn)運(yùn)站最終聚類(lèi)結(jié)果。

表4　垃圾轉(zhuǎn)運(yùn)站最終聚類(lèi)結(jié)果

3　焚燒垃圾的清運(yùn)路線

3.1　車(chē)輛分配模型求解

由于車(chē)輛有限，本文先將16輛車(chē)分給三類(lèi)垃圾的運(yùn)輸，為此建立加權(quán)載荷模型求解垃圾站車(chē)輛的分配，模型如下：

(6)

式中：xij表示觀測(cè)值；Dij表示觀測(cè)值的對(duì)應(yīng)權(quán)數(shù)；αi表示權(quán)算術(shù)平均數(shù)(即預(yù)測(cè)值)。運(yùn)輸廚余垃圾的拖車(chē)所占比率為：

(7)

運(yùn)輸焚燒垃圾的拖車(chē)所占比率：

(8)

運(yùn)輸填埋垃圾的拖車(chē)所占比率：

(7)

運(yùn)輸焚燒垃圾的拖車(chē)所占比率：

(8)

運(yùn)輸填埋垃圾的拖車(chē)所占比率：

(9)

采用加權(quán)載荷法求解不同類(lèi)型運(yùn)輸車(chē)輛的分配情況，結(jié)果如表5所示。

3.2　垃圾清運(yùn)路徑規(guī)劃

TSP模型是路運(yùn)輸問(wèn)題的最為典型的一個(gè)模型，它的全稱(chēng)是TravelingSalesman Problem(TSP)，中文稱(chēng)作旅行商問(wèn)題[8]。TSP模型描述如下：在給出的一個(gè)頂點(diǎn)網(wǎng)絡(luò)(有向或無(wú)向)，要求找出一個(gè)包含所有頂點(diǎn)的具有最小耗費(fèi)環(huán)路。任何一個(gè)包含網(wǎng)絡(luò)中所有n個(gè)頂點(diǎn)的環(huán)路被稱(chēng)作一個(gè)回路。在旅行商問(wèn)題中，要設(shè)法找到一條最小耗費(fèi)的回路。

表5　垃圾轉(zhuǎn)運(yùn)站車(chē)輛分配結(jié)果

TSP模型數(shù)學(xué)表達(dá)式如下：

?連通圖H，其頂點(diǎn)集合A，頂點(diǎn)間距離集為

(10)

目標(biāo)函數(shù)：

(11)

約束條件為：

決策變量：

如果xij=0，從i到j(luò)無(wú)通路；如果xij=1，從i到j(luò)有通路。

圖2　焚燒垃圾運(yùn)輸路線圖

本文首先利用k-Means聚類(lèi)方法將38個(gè)垃圾轉(zhuǎn)運(yùn)站點(diǎn)分成16塊，記為P集合，然后采用TSP模型對(duì)P集合的垃圾運(yùn)轉(zhuǎn)路徑進(jìn)行搜索得出焚燒垃圾運(yùn)輸路線分別如圖2所示。

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

圖3　一區(qū)的廚余垃圾運(yùn)輸路線

圖4　二區(qū)的廚余垃圾運(yùn)輸路線

圖5　三區(qū)的廚余垃圾運(yùn)輸路線

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

針對(duì)城市垃圾清運(yùn)路徑規(guī)劃問(wèn)題，本文提出了兩種聚類(lèi)模型，主要優(yōu)點(diǎn)包括：

(1)對(duì)于廚余垃圾處理設(shè)備的分配問(wèn)題，分別提出了最短距離聚類(lèi)模型和k-Means聚類(lèi)模型，通過(guò)比較得出最優(yōu)解決方案，避免只采用一種方案而導(dǎo)致規(guī)劃結(jié)果不準(zhǔn)確。

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

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

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

(1)對(duì)于垃圾轉(zhuǎn)運(yùn)站聚類(lèi)問(wèn)題，本文考慮的因素較少，沒(méi)有考慮交通因素、占地費(fèi)用以及每個(gè)地方垃圾量的不確定性等因素，因此所得的結(jié)果不夠準(zhǔn)確。

(2)對(duì)于運(yùn)輸中汽車(chē)的分配問(wèn)題，由于提供的數(shù)據(jù)有限，沒(méi)有充分考慮汽車(chē)運(yùn)輸時(shí)的排隊(duì)問(wèn)題，容易導(dǎo)致汽車(chē)分配不夠合理。

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

本文在對(duì)城市生活垃圾收運(yùn)系統(tǒng)各個(gè)環(huán)節(jié)進(jìn)行深入分析的基礎(chǔ)上，結(jié)合現(xiàn)代物流理論，以經(jīng)濟(jì)最優(yōu)化為目標(biāo)，提出了城市垃圾收運(yùn)系統(tǒng)的優(yōu)化方法和數(shù)學(xué)模型，在較準(zhǔn)確地解決深圳市南山區(qū)垃圾處理問(wèn)題上，具有一定的通用性，可以推廣到全國(guó)各大城市的垃圾處理方案設(shè)計(jì)中以及特定情況下的貨物運(yùn)輸問(wèn)題中。

[參考文獻(xiàn)]

[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]栗娜,李玲萍.垃圾站選址問(wèn)題的數(shù)學(xué)模型及應(yīng)用[J].物流技術(shù),2011,30(12):135-137.

[3]賈傳興, 彭緒亞, 劉國(guó)濤,等. 城市垃圾中轉(zhuǎn)站選址優(yōu)化模型的建立及其應(yīng)用[J].環(huán)境科學(xué)學(xué)報(bào), 2006, 26:1927-1931.

[4]劉云斌.城市生活垃圾填埋場(chǎng)選址模糊綜合評(píng)判系統(tǒng)[D].成都:西南交通大學(xué),2004.

[5]趙靜,但琦.數(shù)學(xué)建模與數(shù)學(xué)實(shí)驗(yàn)[M].北京: 高等教育出版社,2004.

[6]黃雍檢,賴(lài)明勇.MATLAB語(yǔ)言在運(yùn)籌學(xué)中的應(yīng)用[M].湖南: 湖南大學(xué)出版社,2005.

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

[8]吳翊,吳孟達(dá),成禮智.數(shù)學(xué)建模的理論與實(shí)踐[M].長(zhǎng)沙: 國(guó)防科技大學(xué)出版社,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

(責(zé)任編輯：張凱兵)