【正文】 1, 2 , 3ss la b el s jjjcjN ????x 。 （ 2）算法流程 Step1：從數(shù)據(jù)集 381{}nn?x 中任意選取 3賦給初始的聚類中心 1c ， 2c ， 3c 。 模型一： kMeans 模型 —— 垃圾轉(zhuǎn)運站點的初步確定 （ 1） kMeans 聚類基本思路：接受聚類參數(shù) k，然后將事先輸入的 n個數(shù)據(jù)對象劃分為 k 個聚類以便使得所獲得的聚類滿足：同一聚類中的對象相 似度較高；而不同聚類中的對象相似度較小。 （ 3）廚余垃圾 的清運路線 我們將三類內(nèi)部的垃圾站點分別采用 kMeans 聚類方法分成 5 塊，并記為 1P 、 2P 、3P 集合，具體數(shù)據(jù)如下表所示： 表 7. 1P 、 2P 、 3P 集合中的垃圾量以及到處理中心的距離 區(qū)塊 塊序號 1P 集合 垃圾量 到涌下村的距離 一區(qū) 1 23， 24 ， ， ， 2 36 3 21， 22， 10， 14， 30 ， ， ， ， ， ， ， 4 9， 1， 17 ， ， ， ， 5 12 二區(qū) 1 7 2 2， 18， 6 ， ， ， ， 3 8， 20 ， ， 4 13， 27 ， ， 5 16， 28， 35 ， ， 40 ， ， 三區(qū) 1 31， 11， 5， 32 ， ， ， ， ， ， 2 34 3 19， 4， 3 ， ， ， ， 4 25， 38， 37 ， ， ， ， 5 33 然后采用 和處理 P 集合同樣的處理方法對 1P 、 2P 、 3P 進行處理， 得出廚余垃圾的運輸路線，結(jié)果如下圖所示： 11 圖 2. 一區(qū)的廚余垃圾運輸路線 圖 3. 二區(qū)的廚余垃圾運輸路線 12 圖 4. 三區(qū)的廚余垃圾運輸路線 注： :運走 n*10噸后 ,還有剩余 的站點 (n是次數(shù)， n=1,2,…) :垃 圾量超過 ，且一次就能運完的垃圾站點 :表示運走 n*（ ～ 10）噸后無剩余的站點（ n是次數(shù)， n=2,3， … ） :表示垃圾量不足 :表示需要運輸兩次或兩次以上的垃圾站點 :表示垃圾處理中心 運輸廚余垃圾每天的總費用為 1224元，每輛車需工作 小結(jié)： 1. 每天廚余垃圾的的產(chǎn)量為 460噸，我們通過查找資料得出廚余垃圾經(jīng)處理設(shè)備處理后的產(chǎn)物的產(chǎn)率為 ，然后計算出廚余垃圾經(jīng)處理設(shè)備處理后的產(chǎn)物量為 92噸，其收益為 23000～ 69000元。b:表示卸車的次數(shù) ) 每天運輸焚燒垃圾的總費用 1428 元： ,每輛車需工作 個小時 （ 2）填埋垃圾的清運路線 此問題的求解過程與焚燒垃圾清運路線的求解過程一樣，并且結(jié)果基本相同。L :表示末 點到處理中心的距離） 時間的計算公式： b5a10/40ST ????? 總 ( 總S :表示總路程 。 圖 1. 焚燒垃圾運輸路線圖 注： :垃 圾量超過 ，且一次就能運完的垃圾站點 :表示垃圾量不足 10 :表示需要運輸兩次或兩次以上的垃圾站點 :表示垃圾處理中心 費用的計算公式： )L39。 TSP 模型數(shù)學(xué)表達式如下： ? 連通圖 H，其頂點集合 A，定點間距離為 ? ?, , 1 ,ijC c i j N i j n? ? ? ? 目標(biāo)函數(shù)： 11minmnij ijijcx???? 約束條件： 1 1, 1, 2,nijj x i n? ??? 1 1, 1, 2 ,niji x i m? ??? ? ?0 ,1 , 1 , 2 , , , 1 , 2 , ,ijx i n j m? ? ? 決策變量： 0ijx? ，從 i到 j 無通路； 1ijx? ，從 i到 j 有通路。在 旅行商問題中，要設(shè)法找到一條最小耗費的回路。 TSP 模型可以如下描述：在給出的一個雄頂點網(wǎng)絡(luò) (有向或無向 )，要求找出一個包含所有甩個頂點的具有最小耗費的環(huán)路。 （ 2）模型求解 運輸廚余垃圾的拖車所占比率： 1 3 1 2 1 31 1 2 2 3 31 1 11 1 3 1 2 1 31 1 2 2 3 31 1 15 ( )5 ( )i i i i i ii i ii i i i i i i Y i i Z ii i ix D x D x Dx D x D x D Y D Z D? ? ? ?? ? ?? ? ? ? ? ??? ? ? ? ? ? ? ? ? ?? ? ?? ? ? 運輸焚燒垃圾的拖車所占比率： 2 1 3 1 2 1 31 1 2 2 3 31 1 15 ( )i Y ii i i i i i i Y i i Z ii i iYDx D x D x D Y D Z D?? ? ???? ? ? ? ? ? ? ? ? ?? ? ? 運輸填埋垃圾的拖車所占比率： 3 1 3 1 2 1 31 1 2 2 3 31 1 15 ( )i Z ii i i i i i i Y i i Z ii i iZDx D x D x D Y D Z D?? ? ???? ? ? ? ? ? ? ? ? ?? ? ? （ 2）求解車輛的分配 用加權(quán)載荷法確定每類具體方法如下： 表 5. 垃圾轉(zhuǎn)運站最終聚類結(jié)果 車輛類別 所占比率 車輛數(shù)量 運輸廚余垃圾的車輛 5 運輸焚燒垃圾的車輛 4 運輸填埋 垃圾的車輛 7 8 模型二： TSP模型 —— 清運路線的設(shè)計 （ 1）焚燒垃圾的清運路線 通過對同中所給數(shù)據(jù)的分析，以及相關(guān)資量的查閱，我們決定采用 TSP 模型對問題進行求解。 （ 1） 模型 )38,3,2,1,13,3,2,1。 以每一類內(nèi)部為約束條件，以各垃圾轉(zhuǎn)運站點的載荷加權(quán)，用 Matlab中的矩陣運算求得每一個站點至其它各個站點的最短路徑長度的加權(quán)和，最后得出將 3個大型廚余垃7 圾處理設(shè)備位置分別如下表。 以距離和各轉(zhuǎn)運站的廚余垃圾量乘積之和為運行成本，以成本值為目標(biāo)函數(shù)確定垃圾處理設(shè)備的具體位置。 3 兩種模型的比較及最終聚類結(jié)果 通過對兩種方案總費用的比較，我們得出 kmeans 聚類算法為最優(yōu)方案。然后利用 Matlab中的 pdist函數(shù)和squareform函數(shù)將坐標(biāo)轉(zhuǎn)化為距離矩陣，并利用 kMeans函數(shù)進行最短距離聚類，得到如下三部分結(jié)果： 表 3. 垃圾轉(zhuǎn)運站分類結(jié)果 類別 垃圾轉(zhuǎn)運站 一 類 玉泉站 平山村站 同樂村站 松坪山（二）站 光前站 白石洲南站 松坪山站 大沖站 沙河市場站 龍井 華僑城站 深圳大學(xué)站 科技園站 二 類 動物園站 牛城村站 陽光 (白芒關(guān)外 )站 福光站 麻勘站 白芒站 大石磡站 長源村站 塘朗站 官龍村站 新圍村站 西麗路站 三 類 九街站 大新小學(xué)站 南山村站 月亮灣大道站 北 頭站 涌下村站 前海公園站 南光站 南園站 望海路站 花果路站 南山市場 疏港小區(qū)站 通過對表 3 結(jié)果的計算和分析，我們得出：一區(qū)建立一個大型設(shè)備；二區(qū)建立以個大型設(shè)備；三區(qū)建立一個大型設(shè)備和 14 個小型設(shè)備。 Step4：重復(fù) Stept2 和 Stept3，直到達到最大迭代次數(shù)為止。 Step2：對數(shù)據(jù)集中的每個樣本點 ix ，計算其與各個聚類中心 jc 的歐式距離并獲取其類別標(biāo)號： 2( ) a r g m i n || || , 1 , 2 , . . . , 3 8 , 1 , 2 , 3ijjla b e l i i j? ? ? ?xc。聚類相似度是利用各聚類中對象的均值所獲得一個 “中心對象 ”（引力中心）來進行計算的。 表 類別 垃圾轉(zhuǎn)運站 一 類 疏港小區(qū)站 二 類 九街站 玉泉站 動物園站 平山村站 牛城村站 科技園站 同樂村站 松坪山（二）站 大新小學(xué)站 南山村站 陽光 (白芒關(guān)外 )站 月亮灣大道站 光前站 北頭站 涌下村站 白石洲南站 前海公園站 深圳大學(xué)站 官龍村站 松坪山站 南光站 南園站 福光站 新圍村站 大沖站 沙河市場站 龍井 南山市場 麻勘站 白芒站 大石磡站 長源村站 華僑城站 西麗路 塘朗站 三 類 望海路站 花果路站 根據(jù)表 2，我們得出：一區(qū)建立 92 臺小型設(shè)備；二區(qū)建立 2 臺大型設(shè)備和 8 臺小型設(shè)備；三區(qū)建立 138 臺小型設(shè)備。 （ 3）最短距離聚類模型求解 以題中所給地圖的左邊緣和下邊緣為坐標(biāo)軸建立直角坐標(biāo)系，測出 38個垃圾轉(zhuǎn)運站的相對坐標(biāo)，結(jié)果如下表。 Step2：然后按計算公式 ? ?m in , ( , )rk p k q kd d d k p q?? 計算原來各類與新類之間的距離，得到一個新的 37 階的距 離矩陣。 1. 最短距離聚類模型 （ 1）每一個轉(zhuǎn)運站看成一類，依次記為 1 2 38, , ,G G G ，構(gòu)造 38 個轉(zhuǎn)運站間的距離矩陣 1 1 1 2 1 , 3 82 1 2 2 2 , 3 83 8 ,1 3 8 , 2 3 8 , 3 8d d dd d dDd d d????????? 以距離矩陣 D 為基礎(chǔ)，利用最短距離方法聚類。 4 iN ：第二問中第 i個垃圾轉(zhuǎn)運站