垃圾分類處理與清運方案設(shè)計(東北三省數(shù)學(xué)建模)1

1、答卷編號（參賽學(xué)校填寫） ：答卷編號（競賽組委會填寫） ：論文題目：A.垃圾分類處理與清運方案設(shè)計組別：本科生參賽隊員信息 (必填 )：姓名專業(yè)班級及學(xué)號聯(lián)系電話參賽隊員 1參賽隊員 2參賽隊員 3參賽學(xué)校：黑龍江八一農(nóng)墾大學(xué)答卷編號（參賽學(xué)校填寫） ：答卷編號（競賽組委會填寫） ：評閱情況（學(xué)校評閱專家填寫）：學(xué)校評閱 1.學(xué)校評閱 2.學(xué)校評閱 3.評閱情況（聯(lián)賽評閱專家填寫）：聯(lián)賽評閱 1.聯(lián)賽評閱 2.聯(lián)賽評閱 3.垃圾分類處理與清運方案設(shè)計摘要隨著環(huán)境保護日益被人們重視，垃圾分類化受到越來越多國家的重視。隨著國民經(jīng)濟發(fā)展與城市化進程加快，我國大城市的垃圾分類化也已經(jīng)提到日程上來。但是

2、垃圾的運送處理成為了一個很難解決的問題，因此如何達到最佳經(jīng)濟效益和環(huán)保效果，是我們此次研究的主要問題。問題一：廚余垃圾處理設(shè)備的分布設(shè)計。本問題我們首先采用最短距離聚類模型以及 k-Means 聚類模型來確定大型廚余垃圾處理設(shè)備的數(shù)量。通過對兩種模型的分析比較，我們發(fā)現(xiàn)采用 k-Means 聚類模型所得結(jié)果更為符合我們所要達到的效果， 而且通過比較建設(shè)廚余垃圾處理設(shè)備的花費，發(fā)現(xiàn)使用 3 個大型廚余垃圾處理設(shè)備時能達到最佳經(jīng)濟效益和環(huán)保效果。因此我們運用k-Means 聚類模型進行距離聚類，將38 個垃圾轉(zhuǎn)運站分成 3 塊。然后我們利用優(yōu)化模型，使用Matlab 進行編程，求解廚余垃圾處理設(shè)備

3、的位置分布。將三個大型廚余垃圾處理設(shè)備分別置于新圍公廁垃圾站，大沖公廁垃圾站及涌下村。通過計算建立設(shè)備的總花費為13500 萬元。問題二：清運路線具體方案設(shè)計。 我們通過建 TSP 模型來解決。 對于焚燒垃圾和填埋垃圾清運路線的確定，我們首先運用k-Means 聚類方法，將 38 個垃圾轉(zhuǎn)運站劃分為16 塊，然后采用下山逐點搜索法，確定路線運輸路線。而對于廚余垃圾的運輸，我們在第一問題中所分得的 3 塊基礎(chǔ)上，再次利用 k-Means 聚類方法將每個塊分為 56 個塊，最后采用下山逐點搜索法確定出處于廚余垃圾的運輸路線,通過計算得出每天總的費用為 5001 元（不包括可回收垃圾、有害垃圾以及每

4、個小區(qū)收集垃圾的運輸費用） 。問題三：垃圾運轉(zhuǎn)站的重新分布設(shè)計和大、小型廚余垃圾處理設(shè)備的分布設(shè)計。對于此問題我們建立了 k-Means 聚類模型，中位點選址模型以及集合覆蓋模型。對于此模型，我們首先利用 excel 將深圳所有小區(qū)的數(shù)據(jù)按片區(qū)名稱分類匯總，并得出每個小區(qū)的總?cè)藬?shù)。然后篩選出人數(shù)超過 2800 人的小區(qū)及人數(shù)不足 2800 人但房間數(shù)超過 80 間的小區(qū)作作為分析研究的對象。再運用谷歌地球軟件測出篩選出來的小區(qū)的坐標。通過 Matlab 軟件中的 pdist 函數(shù)和 squareform 函數(shù)將其化為距離方陣，并通過 k-Means 方法將小區(qū)聚為 38 類。然后以每一類中的居

5、民人數(shù)和距離作為選取轉(zhuǎn)運站位置的主要依據(jù)，用選址問題中的中位點選址方法確定垃圾運轉(zhuǎn)站的位置， 最后根據(jù)所給的垃圾運轉(zhuǎn)站的轉(zhuǎn)運量進行局部調(diào)整而得出垃圾站點的位置分布。問題四：垃圾運轉(zhuǎn)站位置重新設(shè)計后清運路線具體方案設(shè)計。此問題的解決方案與解決問題二的方案相同。關(guān)鍵詞： 中位點選址方法Matlab 下山搜索法集合覆蓋算法k-Means 聚類法1一、問題重述垃圾分類化收集與處理是有利于減少垃圾的產(chǎn)生，有益于環(huán)境保護，同時也有利于資源回收與再利用的城市綠色工程。我國大城市如北京、上海、重慶和深圳的垃圾分類化已經(jīng)提到日程上來，并且都都取得了一定成果，但是許多問題仍然是垃圾分類化進程中需要深入研究的。在深

