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