垃圾分類問題的處理與方案設計全文

1、河南理工大學2011年數學建模競賽論文答卷編號（競賽組委會填寫）：題目編號：（ A）論文題目： 垃圾分類處理與清運方案 參賽隊員信息(必填)： 姓 名年級專業(yè)班級聯(lián)系電話隊員1李迎超09信息09-2班隊員2趙亮09信息09-2班隊員3齊卓09結構工程 答卷編號（競賽組委會填寫）：評閱情況（學校評閱專家填寫）：評閱1.評閱2.評閱3. 垃圾分類處理與清運方案設計 摘要隨著大運會的開展，深圳的外觀建設和綠化都是展現深圳形象的重要措施，其中垃圾處理尤為重要，因此設計一個良好的垃圾處理與清運方案是很重要的。垃圾轉運站設置的一個重要意義在于節(jié)省運費。一般用于收集小區(qū)垃圾到轉運站的車為清運車，在本題中，題

2、目給出了深圳市南山區(qū)的垃圾轉運站的分布和轉運能力的大小，要求設計出大小櫥余設備的分布并且給出清運方案的具體設計。在設計大小櫥余設備及其分布時，運用了最短路和最少費用作為模型通過程序的編譯求出三大部分地區(qū)中的線路長短，以十年為期限。第一部分區(qū)域如果用大型設備需用1臺，選擇在動物園垃圾轉運站，此時獲得純利潤為元，若用小型設備需用815臺，此時獲得純利潤元。對于第二部分如果用大型設備需用3臺，選擇在南山市場垃圾中轉站，此時獲得純利潤為元，若用小型設備需用2475臺，此時獲得純利潤為元。對于第三部分如果用大型設備需用1臺，選擇在望海路垃圾轉運站，此時獲得純利潤為元，若用小型設備需用380臺，此時獲得純

3、利潤為元。在設計清運方案時，我們把主干道作為考慮對象并對它進行簡化，用圖論的相關知識找到每一個區(qū)域的可行方案，最終得到了一種可行的具體的清運方案。第二問題依據集合覆蓋模型,確定垃圾中轉站的待選點;進而運用整數規(guī)劃構建垃圾收運系統(tǒng)費用最小模型,。由于垃圾轉運站被重新設計，因此各個量都是不確定的，在此建立了兩個通用的集合覆蓋模型與垃圾收運系統(tǒng)費用最小模型。只要帶入確定的數據，就能得到垃圾轉運站的規(guī)模、位置以及最佳經濟效益。關鍵詞： 網格法；最短路；最短距離矩陣；C語言一、問題重述垃圾主要分為櫥余垃圾，可回收垃圾，有害垃圾和其他不可回收垃圾；為了更好地處理垃圾，引入垃圾收集、分類且盡量對櫥余垃圾及可

4、回收垃圾再處理的方法，這樣既美化了環(huán)境又節(jié)約了回收成本，達到取得一定經濟效益的目的。由于處理櫥余垃圾及可回收垃圾會產生經濟效益而后兩類垃圾只會消耗費用，并且行駛不同的路線去收集、運送垃圾會使車輛的耗油量不同，同時購買的大小型櫥余垃圾處理設備數量不同及安排位置的不同都會使經濟效益有所不同，這都涉及了最優(yōu)化方案問題。第一問是在轉運站規(guī)模與位置和深圳南山區(qū)的實際情況相同時，設計出大小型設備的分布，并且在目前運輸裝備條件下給出清運路線的具體方案。第二問是轉運站被重新設計，此時轉運站的規(guī)模與位置都是不確定的，再重新求上述問題。二、問題分析本項研究課題能為深圳市的垃圾分類化進程作出貢獻，因此具有十分重要的

5、現實意義。第一問中，在垃圾轉運站的規(guī)模與位置確定條件下，在南山地圖上通過用豎直線段與水平線段構成的網格，用網格來具體確定南山地區(qū)垃圾轉運站的具體位置和各個垃圾轉運站之間的路線。對于清運路線的選擇，可以把南山區(qū)分成若干小塊是每一小塊只含有一個轉運站，從而可以將南山地區(qū)的各個垃圾轉運站之間的復雜路線進行簡化，進一步運用最近線段等效原則，將各段曲線用豎直的直線線段與水平的直線線段來進行等效，再通過對路線等效模型的分析，可以用等效的豎直線段與水平線段的長短和網格的結合來確定各個垃圾轉運站之間的距離，從而來確定具體兩個垃圾轉運站的的最短路線，通過對模型的分析，可以求出南山區(qū)各個垃圾轉運站之間的最短路線和