6、圳，垃圾分為四類：櫥余垃圾、可回收垃圾、有害垃圾和其他不可回收垃圾。在垃圾分類收集與處理中，不同類的垃圾有不同的處理方式，所有垃圾將從小區(qū)運送到附近的轉(zhuǎn)運站，再運送到少數(shù)幾個垃圾處理中心。其中，廚余垃圾和可回收垃圾經(jīng)過處理，回收和利用，能產(chǎn)生經(jīng)濟效益。而有害垃圾和不可回收垃圾只有消耗處理費用，不產(chǎn)生經(jīng)濟效益。我們此次研究主要是解決以下幾個問題：問題（一）：假定現(xiàn)有垃圾轉(zhuǎn)運站規(guī)模與位置不變條件下，給出大、小型設(shè)備（櫥余垃圾）的分布設(shè)計問題（二）：在目前的運輸裝備條件下給出清運路線的具體方案。以期達到最佳經(jīng)濟效益和環(huán)保效果。問題（三）：假設(shè)轉(zhuǎn)運站允許重新設(shè)計，重新給出大、小型設(shè)備的分布設(shè)計。問題（

7、四）：求出重新設(shè)計垃圾運轉(zhuǎn)站位置后清運路線的具體方案二、問題分析2.1 廚余垃圾處理設(shè)備的分布設(shè)計根據(jù)題意我們首先要解決的問題是廚余垃圾處理設(shè)備的分布設(shè)計， 對于此問題我們要考慮所用大、小型處于垃圾處理設(shè)備的數(shù)量，以及所選用的廚余垃圾處理設(shè)備的放置地點的選擇。我們首先計算大型設(shè)備和小型設(shè)備所需的臺數(shù)。由于大、小型設(shè)備的處理垃圾能力不同，而且大型設(shè)備的的處理能力遠遠大于小型設(shè)備，所以我們先考慮大型廚余垃圾處理設(shè)備的安置。通過計算，我們得出廚余垃圾總量大約460 噸，而大型廚余設(shè)備處理能力為 200 噸，小型廚余垃圾處理能力在0.2-0.3 噸。相對來說小型廚余垃圾處理設(shè)備比大型廚余垃圾處理設(shè)備成

8、本高出許多，所以決定采用3 臺大型廚余垃圾處理設(shè)備。我們考慮將 38 個垃圾站點分成三類，并分別建設(shè)大型廚余垃圾處理設(shè)備。為此，先運用模糊數(shù)學(xué)中的聚類分析方法，構(gòu)造距離相似矩陣，將轉(zhuǎn)運站分為三類，每一類轉(zhuǎn)運站中布置一臺大型廚余設(shè)備。然后，確定設(shè)備的具體位置，這時可以考慮在每一個大型設(shè)備分區(qū)內(nèi)，以運行成本最少為目標來確定位置。為此，我們用百度地圖搜索到了轉(zhuǎn)運站之間的最短距離，結(jié)合各轉(zhuǎn)運站的廚余垃圾量，以及距離和各轉(zhuǎn)運站的廚余垃圾量乘積之和為運行成本，求最小成本值。求出每一個大型設(shè)備分區(qū)內(nèi)大型廚余垃圾處理設(shè)備的具體位置。具體算法可以采用退火算法、中位點算法等，因為數(shù)據(jù)少、計算精確我們選擇中位點算法

9、求得具體位置。12.2 清運路線具體方案的設(shè)計對于此問題我們建立了TSP 模型解決。首先根據(jù)題意，針對焚燒和填埋垃圾的運輸，我們運用 k-Means 聚類方法，將 38 個垃圾轉(zhuǎn)運站劃分為 16 個塊，然后運用 TSP 模型，確定路線運輸路線。而對于廚余垃圾的運輸，我們在第一問題中所分得的 3 塊的基礎(chǔ)上，再次利用 k-Means 聚類方法將每個塊分為 5 6 個塊并運用 TSP 模型確定出廚余垃圾的運輸路線。2.3 垃圾運轉(zhuǎn)站的重新分布設(shè)計和大、小型廚余垃圾處理設(shè)備的分布設(shè)計對于此問題我們建立了三個數(shù)學(xué)模型： k-Means 聚類模型，中心位置選址模型和集合覆蓋模型。通過對問題的分析，我們首

10、先要解決的是居民小區(qū)的數(shù)據(jù)。我們首先利用 excel 將深圳所有小區(qū)的數(shù)據(jù)按片區(qū)名稱分類匯總，并得出每個小區(qū)的總?cè)藬?shù)，然后通過人數(shù)和房間數(shù)對小區(qū)進行篩選作為分析研究的對象。 再運用谷歌地球軟件測出篩選出來的小區(qū)的坐標，通過 Matlab 軟件中的 pdist 函數(shù)和 squareform函數(shù)將其化為距離方陣，并通過 k-Means 聚類法將小區(qū)聚類。然后以每一類中的居民人數(shù)和距離作為選取轉(zhuǎn)運站位置的主要依據(jù)，用選址問題中的中位點選址方法確定垃圾運轉(zhuǎn)站的位置，最后根據(jù)所給的垃圾運轉(zhuǎn)站的轉(zhuǎn)運量進行局部調(diào)整而得出垃圾站點的位置分布。2.4 垃圾運轉(zhuǎn)站位置重新設(shè)計后清運路線的具體方案設(shè)計此問題與問題二

