【正文】 1 深圳南山區(qū)垃圾分類處理與清運方案設(shè)計 摘要 本文針對深圳市南山區(qū)的垃圾收集處理現(xiàn)狀進行建模分析。在收集分析了大量數(shù)據(jù)的基礎(chǔ)上，在南山區(qū)建立了合理的坐標(biāo)系，根據(jù)集合覆蓋模型利用 EXCEL的規(guī)劃求解工具箱給出了最佳的 35 個轉(zhuǎn)運站分布。綜合實際情況，優(yōu)化成現(xiàn)在的 28 個。首先我們把南山區(qū)劃分為兩個區(qū)域 ， 采用單工廠靜態(tài)選址的韋伯問題模型求解了垃圾處理站的理論最佳位置 ，運 用 NLP 模型驗證了所劃分區(qū)域的合理性。 然后 以環(huán)保效益為基礎(chǔ)，根據(jù)城市擴張理論 ，結(jié)合處理站的可變成本確定了處理站的實際最佳位置。利 用最短路徑的 Dijkstra 算法求解出最短輸運路線。根據(jù) Q 值法對于各個轉(zhuǎn)運站的廂數(shù)進行了合理的分配。在此基礎(chǔ)上我們又提出平均工作量原理，對輸運路線進一步調(diào)整，使得各個轉(zhuǎn)運站 ，每個司機 的 工作量 趨于平均。最后采用了 TSP 模型，對于 部分 轉(zhuǎn)運站的少量 剩余余垃圾進行統(tǒng)一輸運，使得整體輸運結(jié)構(gòu)更加合理，實現(xiàn)了以環(huán)保為基礎(chǔ)的最佳經(jīng)濟效益。 關(guān)鍵詞： 集合覆蓋模型 Dijkstra 算法 規(guī)劃求解 TSP 模型 城市擴張理論 平均工作量 Ⅰ 問題重述 垃圾分類化收集與處理是有利于減少垃圾的產(chǎn)生，有益于環(huán)境保護，同時也有利于資源回收與再利用的城 市綠色工程。在發(fā)達國家普遍實現(xiàn)了垃圾分類化，隨著國民經(jīng)濟發(fā)展與城市化進程加快，我國大城市的垃圾分類化已經(jīng)提到日程上來。 在深圳，垃圾分為四類：櫥余垃圾、可回收垃圾、有害垃圾和其他不可回收垃圾，處理的流程如下： 2 我們將運用數(shù)學(xué)建模方法對深圳市南山區(qū)的分類化垃圾的實現(xiàn)做一些研究，具體需要解決的問題是： 假定現(xiàn)有垃圾轉(zhuǎn)運站規(guī)模與位置不變條件下，給出大、小型設(shè)備（櫥余垃圾）的分布設(shè)計，同時在目前的運輸裝備條件下給出清運路線的具體方案。以期達到最佳經(jīng)濟效益和環(huán)保效果。 轉(zhuǎn)運站允許重新設(shè)計，給出大、小型設(shè)備 （櫥余垃圾）的分布設(shè)計，同時在目前的運輸裝備條件下給出清運路線的具體方案。以期達到最佳經(jīng)濟效益和環(huán)保效果。 Ⅱ 模型假設(shè) 假設(shè) 地圖上 交叉的路線均可以直接通行，不考慮立交橋的情況。 假設(shè)運輸車只能通過次干道以上的路線，認(rèn)為大部分的街坊路是無法通行的。 假設(shè)每天各個社區(qū)產(chǎn)生的垃圾是一個固定值。 假設(shè)處理站的垃圾是當(dāng)天處理完的。 在為處理站選址的過程中，假設(shè)是不受地價影響的，各種處理站的建造成本是固定的。 假設(shè)其他種類的垃圾處理設(shè)備也在廚余垃圾處理設(shè)備附近，這樣都達到了一個較好的規(guī)劃目的 ，同時我們可以從轉(zhuǎn)運站一次運送多種垃圾去處理廠。 假設(shè)每個人每天所產(chǎn)生的垃圾量是一定且相等的 ，以期達到公平原則 。 在 TSP 模型中，假設(shè)小型收集車只運廚余垃圾。 Ⅲ 符號說明 符號 對應(yīng)的含義 ( , )kkxy 第 k 個分區(qū)內(nèi)，用單工廠靜態(tài)選址的韋伯問題的模型求解得到的加權(quán)距離最小的垃圾設(shè)備選址坐標(biāo) ( , )nnab 各轉(zhuǎn)運站的坐標(biāo) ( , )n k kd x y 第 n 個轉(zhuǎn)運站到第 k 個分區(qū)的垃圾設(shè)備選址點 的直線距離 nc 表示第 k 個轉(zhuǎn)運站每天的垃圾轉(zhuǎn)運量 D 南山區(qū)的所有地點的坐標(biāo)集合 ( , )iixy 南山區(qū)地圖上任意一點的坐標(biāo) nw 第 n 個轉(zhuǎn)運站在該分區(qū)內(nèi)所占的權(quán)數(shù) ijw? 有向圖中頂點 iv 到頂點 jv 間的弧長 K 求加權(quán)最小距離時所對應(yīng)的分區(qū)內(nèi)所有垃圾站的集合 G 深圳市南山區(qū)路線有向圖 3 V 有向圖中所有頂點的集合 A 有向圖中所有弧的集合 iS 從 sv 到 tv 的最短路徑中包含的前 i 個頂點組合的集合 ( , )sPv v 表示從 sv 出發(fā)到 v 的最短距離 ( , )sTv v 表示從 sv 出發(fā)到 v 的距離 M 表示該 61 個垃圾收集站組成的集合， ? ?= 1, 2 61M … … kC 表示篩選出的第 k 座垃圾轉(zhuǎn)運站的轉(zhuǎn)運能力 iX 表示第 i座垃圾轉(zhuǎn)運站所覆蓋的垃圾收集站的集合 ()Ak 表示篩選出來的第 k 座垃圾轉(zhuǎn)運站所覆蓋的垃圾收集站的集合； ()Bi 表示可以覆 蓋第 i 座垃圾收集站的轉(zhuǎn)運站的集合，其中? ?? ?()B i k i A k?? kW 表示垃圾收集站是否位于第 k 座垃圾轉(zhuǎn)運站附近的決策變量 ikU 表示第 i座垃圾收集站是否有垃圾轉(zhuǎn)運站覆蓋的決策變量 Ⅳ 模型準(zhǔn)備 ：坐標(biāo)系的建立 為了用數(shù)學(xué)形式表達地圖上的地理位置，我們在深圳市南山區(qū)地圖上引入了以南山垃圾焚燒場為坐標(biāo)原點，題中所給地圖的實際尺寸大小為坐標(biāo)值（單位 :cm） 的平面直角坐標(biāo)系。各 轉(zhuǎn)運站的坐標(biāo)如表 1 所示： 垃圾轉(zhuǎn)運站名稱 坐標(biāo) a（ cm） 坐標(biāo) b(cm) 九街站 玉泉站 動物園站 平山村站 51 牛城村站 24 科技園站 同樂村站 松坪山（二）站 大新小學(xué)站 南山村站 4 陽光 (白芒關(guān)外 )站 月亮灣大道站 光前站 40 北頭站 涌下村站 白石洲南站 前海公園站 深圳大學(xué)站 官龍村站 松坪山站 南光站 南園站 望海路站 花果路站 福光站 新圍村站 大沖站 沙河市場站 龍井 南山市場 麻勘站 白芒站 大石磡站 長源村站 華僑城站 疏港小區(qū)站 西麗路站 塘朗站 表 1 ：垃圾處理設(shè)備的選擇 由題中所給數(shù)據(jù)可知，南山區(qū)所有垃圾轉(zhuǎn)運站每天的最大轉(zhuǎn)運量為 804 噸，跟據(jù)題中所給各種垃圾比重，櫥余垃圾占據(jù)四成，即在保證當(dāng)天的垃圾當(dāng)天處理的前提下，每天需處理櫥余垃圾 804 * (? 噸 ） 由于大小型垃圾處理設(shè)備的日處理能力分別為 200 噸 /日和 200300 公斤 /日，我們可采取如下兩種方案，從其建設(shè)及運行成本及進行比較。 方案一：兩座大型處理設(shè)備。 成本為： 4 5 0 0*2 = 9 0 0 0（ 萬 元 ） 運行費用： 150元 /噸 5 方案二：一 座大型處理設(shè)備，其余采用小型處理設(shè)備 成本為： 32 1. 6 20 045 00 + * 28 = 18 11 9. 20. 2 5 （ 萬 元 ） 運行費用： 200元 /噸 顯然，采用方案一更為節(jié)省，因此我們將在南山區(qū)選擇兩處建立大型櫥余垃圾處理設(shè)備，來優(yōu)化南山區(qū)的垃圾分類處理。 ：初步的區(qū)域劃分 由于需建設(shè)兩座垃圾處理設(shè)備，我們擬將南山區(qū)分為兩個區(qū)域來處理，各個區(qū)域個建立一座大型垃圾處理設(shè)備，各個區(qū)域內(nèi)的中轉(zhuǎn)站均將垃圾運到該區(qū)域內(nèi)垃圾處理設(shè)備。 我們作出了南山區(qū)的交 通 道路草圖，根據(jù)各個垃圾轉(zhuǎn)運站的日轉(zhuǎn)運量， 對其進行了分區(qū)（兩個區(qū)內(nèi)的垃圾轉(zhuǎn)運站日轉(zhuǎn)運量各占總轉(zhuǎn)運量的 50%），如圖 1。 圖 1 6 ：定義符號的具體表達式 ： ( , )n k kd x y 我們用兩點之間的距離公式來計算各點之間的直線距離，表達式如下： ? ? ? ?22( , )n i i i n i nd x y x a y b? ? ? ? ： D 經(jīng)過測量，我們確定了南山區(qū)的坐標(biāo)范圍如下： 10 6310 80iixy? ? ???? ? ?? ： nw 權(quán)為該轉(zhuǎn)運站的日轉(zhuǎn)運量占所有垃圾中轉(zhuǎn)站的日轉(zhuǎn)運量的比重。 1()nn NiicwNc?? ? 是 該 分 區(qū) 內(nèi) 轉(zhuǎn) 運 站 的 總 數(shù) Ⅴ 模型的建立 ：靜態(tài)選址模型（初步確定） 我們首先采用單工廠靜態(tài)選址的韋伯問題的模型 【 1】 從運輸費用最少的角度來確定垃圾處理設(shè)備的選址。在建立的坐標(biāo)系內(nèi)求使加權(quán)距離之和最小時的坐標(biāo)作為垃圾處理設(shè)備選址的基本坐標(biāo) ( , )kkxy 。 我 們建立如下的目標(biāo)函數(shù)，其中制約條件為該點的坐標(biāo)在地圖上的南山區(qū)范圍之內(nèi)。求解出的 ( , )iixy 即為該區(qū)域內(nèi)的最優(yōu)解。 ( , )m i n ( , ) ( 1 , 2)ii n n i ixy nK w d x y k? ?? . . ( , )iis t x y D? ：基于 lingo 軟件的區(qū)域劃分驗證 Lingo 中采用ＮＬＰ選址模型如下： 7 求解得到的結(jié)果與原先 分區(qū)方案 吻合 ，驗證了我們分區(qū)的合理性。 。 ：基于最短路徑 Dijkstra 算法 【 2】 的運輸路線模型 給定一個 賦權(quán)的有向圖 ( , )G V A? ,對于每一個弧 ( , )ija v v? ，對應(yīng)的權(quán)() ijw a w??? ，又給定 G 中的兩個頂點 sv ， tv 。設(shè) p 是 G 中從 sv 到 tv 的一條路，定義路 p 的權(quán)是 G 中所有弧的權(quán)之和，記為 ()wp? 。最短路問題就是要在所有從 sv到 tv 的路中，求一條權(quán)最小的路，即求一條從 sv 到 tv 的路 0p ，使 0( ) m in ( )pw p w p??? 上式對 G 中所有從 sv 到 tv 的路 p 取最小，稱 0p 是從 sv 到 tv 的最短 路。稱 0p 的權(quán)為從 sv 到 tv 的距離，記為 ( , )std v v? Dijkstra 算法的計算過程：（以 從 sv 到 tv 為例） 8 ? ? ? ?1( ) , , 1i i ij j i i jP v T v S S v k j?? ? ? ? ? ? ? ? ?? ?m ini jjjvST v T v?? ? ?()j k kjT v P v w?? 考察每個使得 ( , ) ,k j jv v A v S??且 的 jv END ? ?ijTv ??? ? ?()j k kjT v P v w??? ?()j k kjT v P v w?? YES NO NO NO ? ?? ?0 , ( 0) , ( ) 0