6、各個垃圾轉運站之間的最短路線的長度，在設備的規(guī)劃當中，根據南山區(qū)的所有垃圾轉運站的具體分布，認為南山區(qū)北部的垃圾通過拖車運送到南山區(qū)南部地區(qū)進行處理不符合經濟效益，因此，將南山地區(qū)的垃圾轉運站分為三部分，再通過用最短路線來對設備進行規(guī)劃與分配。在第二問中由于轉運站的規(guī)模與位置都是不確定的，增加了模型建立的難度。針對垃圾收運系統(tǒng)的特點，應用了集合覆蓋模型，確定垃圾中轉站的待選點，然后再引入整數規(guī)劃構建垃圾收運系統(tǒng)費用的最小模型，從待選點選出垃圾轉運站的最優(yōu)組合，這樣對轉運站選址分階段進行了二次優(yōu)化，避免了直接運用整數規(guī)劃的復雜運算，為垃圾轉運站選址提供一種簡單易行的方法。三、模型假設（1）負責從

7、小區(qū)到轉運站運輸的車輛在每天早飯后收集垃圾;（2）清運車輛的耗油量只與所走過的路程有關；（3）清運車盡量走主干道，其次是次干道，最后才走街坊路；（4）拖車走高速路，快速路，主干道和次干道，不走街坊路；（5）垃圾處理中心在轉運站里并且所有大小型櫥余垃圾處理設備使用年限為十年，使用時不發(fā)生任何故障四、符號說明拖車從序號為的轉運站到序號為的轉運站轉運送垃圾所花費的費用拖車運行時平均噸公里所花費的費用序號為的垃圾轉運站在所服務區(qū)域內每次清運時走的總路線長（在地圖上的長度）序號為的轉運站M南山地區(qū)所有轉運站的垃圾總量序號為轉運站的垃圾總量序號為的轉運站到序號為的轉運站的路線的距離序號為的轉運站轉運的垃圾

8、總量由序號為的轉運站服務區(qū)域產生的，但不能被分類處理的垃圾總量A,B兩點的路線長度處理中心設在轉運站中，大型設備的個數處理中心設在轉運站中，小型設備的個數五、模型的建立5.1兩點之間路線長度的計算方法 由于本模型中的距離是用網格法求解的，因此，對網格法進行如下說明 如圖一所示，采用坐標點表示網格，若某一點不在網格的邊線上（例如：A點,B點）該點所在的網格的左下角點的坐標為，那么記這個網格的坐標為。那么A點所在的網格的坐標為，B點所在網格坐標為；如果點在網格的邊線上（例如C點），那么認為包含這條邊線的左側的網格的坐標為它所在的網格的坐標，那么C點所在網格坐標為。6F. DG. E . B. C4

9、O. AP20121086 4 2圖5.1 網格法計算距離舉例示意圖為了計算方便，參照實際情況，我們可以對距離的求法作出如下簡化對于任意兩點A，B：（1）如果A,B不在同一網格內并且A,B都不在網格的邊線上，對于從AB的不同路線，可以把所有路線的長度都看作從A點到的直線長度加上從點到點B的直線長度，即為+。例如圖一中A,B兩點，認為它們之間的路線長為：3+2=5。（2）如果A,B不在同一網格內或者其中一點在同一網格邊線上，對于不在邊線上的點認為它在網格的中心處，路線長度的計算與相同。例如對于圖一中的D、E距離為0.55.2最短路線的選取方法如果在兩個垃圾堆放點之間有多條路線可以選取，我們結合實

10、際情況，以在保護環(huán)境的前提下盡量使車所走路最小為原則作出如下分析：（假設下圖曲線就是選取的路線，橫豎直線構成網格） 首先在地圖上繪出水平間距相等和豎直間距相等的直線，構成網格，現假設從A點到B點有如上線路即(網格中的曲線)，將網格中的曲線運用離曲線最近的原則，用標有箭頭的連續(xù)線段來等效該曲線，要求該線段是網格中的水平線段或AABB 圖5.2.1 圖5.2.2AABB 圖5.2.3 圖5.2.4是網格中的豎直線段，而且繪制出的等效連續(xù)直線段的所有端點均勻分布于該曲線的兩側，則上述圖中標有箭頭的連續(xù)線段分別為從A到B點圖中曲線段的等效路線設A點指向B點的有向線段作為向量標準，將其分解為沿水平方向與