11、方法相同。三、模型假設(shè)1假設(shè)題目所給的數(shù)據(jù)真實可靠；2假設(shè)百度地圖中測量的兩點間距離真實可靠；3考慮到環(huán)保，假設(shè)廚余垃圾處理設(shè)備建在垃圾轉(zhuǎn)運站處；4各垃圾點的垃圾必須當(dāng)天及時清除完，不允許滯留；5晚上 22：00 后不堵車；6垃圾只在晚上運輸，每天各垃圾點的垃圾量基本相同，并且基本保證運完后，當(dāng)天不會再有新的垃圾產(chǎn)生；7每個垃圾點無論其中垃圾是否清理完全都需要10 分鐘裝車時間；8假設(shè)小區(qū)人數(shù)小于等于2800 人在數(shù)據(jù)處理時忽略（雖然平均每個小區(qū)的人數(shù)在1400 人左右，但人數(shù)分布比較集中， 所以利用人數(shù)較集中的小區(qū)作為研究對象， 將小區(qū)人數(shù)的下界定為 2800 人。）9測小區(qū)坐標時不考慮海拔

12、高度對距離的影響；10假設(shè)小區(qū)間距離用其坐標之間的直線距離表示；11假設(shè)垃圾的產(chǎn)生量與人數(shù)呈正比關(guān)系；12不考慮小區(qū)人數(shù)的變動；13廚余設(shè)備所安放的轉(zhuǎn)運點出廚余垃圾不需要運輸；14假設(shè) 2.5 噸小車運送垃圾時，在每個站點運送時所走路程相等；。四、定義與符號說明2D ：距離矩陣，元素 dij （i,j 1，2， ，9）為垃圾轉(zhuǎn)運點 vi 至垃圾轉(zhuǎn)運點 v j 的最短路徑長度。Dt ：調(diào)整后的距離矩陣（t=1， 2， ，3）。A ：各垃圾轉(zhuǎn)運點的載荷矩陣（以廚余垃圾的轉(zhuǎn)運量為載荷）。S ：每一個垃圾轉(zhuǎn)運點至其它各個垃圾轉(zhuǎn)的最短路徑長度的加權(quán)和。v i 、 vj ：垃圾轉(zhuǎn)運站點。x1i ：第一區(qū)中

13、第i 個垃圾轉(zhuǎn)運站的廚余垃圾量（i=1，2， ，13）。x2i：第二區(qū)中第 i 個垃圾轉(zhuǎn)運站的廚余垃圾量（i=1， 2， ，12）。x3i ：第三區(qū)中第 i 個垃圾轉(zhuǎn)運站的廚余垃圾量（i=1，2， ，13）。D1i：第一區(qū)中第 i 個垃圾轉(zhuǎn)運站到涌下村垃圾處理中心的距離（ i=1，2，13）。D2i：第二區(qū)中第 i 個垃圾轉(zhuǎn)運站到大沖公廁垃圾站垃圾處理中心的距離（ i=1，2，12）。D3i ：第三區(qū)中第 i 個垃圾轉(zhuǎn)運站到新圍公廁垃圾站的距離（i=1，2， ，13）。Yi ：表示各個垃圾轉(zhuǎn)運站焚燒垃圾量（i=1，2， 37）。DYi ：表示第 i 個垃圾轉(zhuǎn)運站到南山垃圾廠的距離（i=1，2，

14、 37）。Zi ：表示各個垃圾轉(zhuǎn)運站填埋垃圾的量（i=1 ， 2， ，37）。D Zi ：表示各個垃圾轉(zhuǎn)運站到下坪固體廢物填埋場的距離（i=1 ，2， ，37）。M 1,2, , m ：表示有 m 座垃圾收集站組成的集合；Ck ：表示篩選出的第k 座垃圾中轉(zhuǎn)站的中轉(zhuǎn)能力；X i ：表示第 i 座垃圾收集站的垃圾量；A(k ) ：表示篩選出的第k 座垃圾中轉(zhuǎn)站所覆蓋的垃圾收集站的集合；B(i ) ：表示可以覆蓋第f 座垃圾收集站的中轉(zhuǎn)站的集合；Wk ：表示是否啟用第k 座垃圾中轉(zhuǎn)站；U ik ：表示第 f 座垃圾中轉(zhuǎn)站是否被第七座垃圾中轉(zhuǎn)站覆蓋。3Ni ：第二問中第i 個垃圾轉(zhuǎn)運站所需2.5 噸

15、汽車的數(shù)量；ni ：垃圾轉(zhuǎn)運站重新分配后第i 個垃圾站點所需要轉(zhuǎn)運的垃圾總量。五、模型的建立與求解5.1 廚余垃圾處理設(shè)備的分布設(shè)計模型一：聚類分析模型 確定大型設(shè)備的臺數(shù)根據(jù)以上分析，我們建立了最短距離聚類模型和k-Means 聚類模型。1. 最短距離聚類模型（1）每一個轉(zhuǎn)運站看成一類，依次記為G1, G2 , G38 ，構(gòu)造 38 個轉(zhuǎn)運站間的距離矩陣d11d12d1,38d21d22d2,38Dd38,1d38,2d38,38以距離矩陣 D 為基礎(chǔ)，利用最短距離方法聚類。（2）算法流程Step1：在距離矩陣 D 的非對角元素中找出距離最短的兩個類Gp 和 Gq ，并為一新類Gr 。Ste

16、p2：然后按計算公式drk min d pk , dqk (k p, q)計算原來各類與新類之間的距離，得到一個新的37 階的距離矩陣。Step3：轉(zhuǎn)到 Step1，這樣一直下去，直至各分類對象被歸為一類為止。（3）最短距離聚類模型求解測出 38個垃圾轉(zhuǎn)運站以題中所給地圖的左邊緣和下邊緣為坐標軸建立直角坐標系，的相對坐標，結(jié)果如下表。表 1.垃圾轉(zhuǎn)運站點坐標序站點坐標序站點坐標號號1九街站(310.88,614.74)20松坪山站(472.67,708.31)2玉泉站(387.25,643.88)21南光站(346.3,485.51)3動物園站(557.51,912.21)22南園站(305.

17、11,490.7)4平山村站(550.19,869.55)23望海路站(377.43,272.8)5牛城村站(364.03,1035.02)24花果路站(373.79,297.45)6科技園站(456.6,501.66)25福光站（ 731.16， 918.44）47同樂村站（ 333.31， 758.42）26新圍村站(509.69,862.21)8松坪山（二）站(414.05,705.39)27大沖站(512.03,609.54)9大新小學(xué)站(294.92,585.53)28沙河市場站(591.91,629.27)10南山村站(251.38,456.19)29龍井(630.57,731.0

18、7)11陽光 (白芒關(guān)外 )站(423.74,1128.34)30南山市場(315.83,525.02)12月亮灣大道站(262.01,643.21)31麻勘站(507.74,1158.73)13光前站(566.28,740.23)32白芒站(440.77,1087.5)14北頭站(289.49,502.03)33大石磡站(621.53,1054.34)15涌下村站(303.78,552.77)34長源村站（ 810.19， 928.92）16白石洲南站(576.85,551.37)35華僑城站(728.92,597.51)17前海公園站(267.75,635.54)36疏港小區(qū)站(186.9

19、2,286.51)18深圳大學(xué)站(432.21,569.66)37西麗路站（ 489.97， 788.75）19官龍村站(481.69,883.28)38塘朗站（ 738.11， 904.59）通過對本問題的以上分析和算法流程，把38 個垃圾轉(zhuǎn)運站點聚為 3 類，具體做法是利用 Matlab 中的 pdist 函數(shù)和 squareform 函數(shù)將坐標轉(zhuǎn)化為距離矩陣，并利用linkage和 cluster 函數(shù)進行最短距離聚類，得到如下三類結(jié)果如下表。表 2.垃圾轉(zhuǎn)運站分類結(jié)果類別垃圾轉(zhuǎn)運站一類疏港小區(qū)站二類九街站玉泉站動物園站平山村站牛城村站科技園站同樂村站松坪山（二）站 大新小學(xué)站南山村站陽

20、光 (白芒關(guān)外 )站 月亮灣大道站光前站北頭站涌下村站白石洲南站前海公園站深圳大學(xué)站官龍村站松坪山站南光站 南園站福光站新圍村站大沖站沙河市場站龍井南山市場麻勘站白芒站大石磡站長源村站華僑城站西麗路塘朗站三類望海路站花果路站根據(jù)表 2，我們得出：一區(qū)建立 92 臺小型設(shè)備； 二區(qū)建立 2 臺大型設(shè)備和 8 臺小型設(shè)備；三區(qū)建立 138 臺小型設(shè)備。在不考慮運費的情況下， 我們計算出總費用為： 15440 萬元2. k-Means 聚類模型：（1）k-Means 5 聚類基本思路： 接受聚類參數(shù) k，然后將事先輸入的n 個數(shù)據(jù)對象劃分為k 個聚類以便使得所獲得的聚類滿足：同一聚類中的對象相似度較