11、豎直方向上的向量，而且上圖中的標有箭頭的線段為向量，則有：在水平方向上從A點到B點之間的所有有向線段中，如果A與B之間存在多條曲線，其中等效有向線段中存在一條或多條水平有向線段與AB有向線段水平方向相反方向的，則那條曲線的距離長度就非AB間線路最短的，例如上圖中的與。在豎直方向上從A點到B點之間的所有有向線段中，如果A與B點之間存在多條曲線，選取每個等效有向線段中最大豎直有向線段的模按從大到小順序排列，則其中豎直有向線段中模最大的即偏離標準AB有向線段越大，則該條曲線的距離長度也非AB間線路最短的，例如上圖中的，。根據上述和的分析，則在所有A與B的所有路線中，符合與的原則，可以選取從A到B之間

12、的最短線路，用上述等效路線來算出A點到B點的距離，再通過上述網格法來估測A到B的距離，通過比例尺可以算出A到B的距離。如果在某兩個垃圾堆放點之間僅有一條路可供選擇那么就直接選取那條路作為最短路線。5.3清運方案的設計5.3.1清運車清運方案的設計例如，對于麻勘站所服務的區(qū)域我們只考慮主要的路及街道，畫出了它們的示意圖并對路口，街道口及路和街道的盡頭用字母進行編號，并且假設垃圾只存在于編號的地點。O 圖5.3在所建立的網格表上找到各點坐標：,；根據坐標關系確定個點之間的關系進而用5.1所示方法求得各關聯(lián)點之間的距離：其中在同一格內，那么=1;=1;=0;=2;=;d(F,O)=。根據求得的距離及

13、示意圖尋找清運車的可行方案：垃圾清運方案為。最后根據可行方案計算出清運車所走的路程：路線長為：=。經計算得到了其余各站清運車需要走的總路程：=6；=；=9；=14；=6；=；=24；=15；=；=；= ；=45；=；=4；=；=；=14；=13；=；=9；=；=；=14；=；=6；=；=9；=17；=9；35；=；=2；=9；=3；=10；=44；=19；=20由于耗油量僅與路程成正比，因此，對于整個南山區(qū)的清運車有： = （1）其中指第個轉運站的清運車每次清運走的總路程，每輛車每公里耗油為0.275把上述數據代入式得：=142.175現在深圳市汽油價格為8.0元/升，那么每天清運車所需油錢為

14、：142.1758=117.4元。5.3.2拖車及設備的設計由分析可知，居民產生的垃圾全部由收集車輛收集到垃圾轉運站，垃圾轉運站的轉運的垃圾由拖車拖往處理中心進行垃圾處理和回收，其余垃圾直接被拖車拉送到焚燒廠與填埋場處理，由于第一部分分別包括麻勘、陽光、白芒、牛城、大石勘、官龍村、新圍村、平山村、動物園、福光、塘朗、長源、西麗路十三個垃圾轉運站，垃圾處理中心就設在其中的某個或多個垃圾轉運站上。垃圾轉運站的地點分布于各個網格中，那么垃圾轉運站相對于零點的跨越網格數就是恒定的，序號為的垃圾轉運站在水平方向上跨越的網格數為，在豎直方向上跨越的網格數為，序號為的垃圾轉運站在水平方向上跨越的網格數，在豎

15、直方向上跨越的網格數為，由上面分析，轉運站之間的線路等效為網格上的豎直與水平線段，那么序號為的垃圾轉運站到序號為的垃圾轉運站所跨越的網格數為，也就是相當于兩不同序號的垃圾轉運站之間的路線最短距離為，那么有：=可知第一部分中各個垃圾轉運站點之間的跨越網格數，即垃圾轉運站之間的距離可以確定。 由于各個站的垃圾是均勻分布的，垃圾轉運站的垃圾量與轉運站的周圍的居民分布密度有直接關系，人口密度越大，則垃圾轉運站的垃圾總量越多，垃圾轉運站的規(guī)模越大，轉運量就也就越大，那么各個垃圾轉運站的垃圾總量，則： 其中 垃圾從序號為轉運站運送到序號為轉運站產生的費用，有： 在第一部分任意選取序號為的垃圾轉運站作為分析