21、高；而不同聚類中的對象相似度較小。聚類相似度是利用各聚類中對象的均值所獲得一個“中心對象 ”（引力中心）來進行計算的。（2）算法流程Step1：從數(shù)據(jù)集 xn 38n1 中任意選取 3 賦給初始的聚類中心c1 ， c2 ， c3 。Step2：對數(shù)據(jù)集中的每個樣本點xi ，計算其與各個聚類中心c j 的歐式距離并獲取其類別標號：label (i )arg min | xicj |2 , i1,2,.,38, j1,2,3 。j5Step3：按下式重新計算3 聚類中心xscjs:label ( s)j, j 1,2,3。N jStep4：重復(fù) Stept2 和 Stept3，直到達到最大迭代次數(shù)

22、為止。（3）k-Means 聚類模型求解我們利用第一部分測出 38個垃圾轉(zhuǎn)運站的坐標值。然后利用 Matlab中的 pdist函數(shù)和squareform函數(shù)將坐標轉(zhuǎn)化為距離矩陣， 并利用 k-Means函數(shù)進行最短距離聚類， 得到如下三部分結(jié)果：表 3. 垃圾轉(zhuǎn)運站分類結(jié)果類別垃圾轉(zhuǎn)運站一類玉泉站 平山村站 同樂村站 松坪山（二）站光前站白石洲南站松坪山站大沖站 沙河市場站 龍井 華僑城站深圳大學(xué)站 科技園站二類動物園站 牛城村站陽光 (白芒關(guān)外 )站 福光站麻勘站白芒站大石磡站長源村站 塘朗站 官龍村站新圍村站西麗路站三類九街站 大新小學(xué)站南山村站月亮灣大道站北頭站涌下村站前海公園站南光站

23、南園站 望海路站花果路站南山市場 疏港小區(qū)站通過對表 3 結(jié)果的計算和分析，我們得出：一區(qū)建立一個大型設(shè)備；二區(qū)建立以個大型設(shè)備；三區(qū)建立一個大型設(shè)備和 14 個小型設(shè)備。在不考慮運費的情況下，我們計算出總費用為： 13867 萬元。3 兩種模型的比較及最終聚類結(jié)果通過對兩種方案總費用的比較，我們得出 k-means 聚類算法為最優(yōu)方案。模型二：優(yōu)化模型 確定廚余垃圾處理中心位置根據(jù)表 4的垃圾轉(zhuǎn)運站最終聚類結(jié)果，以及對于廚余垃圾處理設(shè)備的分布設(shè)計，我們首先用百度地圖測出每一個垃圾轉(zhuǎn)運站vi 至其它各個站點 v j 的最短路徑長度 dij （ i，j 1，2，），求出三類內(nèi)部的距離矩陣d11d

24、1nDt, t1,2,3.dm1dmn下面建立模型確定每一類內(nèi)部廚余垃圾處理中心的位置。以距離和各轉(zhuǎn)運站的廚余垃圾量乘積之和為運行成本， 以成本值為目標函數(shù)確定垃圾處理設(shè)備的具體位置?？紤]目標函數(shù)min St (vi ) S(v1 ), S(v2 ), S( vn ) Dt * Ati其中， At a(v1 ), a(v2 )a(vn ) 為每類內(nèi)各站點的載荷矩陣（廚余垃圾量） 。以每一類內(nèi)部為約束條件，以各垃圾轉(zhuǎn)運站點的載荷加權(quán)，用Matlab中的矩陣運算求得每一個站點至其它各個站點的最短路徑長度的加權(quán)和，最后得出將3個大型廚余垃6圾處理設(shè)備位置分別如下表。表 4. 垃圾轉(zhuǎn)運站最終聚類結(jié)果類

25、別大型廚余垃圾處理設(shè)備位置一類新圍公廁垃圾站二類大沖公廁垃圾站三類涌下村5.2 清運路線具體方案的設(shè)計模型一：加權(quán)載荷模型 車輛的分配由于車輛有限，我們先將 16 輛車分給三類垃圾的運輸，為此建立加權(quán)載荷模型。（1）模型ixij Dij(i 1,2,3; j1,2,3, 13, s 1,2,3, ,38)xs Dsxij ：觀測值； Dij ：觀測值的對應(yīng)權(quán)數(shù)；i ：權(quán)算術(shù)平均數(shù)（即預(yù)測值） 。（2）模型求解運輸廚余垃圾的拖車所占比率：1312135 ( x1 i D1ix2 iD2 ix3iD3i )1i 1i 1i 11312135 ( x1i D1ix2i D2 ix3iD3 i ) Y

26、iDYiZi DZii 1i 1i1運輸焚燒垃圾的拖車所占比率：2YiDYi1312135 ( x1i D1ix2 i D2 ix3 i D3i )Yi DYi Zi DZii 1i 1i 1運輸填埋垃圾的拖車所占比率：3ZiDZi1312135 ( x1i D1ix2i D2 ix3 i D3i )Yi DYi Zi DZii 1i 1i 1（2）求解車輛的分配用加權(quán)載荷法確定每類具體方法如下：表 5.垃圾轉(zhuǎn)運站最終聚類結(jié)果車輛類別所占比率車輛數(shù)量運輸廚余垃圾的車輛0.325運輸焚燒垃圾的車輛0.254運輸填埋垃圾的車輛0.4277模型二： TSP 模型 清運路線的設(shè)計（1）焚燒垃圾的清運路

27、線通過對同中所給數(shù)據(jù)的分析， 以及相關(guān)資量的查閱， 我們決定采用 TSP 模型對問題進行求解。TSP 模型 6 路運輸問題的最為典型的一個模型，它的全稱是TravelingSalesman Problem(TSP)，中文叫做旅行商問題。 TSP 模型可以如下描述：在給出的一個雄頂點網(wǎng)絡(luò) (有向或無向 )，要求找出一個包含所有甩個頂點的具有最小耗費的環(huán)路。任何一個包含網(wǎng)絡(luò)中所有 n 個頂點的環(huán)路被稱作一個回路 (Tour)。在旅行商問題中，要設(shè)法找到一條最小耗費的回路。既然回路是包含所有頂點的一個循環(huán)，故可以把任意一個點作為起點 (因此也是終點 )，這也是 TSP 模型的一個特點。TSP 模型數(shù)

28、學(xué)表達式如下：連通圖 H，其頂點集合 A ，定點間距離為 Ccij i, jN ,1i , jn目標函數(shù)：mnmincij xiji 1j1約束條件：nxij1,i1,2,nj 1nxij1,i1,2,mi 1xij 0,1,i 1,2, , n, j1,2, , m決策變量：xij0 ，從 i 到 j 無通路； xij 1 ，從 i到 j 有通路。我們首先利用 k-Means 聚類方法將 38 個垃圾轉(zhuǎn)運站點分成 16 塊，記為 P 集合，具體數(shù)據(jù)如下表所示：表 6. P 集合及該集合的垃圾量塊序號垃圾站點序號垃圾量到焚燒廠的距離116,27,285.9,3.9,8.914.8，13.5,1

29、6.822,7， 8,207.4,1.5,2.9,7.410.8，12.9,14.9,13.834,19,267.4,4.5,5.918.8,17.1,16.941,9,12， 175.9,8.9,11.9,4.710.1,8.1,10.2,8.8523,248.9,8.911.7,11.265,321.5,2.419.4,20.1725,34,382.9， 1.5,2.921.9,24.1,21.2814,15,21,22,304.5,5.9,4.5,4.5,7.46.8,8.5,8.2,7.6,7.5911,312.9， 2.921.5,2210107.45.98116,85.9， 2.9