16、:若選取序號為的垃圾轉運站作為垃圾處理中心，即大，小型設備設在該垃圾轉運站，其他有（）個垃圾轉運站運送到該垃圾處理中心處理。十年中一大型廚余垃圾處理設備所掙取的利潤與可回收垃圾的利潤和為:十年中一小型設備垃圾處理設備所掙取的利潤與可回收垃圾的利潤和為：通過上述分析，在第一部分地區(qū)的使其余垃圾轉運站運送垃圾到達垃圾轉運站時，在同樣的地區(qū)使用設備十年，使用大型設備產生的經濟效益大于使用小型設備產生的經濟效益可以得到在第一部分中把動物園的垃圾轉運站中設立為垃圾處理中心。在第二部分中存在二十二個垃圾轉運站，垃圾處理中心就設在其中的某個或多個垃圾轉運站上。同理，用劃網格的方法將第二部分中各個垃圾轉運站的

17、之間的最短線路求出來：有 =第二部分中各個垃圾轉運站點之間的跨越網格數，即垃圾轉運站之間的距離可以確定，由上述的網格方法可得出垃圾轉運站之間各點最短距離矩陣得：垃圾從序號為轉運站運送到序號為轉運站產生的費用： 若選取序號為的垃圾轉運站作為垃圾處理中心，即大，小型設備設在該垃圾轉運站，其他有（）個垃圾轉運站運送到該垃圾處理中心處理；其他（）個垃圾轉運站運送到該垃圾處理中心的拖車運送總費用為;十年中一個大型廚余垃圾處理設備所掙取的利潤與可回收垃圾的利潤和為:十年中一個小型設備垃圾處理設備所掙取的利潤與可回收垃圾的利潤和為：求出第一部分中使其余垃圾轉運站運送垃圾到達各個垃圾轉運站時，拖車運送總費達到

18、最?。?即 將拖車運送總費用按照從小到大順序排列，依次選出其中垃圾轉運站，選取其中從小到大的依次考慮得：若垃圾轉運站的垃圾總的轉用來的垃圾總量成倍數關系，那么就在該處理中心建造幾個大型設備若垃圾轉運站的垃圾總的轉用來的垃圾總量不成倍數，根據具體情況來分配大型垃圾處理設備若垃圾轉用來的垃圾總量/0.25的倍數，那么就在該處理中心設幾臺設備若垃圾轉用來的垃圾總量/0.25不是成倍數關系，那么處理中心就應該在第二部分中：由程序得： 由于，可以得到在第一部分中序號為30即南山市場的垃圾轉運站中設立垃圾處理中心，其大型設備的個數即等于3 246那么 .6可以得到：在十年內在第二部分中，在南山市場垃圾轉運

19、站中用大型設備處理垃圾，可以帶來的純利潤為：若如果將大型設備換作小型設備來處理，大概能產生的經濟效益為：由程序計算得： 由于，可以得到在第二部分中序號為30即南山市場的垃圾轉運站中設立垃圾處理中心，其小型設備的個數即等于2475來處理同等的垃圾: 246 通過上述分析，在第二部分地區(qū)的使其余垃圾轉運站運送垃圾到達垃圾轉運站時，在同樣的地區(qū)使用設備十年，使用大型設備產生的經濟效益遠大于使用小型設備來產生的經濟效益。同理，在第三部分，即東濱路以南地區(qū)中有花果路公廁、望海路垃圾站兩個垃圾轉運站，在在第三部分中：由程序計算得： 那么 1026可以得到：在十年內在第三部分中，在花果路公廁市場垃圾轉運站中

20、用大型設備處理垃圾，可以帶來的純利潤為：如果將大型設備換作小型設備來處理，大概能產生的經濟效益為：由程序運行得： 可以得到：在十年內在第三部分中，在南山市場垃圾轉運站中用大型設備處理垃圾，可以帶來的純利潤為：通過上述分析，在第三部分地區(qū)的使其余垃圾轉運站運送垃圾到達垃圾轉運站時，在同樣的地區(qū)使用設備十年，使用大型設備產生的經濟效益小于使用小型設備來產生的經濟效益，因此，在此區(qū)域應該選用小型設備來處理垃圾。5.4垃圾轉運站規(guī)模與位置不定垃圾收運過程是垃圾從分散到集中的過程是一個產生源高度分散、處置相對集中、產生量隨季節(jié)變化的“倒物流”系統(tǒng)。借鑒物流系統(tǒng)理論來垃圾收運“倒物流”系統(tǒng)的規(guī)劃是可行的。