30、12.3,14.9,1213,29,375.9， 4.5，4.517.6,16.7,15133611.94.81435.919.8153520.817.216338.923然后我們采用 TSP 模型對 P 集合的垃圾運轉(zhuǎn)路徑進行搜索得出焚燒垃圾運輸路線如下圖。圖 1. 焚燒垃圾運輸路線圖注：:垃圾量超過 8.5 噸，且一次就能運完的垃圾站點:表示垃圾量不足8.5 噸的垃圾站點9:表示需要運輸兩次或兩次以上的垃圾站點:表示垃圾處理中心費用的計算公式： F費0.32.07L2.07(lL' )（ l :表示轉(zhuǎn)運站點之間的距離； L ':表示末點到處理中心的距離）時間的計算公式：TS

31、總 /4010a5b ( S總 : 表示總路程 ;a:表示裝車的次數(shù) ;b:表示卸車的次數(shù) )每天運輸焚燒垃圾的總費用1428 元： ,每輛車需工作 5.2 個小時（2）填埋垃圾的清運路線此問題的求解過程與焚燒垃圾清運路線的求解過程一樣，并且結(jié)果基本相同。通過計算，每天運輸填埋垃圾的總費用為 2349 元，每輛車需工作 4.8 個小時。（3）廚余垃圾的清運路線我們將三類內(nèi)部的垃圾站點分別采用k-Means 聚類方法分成 5 塊，并記為 P1 、 P2 、P3 集合，具體數(shù)據(jù)如下表所示：表 7. P1 、 P2 、 P3 集合中的垃圾量以及到處理中心的距離區(qū)塊塊序號1 集合垃圾量到涌下村的距離P

32、一區(qū)123， 2417.13， 17.13，8.3， 8.023622.847.1321， 22， 10， 14， 308.57，8.57，14.28，8.57，14.282.3，2.0，2.8，1.949， 1， 1717.13， 11.42， 9.141.2， 0.54， 2.051222.843.8二區(qū)172.88.522， 18， 614.3，8.6， 11.44.0， 3.6， 1.138， 205.7， 14.37.2， 3.7413， 2711.4， 8.65.2， 7.7516， 28， 3517.1，17.1， 401.4， 3.6， 3.4三區(qū)131， 11， 5， 325

33、.7， 5.7， 2.9，4.67.1，6.0，4.7，5.22342.97.6319， 4， 38.6， 14.3， 11.40.85，2.3， 2.4425， 38， 375.7， 5.7， 8.65.1， 4.6， 5.653317.15.6然后采用和處理 P 集合同樣的處理方法對P1 、 P2 、 P3 進行處理，得出廚余垃圾的運輸路線，結(jié)果如下圖所示：10圖 2. 一區(qū)的廚余垃圾運輸路線圖 3. 二區(qū)的廚余垃圾運輸路線11圖 4. 三區(qū)的廚余垃圾運輸路線注：:運走 n*10 噸后 ,還有剩余 的站點 (n是次數(shù)， n=1,2, ):垃圾量超過 8.5噸，且一次就能運完的垃圾站點:表示

34、運走 n* （8.510）噸后無剩余的站點（n是次數(shù)， n=2,3，）:表示垃圾量不足 8.5噸的垃圾站點:表示需要運輸兩次或兩次以上的垃圾站點:表示垃圾處理中心運輸廚余垃圾每天的總費用為 1224元，每輛車需工作 4.7個小時小結(jié)：1. 每天廚余垃圾的的產(chǎn)量為 460噸，我們通過查找資料得出廚余垃圾經(jīng)處理設(shè)備處理后的產(chǎn)物的產(chǎn)率為 0.2，然后計算出廚余垃圾經(jīng)處理設(shè)備處理后的產(chǎn)物量為 92噸，其收益為 2300069000元。2. 我們首先利用題目所給的四類垃圾（廚余垃圾、可回收垃圾、有害垃圾、其他不可回收垃圾）的比例（ 4:2:1:3）計算出每天產(chǎn)生的可回收垃圾量為 230噸，然后，利用可回

35、收垃圾中四類垃圾（紙類、塑料、玻璃、金屬）的平均比例計算出相應(yīng)垃圾的產(chǎn)量，具體結(jié)果如下表表 8. 可回收垃圾收益表類別產(chǎn)量（噸）收益（元）紙類127.019127019塑料80.8304201201玻璃13.85666898金屬9.237822994合計230.94383581123. 總收益為 381112 427112元5.3 垃圾運轉(zhuǎn)站的重新分布設(shè)計和大、小型廚余垃圾處理設(shè)備的分布設(shè)計對于本問題我們采用了k-means 模型、集合覆蓋模型以及中心位點選址模型進行求解。模型一： k-Means 模型 垃圾轉(zhuǎn)運站點的初步確定（1）k-Means 聚類基本思路： 接受聚類參數(shù) k，然后將事先輸

36、入的n 個數(shù)據(jù)對象劃分為 k 個聚類以便使得所獲得的聚類滿足：同一聚類中的對象相似度較高；而不同聚類中的對象相似度較小。聚類相似度是利用各聚類中對象的均值所獲得一個“中心對象 ”（引力中心）來進行計算的。（2）算法流程Step1：從數(shù)據(jù)集 xn 38n1 中任意選取 3 賦給初始的聚類中心c1 ， c2 ， c3 。Step2：對數(shù)據(jù)集中的每個樣本點xi ，計算其與各個聚類中心c j 的歐式距離并獲取其類別標號：label (i )arg min | xicj |2 , i1,2,.,38, j1,2,3 。j12Step3：按下式重新計算3 聚類中心xscjs:label ( s)j, j

37、1,2,3 。N jStep4：重復(fù) Stept2 和 Stept3，直到達到最大迭代次數(shù)為止。（3）k-Means 模型的求解：我們首先利用 excel3 深圳所有小區(qū)的數(shù)據(jù)按片區(qū)名稱分類匯總，并得出每個小區(qū)的總?cè)藬?shù)。然后篩選出人數(shù)超過 2800 人的小區(qū)以及剩余中房間數(shù)超過80 間的小區(qū)作為分析研究的對象。再運用谷歌地球軟件測出篩選出來的小區(qū)的坐標。參照當(dāng)?shù)厝丝诿芏纫约袄占芏?，算出該城區(qū)垃圾收集最優(yōu)半徑為750m；再結(jié)合實際勘探情況以及城市總體規(guī)劃共布置大型垃圾收集站149 座。然后通過 Matlab軟件中的 pdist 函數(shù)和 squareform 函數(shù)將其化為距離方陣，并通過 k

38、-Means 方法將小區(qū)聚為 38 類。然后以每一類中的居民人數(shù)和距離作為選取轉(zhuǎn)運站位置的主要依據(jù)，用選址問題中的中位點選址方法確定垃圾運轉(zhuǎn)站的位置，模型二：集合覆蓋模型 垃圾轉(zhuǎn)運站點的調(diào)整集合覆蓋模型目標是在滿足覆蓋所有垃圾運轉(zhuǎn)戰(zhàn)的情況下， 確定建立大型廚余垃圾處理設(shè)備的個數(shù)或建設(shè)費用最小，并配置這些服務(wù)設(shè)施使所有的轉(zhuǎn)運站都能被覆蓋住到。具體表達式如下所示。minWkkMU ik1(i1,2,m)(1)k B (i )X iU ikCk Wk (i 1,2, m; kB(i )(2)i A (k )Xi , Ci0,( i1,2, m; kB(i)(3)Wk0,1(4)U ik0,1(5)目

39、標函數(shù)為從現(xiàn)有 m 座垃圾運轉(zhuǎn)站的位置中優(yōu)選出可以覆蓋m 座垃圾收集站的最小數(shù)目的中轉(zhuǎn)站選點；約束式l 表示每一座垃圾運轉(zhuǎn)站的垃圾均被清運；約束式2 是滿足垃圾運轉(zhuǎn)站中轉(zhuǎn)能力的要求；約束式3 表示垃圾站和中轉(zhuǎn)站的垃圾量非負；約束式 4是垃圾收集站是否位于第k 座垃圾中轉(zhuǎn)站附近的決策變量；約束式5 是第 j 座垃圾收集站是否有垃圾收運到第k 座中轉(zhuǎn)站的決策變量。從而得出垃圾轉(zhuǎn)運站點的位置分布，如下表所示：表 9. 垃圾運轉(zhuǎn)站新站點分布編片區(qū)名稱地址總?cè)藬?shù)垃圾轉(zhuǎn)運量號1平山村站南山區(qū)平山村內(nèi)2894324.5323313207網(wǎng)格片區(qū)匯總南山華泰小區(qū)79415.843525307網(wǎng)格片區(qū)匯總后海小

40、學(xué)400117.44932401網(wǎng)格片區(qū)匯總登良路與南商路交叉口處3333036.789725南山村站東濱路與前海路交匯處4113522.166556沙河市場站南山區(qū)沙河市場旁7980331.861247大沖站深南大道大沖村旁1999714.715158前海公園站南山區(qū)前海公園內(nèi)1911153.19449龍井龍珠五路龍井村旁3202817.6762810大新小學(xué)站南頭街大新小學(xué)旁5812932.081441103網(wǎng)格片區(qū)匯總大磡村綜合市場1734629.147331201網(wǎng)格片區(qū)匯總公園路與招商路1633330.979121322網(wǎng)格片區(qū)匯總新圍村1473419.516114華僑城站僑城東路西

41、側(cè)2145542.627721505網(wǎng)格片區(qū)匯總白芒村南2251227.3336616北頭站前海路與桂廟路交叉口1041917.2507717動物園站深圳野生動物園1204016.300411816網(wǎng)格片區(qū)匯總留仙洞村130625.76714319南園站南山區(qū)南園村內(nèi)4060917.2401120白石洲站白石洲與石洲中路交叉口2893931.942922107網(wǎng)格片區(qū)匯總西麗路2261217.82287221網(wǎng)格匯總珠光村1521320.150562304網(wǎng)格片區(qū)匯總北環(huán)大道與京港澳高速公1368327.18597路交叉口24玉泉站玉泉路寶龍路口237349.52912825九街站深南大道南頭

42、中學(xué)旁1204813.29862610網(wǎng)格片區(qū)匯總官龍村1706615.697927深圳科技工業(yè)園大廈深圳科技工業(yè)園大廈1682529.566342803網(wǎng)格片區(qū)匯總東角頭 -地鐵站2029539.241252907網(wǎng)格片區(qū)匯總玉泉路1425131.460563011網(wǎng)格片區(qū)匯總興海大道蛇口站1265941.919093102網(wǎng)格片區(qū)匯總南山區(qū)福光村內(nèi)5080731.9473432松坪山（二）站高新北區(qū)朗山一路綠地內(nèi)2047110.0595633深圳大學(xué)站校園內(nèi)81068.73254734平山 P片區(qū) 匯總創(chuàng)業(yè)路與南光路交叉口1748620.403535科技園站科苑南路與濱海路大道交86331

43、7.02847匯處西側(cè)36松坪山站南山區(qū)松坪山第五工業(yè)區(qū)305425.651883703網(wǎng)格片區(qū)匯總桃李花園328118.107873803網(wǎng)格片區(qū)匯總學(xué)府路與南山大道交叉口964923.8228214圖 5. 新設(shè)計的垃圾轉(zhuǎn)運站分布圖模型三：優(yōu)化模型 廚余垃圾處理中心的確定1. 聚類分析模型 將 38 個站點分為三類根據(jù)表 9的垃圾轉(zhuǎn)運站最終聚類結(jié)果，以及對于廚余垃圾處理設(shè)備的分布設(shè)計，我們首先用百度地圖測出每一個垃圾轉(zhuǎn)運站vi 至其它各個站點 v j 的最短路徑長度 dij （ i，j 1，2，），求出三類內(nèi)部的距離矩陣d11d1nDt, t 1,2,3.dm1dmn下面建立模型確定每一類內(nèi)部廚余垃圾處理中心的位置。以距離和各轉(zhuǎn)運站的廚余垃圾量乘積之和為運行成本， 以成本值為目標函數(shù)確定垃圾處理設(shè)備的具體位置?？紤]目標函數(shù)min St (vi ) S(v1 ), S(v2 ),S( vn )Dt * Ati15其中， At a(v1 ), a(v2 ) a(vn ) 為每類內(nèi)各站點的載荷矩陣（廚余垃圾量） 。我們首先采用與解決問題一同樣的方法確定38 個垃圾站