21、在各種垃圾回收物流系統(tǒng)的運作方式中，轉運站起垃圾收集和運輸分開的作用。因此，垃圾轉運站的優(yōu)化選址是垃圾收運系統(tǒng)優(yōu)化研究的關鍵環(huán)節(jié)，必須研究兩個問題：其一是必須達到的運輸距離，即所謂臨界轉運距離；其二是垃圾轉運站設置的合理位置。本文針對垃圾收運系統(tǒng)的特點，首先應用集合覆蓋模型，確定垃圾中轉站的待選點，然后再引入整數規(guī)劃構建垃圾收運系統(tǒng)費用的最小模型，從待選點選出垃圾中轉站的最優(yōu)組合，這樣對轉運站選址分階段的二次優(yōu)化，避免了直接運用整數規(guī)劃的復雜運算，為垃圾轉運站選址提供一種簡單易行的方法。5.4.1垃圾中轉站待選點的確定5.4.1.1垃圾收運系統(tǒng)物流系統(tǒng)通常應用交叉中值模型、精確重心法、覆蓋模型

22、和中值模型。對于城市垃圾收運系統(tǒng)，在綜合考慮城市總體規(guī)劃、當地經濟、市政設施、交通狀況、公眾的接受認可度等影響因素，并進行現場勘探的基礎上，利用集合覆蓋模型初步確定垃圾轉運站的待選址?？紤]到垃圾站越多，環(huán)境影響點越多，因此，在不影響垃圾正常收集的前提下，參照垃圾收集密度以及當地人口密度，適當增加每座垃圾站的服務范圍，計算出每一垃圾轉運站的規(guī)模，即轉運能力，而后用最少垃圾轉運站去覆蓋所有小區(qū)。具體步驟如下：設有座小區(qū)，集合覆蓋模型為： （1）對上述（1）模型求解，可以應用分支定界的求解方法進行精確計算，但計算過程復雜且運算量較大。因此，本研究選用啟發(fā)式算法進行求解，所得結果可能不是最優(yōu)解，但必定

23、是可行解，據此初步確定垃圾轉運站的待選點，為二次優(yōu)化做準備。5.2.2垃圾轉運站選址優(yōu)化模型的建立在確定了垃圾轉運站的待選點后，運用整數規(guī)劃法建立整個垃圾收運系統(tǒng)總費用最小模型，實現總體優(yōu)化。5.2.2.1模型提出整個垃圾收運過程中所發(fā)生的費用主要取決于規(guī)劃期內垃圾從小區(qū)到轉運站的運輸費用，垃圾從轉運站到垃圾處理中心、南山垃圾焚燒廠、下坪固體廢棄物填埋廠的運輸費用，大小型廚余垃圾處理設備的投資費用與運行成本，最后還有司機的工資。這些費用彼此相互關聯(lián)相互制約，均與轉運站位置、規(guī)模密切相關。5.2.2.2垃圾收運系統(tǒng)費用最小模型 （2）式中，為規(guī)劃使用年限，為第座小區(qū)運往第座轉運站單位運輸量單位距

24、離的費用，為第i座小區(qū) 運往第k 座轉運站的日運輸垃圾量， 為第i座小區(qū)運往第k座轉運站運輸距離 ，為第k座轉運站運往第j座垃圾處理中心單位運輸量單位距離的費用， 為第k座轉運站運往第j座處理場日運輸垃圾量， 為第k座轉運站運往第j座處理場運輸距離， 為規(guī)劃期內待購買的大小型設備的固定投資， E為大小型設備的運行成本， Qmin為中轉站建設的最小控制規(guī)模， Qmax為中轉站建設的最大控制規(guī)模。六、模型評價（1）針對垃圾收運系統(tǒng)的特點，利用網格法確定兩點的位置與距離，,引入逆向物流理論,應用集合覆蓋模型,確定垃圾中轉站的待選點;進而運用整數規(guī)劃構建垃圾收運系統(tǒng)費用現值最小模型,從待選點中選出垃圾

25、中轉站的最優(yōu)組合。（2）通過對中轉站選址分階段的兩次優(yōu)化，避免了整數規(guī)劃復雜的運算，實際應用性好為城市垃圾轉運站選址提供了一種簡單易行的方法.(3)本模型采用網格法測定兩點的距離，再加上使用粗糙的比例尺會使某些點間的距離不太準確，影響結論數據的準確度。七、參考文獻1 姜啟源，謝金星，葉俊.數學模型（第三版）.北京：高等教育出版社，20032王宏志，韓志明.C語言程序設計（第二版）.中國鐵道出版社，20093蔡臨寧.物流系統(tǒng)規(guī)劃建模及實例分析M.北京：機械工業(yè)出版社，3043附錄：附錄1：對轉運站的編號編號垃圾轉運站名稱編號垃圾轉運站名稱編號垃圾轉運站名稱1九街站14北頭站27大沖站2玉泉站15涌下村站28