生活垃圾處理問(wèn)題4001浙江林學(xué)院數(shù)學(xué)建模競(jìng)賽

1、承 諾 書我們仔細(xì)閱讀了中國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽的競(jìng)賽規(guī)則.我們完全明白，在競(jìng)賽開始后參賽隊(duì)員不能以任何方式（包括電話、電子郵件、網(wǎng)上咨詢等）與隊(duì)外的任何人（包括指導(dǎo)教師）研究、討論與賽題有關(guān)的問(wèn)題。我們知道，抄襲別人的成果是違反競(jìng)賽規(guī)則的, 如果引用別人的成果或其他公開的資料（包括網(wǎng)上查到的資料），必須按照規(guī)定的參考文獻(xiàn)的表述方式在正文引用處和參考文獻(xiàn)中明確列出。我們鄭重承諾，嚴(yán)格遵守競(jìng)賽規(guī)則，以保證競(jìng)賽的公正、公平性。如有違反競(jìng)賽規(guī)則的行為，我們將受到嚴(yán)肅處理。我們參賽選擇的題號(hào)是（從a/b/c/d中選擇一項(xiàng)填寫）： c 我們的參賽報(bào)名號(hào)為（如果賽區(qū)設(shè)置報(bào)名號(hào)的話）： 4001 所屬學(xué)校（請(qǐng)

2、填寫完整的全名）： 重慶郵電大學(xué) 參賽隊(duì)員 (打印并簽名) ：1. 劉傳巧 2. 趙 星 3. 趙 宇 指導(dǎo)教師或指導(dǎo)教師組負(fù)責(zé)人 (打印并簽名)： 鄭繼明 日期： 2011 年 7 月 12 日賽區(qū)評(píng)閱編號(hào)（由賽區(qū)組委會(huì)評(píng)閱前進(jìn)行編號(hào)）：生活垃圾管理系統(tǒng)的數(shù)學(xué)建模摘要本文通過(guò)建立一系列模型，對(duì)城市垃圾收運(yùn)路線的優(yōu)化和垃圾收運(yùn)車輛的調(diào)度進(jìn)行了研究。通過(guò)分析，本文類比旅行推銷員問(wèn)題（tsp），將問(wèn)題轉(zhuǎn)化成圖論相關(guān)問(wèn)題進(jìn)行分析。對(duì)于問(wèn)題一：考慮到實(shí)際生活中垃圾收運(yùn)點(diǎn)的垃圾一般是運(yùn)往某個(gè)固定的中轉(zhuǎn)站進(jìn)行處理，本文通過(guò)曼哈頓距離分類將垃圾收運(yùn)點(diǎn)分到最近中轉(zhuǎn)站，從而將多中轉(zhuǎn)站轉(zhuǎn)化成一個(gè)中轉(zhuǎn)站來(lái)進(jìn)行分析。

3、在此基礎(chǔ)上，本文首先建立最佳h圈模型，得到垃圾收運(yùn)的路線，然后，本文將多垃圾收運(yùn)車輛簡(jiǎn)化成首先由一輛車沿該路線收運(yùn)垃圾，從而得到了垃圾收運(yùn)的多條子路線，并計(jì)算用時(shí)和路線長(zhǎng)度，最后將車輛的工作區(qū)間條件引入進(jìn)行收運(yùn)路線的具體分配，同時(shí)，將子路線進(jìn)行更均勻的分配有利于提高模型的魯棒性，于是本文進(jìn)一步建立了線性規(guī)劃模型。然而，本文進(jìn)一步分析發(fā)現(xiàn)，垃圾收運(yùn)車每次收運(yùn)到最大載重量便返回，之后又到另一個(gè)垃圾站進(jìn)行收運(yùn)，用h圈確定的路線進(jìn)行收運(yùn)并不一定是最優(yōu)的路線。于是，本文又建立了各垃圾收運(yùn)站點(diǎn)之間的最小生成樹模型，并在保證增加距離最小的情況下對(duì)最小生成樹的節(jié)點(diǎn)進(jìn)行修正將最小生成樹修正，消除分支，簡(jiǎn)化模型。

4、通過(guò)對(duì)兩個(gè)模型得到的結(jié)果進(jìn)行比較便可得到較優(yōu)的收運(yùn)方案。對(duì)于問(wèn)題二：本文首先運(yùn)用matlab軟件作出散點(diǎn)圖，對(duì)附錄中的數(shù)據(jù)進(jìn)行初步的分析，發(fā)現(xiàn)車庫(kù)大致在收運(yùn)點(diǎn)群的中心，而中轉(zhuǎn)站的位置在收運(yùn)點(diǎn)的一端。在數(shù)據(jù)分析的基礎(chǔ)上，本文采用二次修正法對(duì)h圈模型進(jìn)行了求解，同時(shí)用附錄的數(shù)據(jù)對(duì)最小生成樹進(jìn)行了求解，經(jīng)過(guò)比較，最小生成樹模型得到的結(jié)果更優(yōu)，于是本文采用最小生成樹模型進(jìn)一步改進(jìn)，通過(guò)整數(shù)規(guī)劃模型完成了垃圾清運(yùn)子路線的劃分、車輛數(shù)目的確定及具體的調(diào)運(yùn)方案，得到總的運(yùn)行距離是710628米，總耗時(shí)為57.0067小時(shí)，并制定出了8輛車的具體運(yùn)行路線。8輛車調(diào)運(yùn)的良好效果，充分說(shuō)明了本文所建模型具有較好的

5、魯棒性。最后本文對(duì)模型的優(yōu)缺點(diǎn)進(jìn)行分析，希望本文所建立的模型能夠很好的運(yùn)用到相關(guān)問(wèn)題的求解中，幫助相關(guān)部門制定相關(guān)的方針。關(guān)鍵詞：tsp 最小生成樹 兩邊逐次修正法 整數(shù)規(guī)劃 垃圾收運(yùn)車輛調(diào)運(yùn)1 問(wèn)題重述隨著人類生產(chǎn)和生活的不斷發(fā)展，由此而產(chǎn)生的垃圾對(duì)生態(tài)環(huán)境及人類生存帶來(lái)極大的威脅，成為重要的社會(huì)問(wèn)題。城市生活垃圾的年增長(zhǎng)速度達(dá)8-10%，嚴(yán)重污染環(huán)境。城市垃圾管理包括計(jì)劃、組織、行政、金融、法律和工程等多方面，并涉及到城市生活垃圾收運(yùn)、運(yùn)輸和處置。而中國(guó)目前處置水平低，管理辦法不多，更是急待解決的問(wèn)題。在這方面，世界許多國(guó)家在謀求解決城市生活垃圾過(guò)程中，產(chǎn)生出許多好的辦法，并在此過(guò)程中總結(jié)

6、了經(jīng)驗(yàn)和教訓(xùn)。城市垃圾自其產(chǎn)生到最終被送到處置場(chǎng)處理，需要環(huán)衛(wèi)部門對(duì)其進(jìn)行收運(yùn)與運(yùn)輸，這一過(guò)程稱為城市垃圾的收運(yùn)。收運(yùn)過(guò)程可簡(jiǎn)述如下：某城市有多個(gè)行政區(qū)，每個(gè)區(qū)內(nèi)均有一個(gè)車庫(kù)，假設(shè)某一車庫(kù)擁有最大裝載量為 w 的垃圾收運(yùn)車 k 輛，并且該區(qū)的垃圾收運(yùn)點(diǎn)（待收運(yùn)垃圾的點(diǎn)）有 n個(gè)，該城市共有垃圾中轉(zhuǎn)站 p 座。每天 k 輛垃圾收運(yùn)車從車庫(kù)出發(fā)，經(jīng)過(guò)收運(yùn)點(diǎn)收運(yùn)垃圾，當(dāng)垃圾負(fù)載達(dá)到最大裝載量時(shí)，垃圾收運(yùn)車運(yùn)往中轉(zhuǎn)站，在中轉(zhuǎn)站卸下所有收運(yùn)的垃圾，然后再出站收運(yùn)垃圾，如此反復(fù)，直到所有收運(yùn)點(diǎn)的垃圾都被收運(yùn)完，垃圾收運(yùn)車返回車庫(kù)。以上收運(yùn)過(guò)程均在各點(diǎn)的工作區(qū)間之內(nèi)完成。請(qǐng)利用數(shù)學(xué)方法建立以下問(wèn)題的數(shù)學(xué)模型

7、，并求解模型，對(duì)模型的結(jié)果做出合理分析和解釋。1. 查閱相關(guān)文獻(xiàn)，建立垃圾收運(yùn)路線的數(shù)學(xué)模型，設(shè)計(jì)出有效的算法，使垃圾收運(yùn)車輛盡可能少，行車?yán)锍瘫M可能短或者垃圾收運(yùn)時(shí)間盡可能少？ 2.針對(duì)附錄中給出的數(shù)據(jù)，求解模型。并且對(duì)模型的適用性、算法的穩(wěn)健性做出分析。2 模型假設(shè)（1）每個(gè)待收運(yùn)的垃圾收運(yùn)點(diǎn)的垃圾日常量在很小的范圍內(nèi)浮動(dòng)，近似可以不變；（2） 垃圾收運(yùn)點(diǎn)兩兩之間的權(quán)重設(shè)為兩點(diǎn)之間的各自坐標(biāo)軸的橫坐標(biāo)和豎坐標(biāo)之差的絕對(duì)值；（3）每一個(gè)垃圾收運(yùn)點(diǎn)與收運(yùn)點(diǎn)之間和相對(duì)應(yīng)的中轉(zhuǎn)站及車庫(kù)均有路徑；（4）車輛在任意兩站中途不停車，并且保持穩(wěn)定的速率，同時(shí)忽略車輛在起步、剎車、拐彎的時(shí)間消耗；（5）假設(shè)

8、垃圾收運(yùn)車的庫(kù)存數(shù)量是充裕的，能夠保證每天按時(shí)完成垃圾收運(yùn)任務(wù)；（6）運(yùn)輸車在每個(gè)垃圾收運(yùn)點(diǎn)及中轉(zhuǎn)站除裝卸垃圾時(shí)間外都沒有其它額外時(shí)間開銷；（7）若垃圾收運(yùn)車在每天的最后一趟沒有滿載，可以回到中轉(zhuǎn)站將垃圾卸載，但是之前每趟必須滿載。3 主要符號(hào)說(shuō)明一個(gè)中轉(zhuǎn)站的垃圾收運(yùn)點(diǎn)的數(shù)量每?jī)蓚€(gè)垃圾收運(yùn)點(diǎn)之間的路徑加權(quán)無(wú)向圖完備圖第個(gè)點(diǎn)到第個(gè)點(diǎn)的距離每條邊的權(quán)重，等于各點(diǎn)間的距離垃圾收運(yùn)車經(jīng)過(guò)所有路線的總時(shí)間第輛車體通過(guò)路線花費(fèi)的總時(shí)間經(jīng)過(guò)第段線路所花費(fèi)的時(shí)間4 問(wèn)題分析隨著垃圾量的日益增多，對(duì)環(huán)境的污染也越來(lái)越大，甚至危害了我們的人身安全，對(duì)垃圾的管理也越來(lái)越重要。為了使得管理費(fèi)用有一定的降低，因此有必要

9、對(duì)垃圾管理進(jìn)行研究，并提出相應(yīng)的建議。針對(duì)問(wèn)題一：建立垃圾收運(yùn)路線的數(shù)學(xué)模型。首先，查閱相關(guān)資料，了解垃圾運(yùn)輸車的運(yùn)作模式。將多垃圾收運(yùn)車簡(jiǎn)化成由一輛車收運(yùn)垃圾，并每當(dāng)垃圾收運(yùn)車裝滿則返回中轉(zhuǎn)站卸掉垃圾再到垃圾收運(yùn)點(diǎn)收運(yùn)垃圾的問(wèn)題，即簡(jiǎn)化為一輛垃圾收運(yùn)車遍歷所有垃圾收運(yùn)點(diǎn)的最短路徑問(wèn)題（），在此基礎(chǔ)上我們可以建立最佳圈模型和最小生成樹模型。然后采用各自模型的算法求解，即運(yùn)用對(duì)應(yīng)于最佳圈模型的二次修正算法，對(duì)應(yīng)于最小生成樹模型的最小生成樹算法。可求出一輛垃圾收運(yùn)車收運(yùn)完所有垃圾收運(yùn)點(diǎn)的垃圾所需要的總的路程和總的時(shí)間。然后對(duì)比這兩種模型，從路程和時(shí)間上分析它們的優(yōu)缺點(diǎn)，找到適合此題的較好的模型。并

10、且，根據(jù)垃圾收運(yùn)車的最大裝載量（）與最佳圈或最小生成樹的路線，確定出垃圾收運(yùn)的多條子路線。在得到從中轉(zhuǎn)站到垃圾收集點(diǎn)收運(yùn)垃圾再回到中轉(zhuǎn)站的子路線的基礎(chǔ)上，計(jì)算出每條子線路所需要的時(shí)間和行駛的路程，同時(shí)計(jì)算從車庫(kù)收運(yùn)同一條子線路上的垃圾然后到中轉(zhuǎn)站所需要的時(shí)間和路程，再計(jì)算出對(duì)應(yīng)子線路上的時(shí)間差和路程差。由每輛垃圾收運(yùn)車必須從車庫(kù)出發(fā)的前提，將從車庫(kù)出發(fā)可以節(jié)省時(shí)間較多，行駛路程較短的子路段合理分配給每輛垃圾收運(yùn)車。從而建立0-1型整數(shù)規(guī)劃模型，求解出垃圾收運(yùn)車的收運(yùn)路線。針對(duì)問(wèn)題二，利用數(shù)據(jù)對(duì)所建立的模型進(jìn)行求解和對(duì)應(yīng)算法分析。首先，根據(jù)題目中給定的垃圾收運(yùn)點(diǎn)、中轉(zhuǎn)站及車庫(kù)的數(shù)據(jù)，利用以及軟件

11、，用所建的模型和相對(duì)應(yīng)的算法，對(duì)垃圾收運(yùn)車的路線進(jìn)行求解，確定垃圾收運(yùn)車的最短路徑路線。再將最佳圈的模型和最小生成樹的模型求得的各自的最短路徑路線進(jìn)行分析，比較兩種模型下的總的路程和總的時(shí)間，然后確定在該數(shù)據(jù)情況下的較優(yōu)模型。從而確定出一輛垃圾收運(yùn)車的情況下的收運(yùn)子路線。接著，根據(jù)子路線，求解0-1型整數(shù)規(guī)劃模型，從而確定出多輛垃圾收運(yùn)車從車庫(kù)出發(fā)收運(yùn)完垃圾并回到車庫(kù)的路線，進(jìn)而求解出垃圾收運(yùn)車的數(shù)量，行車的總路程以及垃圾收運(yùn)的總時(shí)間。最后，根據(jù)求得的垃圾收運(yùn)路線，對(duì)所建立的模型進(jìn)行適用性，以及算法的穩(wěn)健性進(jìn)行分析。5 模型建立與求解5.1 模型準(zhǔn)備5.1.1 曼哈頓距離分類根據(jù)實(shí)際生活中垃圾

12、處理情況，某個(gè)垃圾點(diǎn)的垃圾一般是運(yùn)往一個(gè)固定的中轉(zhuǎn)站進(jìn)行出來(lái)，亦即是說(shuō)某個(gè)中轉(zhuǎn)站固定處理一些垃圾收運(yùn)點(diǎn)運(yùn)來(lái)的垃圾，于是多個(gè)中轉(zhuǎn)站問(wèn)題可以轉(zhuǎn)化成單個(gè)中轉(zhuǎn)站來(lái)進(jìn)行分析。并且通常垃圾點(diǎn)的垃圾是運(yùn)往與之較近的中轉(zhuǎn)站進(jìn)行處理的，于是本文采用以下方法確定垃圾點(diǎn)的歸屬問(wèn)題（由某個(gè)垃圾中轉(zhuǎn)站處理）：其中：為第個(gè)中轉(zhuǎn)站，為第個(gè)垃圾收運(yùn)點(diǎn)，為所求的第垃圾收運(yùn)點(diǎn)到第個(gè)中轉(zhuǎn)站的距離，表示第垃圾收運(yùn)點(diǎn)到第個(gè)中轉(zhuǎn)站。5.1.2垃圾運(yùn)輸車運(yùn)輸時(shí)間和路程（1）垃圾收運(yùn)車第趟收運(yùn)第個(gè)垃圾點(diǎn)的垃圾時(shí)需要的裝載時(shí)間:其中，表示垃圾收運(yùn)車第趟的第個(gè)垃圾點(diǎn)裝載所有垃圾需要的時(shí)間。（2）垃圾收運(yùn)車第趟收運(yùn)垃圾回到中轉(zhuǎn)站卸下垃圾需要時(shí)間：

13、（3）垃圾收運(yùn)車第趟收運(yùn)垃圾需要的行駛路程其中，表示一趟經(jīng)過(guò)的收運(yùn)點(diǎn)個(gè)數(shù)（4）垃圾收運(yùn)車第趟收運(yùn)垃圾需要的時(shí)間：（5）垃圾收運(yùn)車第趟收運(yùn)垃圾需要的總時(shí)間（6）收運(yùn)完垃圾需要的時(shí)間（不含回車庫(kù)的時(shí)間）5.2 模型一：最佳圈模型5.2.1最佳圈模型描述通過(guò)對(duì)題目的分析和上述所寫出的各種時(shí)間和路程的算法形式，此題我們用圖論的知識(shí)解答：我們把垃圾收運(yùn)點(diǎn)、車庫(kù)抽象為圖的頂點(diǎn)集，把它們兩兩之間的距離抽象為圖的邊集。建立無(wú)向帶權(quán)鄰接矩陣如下：哈密爾頓圖：經(jīng)過(guò)的每個(gè)頂點(diǎn)正好一次的圈。最佳圈是指在加權(quán)圖中，權(quán)最小的哈密爾頓圈。判定一個(gè)加權(quán)圖是否存在哈密爾頓圈是一個(gè)問(wèn)題，而它的完備加權(quán)圖（中每條邊的權(quán)等于頂點(diǎn)與在

14、圖中最短路徑的權(quán)）中一定存在哈密爾頓圈，所以在完備圖中尋找最佳圈。該過(guò)程采用兩邊逐次修正法并利用矩陣翻轉(zhuǎn)實(shí)現(xiàn)。完備圖如下：圖1：完備圖5.2.2最佳圈的確定二邊逐次修正法的算法步驟如下：（1）任取初始圈： 圖2：初始圈（2）對(duì)所有的，若則在中刪去邊和而加入邊和，形成新的圈，即：圖3：圈的變換（1） 對(duì)重復(fù)步驟（2），直到條件不滿足為止，最后得到的即為所求5.2.3 模型求解（1）根據(jù)以上描述即所給的數(shù)據(jù)，建立包含垃圾收運(yùn)點(diǎn)、中轉(zhuǎn)站、車站的鄰接矩陣，如下所示：根據(jù)以上所建立的鄰接矩陣畫出散列圖，如下圖所示：圖4：散點(diǎn)圖（3）在畫出圈前，為了使看到翻轉(zhuǎn)效果和更直觀的確定優(yōu)化后圈所走的路線，在第一行

15、和最后一行給距離矩陣加上了一個(gè)點(diǎn)的排列順序的框，又為了是此矩陣成為一個(gè)方陣，在第一列和最后一列加上0（或或者在距離矩陣第一行、列和最后一行、列同時(shí)加上一個(gè)點(diǎn)的排列順序的框），具體矩陣如下：由上矩陣為對(duì)稱陣，其上三角或下三角都可以為圈的初始圈，這里選取上三角的元素對(duì)應(yīng)的頂點(diǎn)為初始圈的路線，即： （4）經(jīng)過(guò)第一次二次修正法得到的第一個(gè)所得圈矩陣及權(quán)重如下：（5）經(jīng)過(guò)第二次二次修正法得到的第二個(gè)圈，可以得到矩陣和權(quán)重，這里為了簡(jiǎn)便，只取它的重要權(quán)重。（6） 經(jīng)過(guò)第三次二次修正法得到的第三個(gè)圈，同樣可得到它的矩陣和權(quán)重，權(quán)重。（7） 經(jīng)過(guò)第四次二次修正法得到的第四個(gè)圈，矩陣如下所示：由以上得到的矩陣可

16、知，第三個(gè)和第四個(gè)圈的權(quán)重接近，所以將第四次得到的結(jié)果作為近似最優(yōu)解，由此可得到近似最佳圈：即圈為垃圾運(yùn)輸車的行駛路線，畫出其圖形如下：圖5：垃圾車在圈中的路線（8） 從以上所算出的結(jié)果，根據(jù)垃圾收運(yùn)車每次運(yùn)輸?shù)睦坎淮笥谳d重量，做出畫出垃圾運(yùn)輸車的路線圖，如下圖所示：圖6：圈情況下的運(yùn)輸車行駛路線圖 按照本模型所得結(jié)果，共需運(yùn)送垃圾25次，總共花費(fèi)時(shí)間70.66405小時(shí)，行駛的總路程為1113199米。5.3模型二：最小生成樹模型5.3.1最小生成樹模型描述由以上所建立的模型，它采用的是最佳圈的方法求出車輛運(yùn)輸路線，得到接近全局最短路徑。以上模型它是把垃圾中轉(zhuǎn)站和車站都納入到求最佳圈中，

17、而且沿著此路徑將所有的點(diǎn)進(jìn)行劃分相應(yīng)的塊中，所得到的結(jié)果不是很理想。而我們知道車庫(kù)到中轉(zhuǎn)站的路程是固定的，車輛從車庫(kù)出發(fā)先到達(dá)相對(duì)于中轉(zhuǎn)站較遠(yuǎn)的垃圾收運(yùn)點(diǎn)，車裝滿就直接到達(dá)中轉(zhuǎn)站，那么它再次從中轉(zhuǎn)站出發(fā)到收運(yùn)垃圾時(shí)的路線會(huì)越來(lái)越短，這對(duì)離中轉(zhuǎn)站較遠(yuǎn)的垃圾收運(yùn)點(diǎn)，如果有很多的垃圾，就會(huì)減少一定的路程，所以我們把中轉(zhuǎn)站和車庫(kù)抽離出來(lái)，只是在垃圾收運(yùn)點(diǎn)中找到最小路徑進(jìn)一步優(yōu)化模型，采用下述的最小生成樹的方法求解出車輛運(yùn)輸路線的全局最短路徑。5.3.2最小生成樹的建立根據(jù)垃圾收運(yùn)車最大裝載量和數(shù)據(jù)分布將所給數(shù)據(jù)分成若干個(gè)區(qū)域，每個(gè)區(qū)域均有若干個(gè)點(diǎn)，通過(guò)圖論生存最小生成樹，找到連接所有垃圾收運(yùn)的點(diǎn)的最小

18、路徑。次模型我們主要采用算法求出所分區(qū)域的最小生成樹，建立方法如下：（1）建立以兩點(diǎn)間距離與垃圾站的乘積為權(quán)重的鄰接矩陣其中一兩點(diǎn)間的的距離為權(quán)重，計(jì)算公式如下：（2）從候選邊表.初始為空集，當(dāng)選定了一個(gè)頂點(diǎn)時(shí)，把與此頂點(diǎn)相連的邊逐漸寫入中；為一個(gè)數(shù)組，初始值為空，它是用來(lái)存放最小生成樹的邊。（3）從候選邊中選出最短邊；（4）調(diào)整候選邊集；（5）重復(fù)（2），（3）直到中含有條邊。通過(guò)上述算法得到的線路即為連接各點(diǎn)的最小生成樹，其特點(diǎn)邊權(quán)和最小。但是，垃圾的收運(yùn)不是簡(jiǎn)單的連接問(wèn)題，而最小生成樹形成的路線需要在樹權(quán)路線上回返，這樣就會(huì)使路程增加。因此為了使得路線更短，我們?cè)谧钚∩蓸涞膱D形基礎(chǔ)上比

19、較樹杈與其相鄰的權(quán)邊的權(quán)重，以增加權(quán)重最小的方法，把葉子節(jié)點(diǎn)加進(jìn)最小生成樹的主干節(jié)點(diǎn)中。這樣就可以將所分區(qū)域的所有垃圾收運(yùn)點(diǎn)串聯(lián)起來(lái)，形成一條鏈，且其權(quán)和最小，這條鏈就是車輛運(yùn)輸路線。5.3.3 最小生成樹的修正 通常按照最小生成樹模型得到的最小生成樹帶有分支，如下所示：圖7：分支示意圖 分支的存在使問(wèn)題更加復(fù)雜化，于是本文在保證增加距離盡量少的前提下，采用如下模型對(duì)最小生成樹進(jìn)行修正，進(jìn)而簡(jiǎn)化問(wèn)題。進(jìn)行修正點(diǎn)的確定，首先需要找出待修正的點(diǎn)，同時(shí)需要修正后增加的距離盡可能短，本文的具體修正方法見下文。（1）修正點(diǎn)的確定修正點(diǎn)的確定是根據(jù)以求最小生成樹的鄰接矩陣來(lái)確定的，修正點(diǎn)它不同于其它點(diǎn)的是

20、它的度數(shù)要大于2。根據(jù)最小生成樹以任意點(diǎn)開始建立鄰接矩陣，如下形式：由鄰接矩陣，計(jì)算它每一行的和，若它的和大于2則為修正點(diǎn)。利用深度優(yōu)先的方法并且建立索引，找到修正點(diǎn)的鄰近點(diǎn)和他所連的葉子節(jié)點(diǎn)。設(shè)為頂點(diǎn)個(gè)數(shù)，為第行，為第列（2）鏈的形成通過(guò)上述找到的點(diǎn)，按照修正點(diǎn)的不同，用不同的數(shù)組存儲(chǔ)。然后進(jìn)行加邊找到取其邊權(quán)最小，進(jìn)行修正，形成鏈。這里采用的是窮舉的方法，找出它的最短路線形成鏈。設(shè)、連接在樹的主干上的節(jié)點(diǎn)，及其它點(diǎn)為分支節(jié)點(diǎn)。    圖8：鏈的生成示意圖通過(guò)連接、，對(duì)經(jīng)過(guò)的所有路線，找到權(quán)重之和最短的路線。5.4最小生成樹模型的求解按照前面的最小生成

21、樹模型，本文將附錄中的數(shù)據(jù)代入模型，并運(yùn)用matlab軟件反正求解，具體的求解結(jié)果如后文所示。5.4.1最小生成樹的生成根據(jù)以上建立模型時(shí)對(duì)最小生成樹的形成的描述,按照求解步驟，利用題目中所給數(shù)據(jù)畫出最小生成樹，圖形如下：圖9：最小生成樹5.4.2最小生成樹的修正由以上所生成的最小生成樹，可以明確它的分支和與這條分支所相連的相鄰點(diǎn)，用語(yǔ)言程序編程，依次求出它每個(gè)分支融入到主干的最短路，得到鏈，圖形如下：圖10：最小生成樹由上圖可知：在垃圾收運(yùn)時(shí)，垃圾收運(yùn)車從車庫(kù)出發(fā)到相對(duì)于中轉(zhuǎn)站而言的最遠(yuǎn)點(diǎn)，沿上圖路線收運(yùn)垃圾，將垃圾送到中轉(zhuǎn)站后再回到車庫(kù)，此即為最優(yōu)路線。5.4.3 垃圾收運(yùn)車路線圖和h圈模

22、型類似，在對(duì)最小生成樹進(jìn)行修正后，本文對(duì)垃圾車的具體路線進(jìn)行仿真，同時(shí)計(jì)算出垃圾車收運(yùn)次數(shù)、總耗時(shí)及總行駛距離，收運(yùn)仿真圖如下：圖11：垃圾收運(yùn)路線（最小生成樹模型）按照本模型所得結(jié)果，共需運(yùn)送垃圾25次，總共花費(fèi)時(shí)間65.85361小時(shí)，行駛的總路程為1019034米。5.5 兩種模型的比較這里，本文對(duì)前面建立的兩個(gè)模型得到的結(jié)果進(jìn)行對(duì)比，以便選擇較優(yōu)的模型進(jìn)行后面的進(jìn)一步優(yōu)化：表一：二邊逐次修正法與最小生成樹對(duì)比表方法二邊逐次修正法最小生成樹總時(shí)間（）70.6640565.85361總路程（）11131991019034總趟數(shù)2525從上表可以看出，最小生成樹模型所求得的結(jié)果較h圈模型得到

23、的結(jié)果所需時(shí)間更少，總的行駛路程更短，因此本文選取最小生成樹模型進(jìn)行下一步分析優(yōu)化。5.6 最小生成樹模型的改進(jìn)5.6.1 出發(fā)點(diǎn)的改進(jìn)考慮到由最小生成樹轉(zhuǎn)換成的鏈有兩端，因此有兩種不同的垃圾收運(yùn)方案。第一種方案是從編號(hào)為1的點(diǎn)即根節(jié)點(diǎn)開始走，第二種方案是從鏈的另一端即尾節(jié)點(diǎn)開始，由此可以得到兩種方案的不同數(shù)據(jù)，見表二。出現(xiàn)這種情況的原因分析:（1）從起始點(diǎn)開始，運(yùn)輸車裝滿后到達(dá)中轉(zhuǎn)站的距離越來(lái)越大，而且到末端時(shí)，末端的垃圾收運(yùn)點(diǎn)中的垃圾它并不能運(yùn)輸完，可能會(huì)有剩，因此它會(huì)增加總的路程，導(dǎo)致時(shí)間增多。（2）從末端開始，運(yùn)輸車裝滿后到達(dá)中轉(zhuǎn)站的距離越來(lái)越短，不會(huì)出現(xiàn)上述問(wèn)題。表二：從鏈的根節(jié)點(diǎn)出

24、發(fā)與從尾節(jié)點(diǎn)的對(duì)比表出發(fā)點(diǎn)根節(jié)點(diǎn)尾節(jié)點(diǎn)總時(shí)間（）65.8536162.44995總路程（）1019034950194總趟數(shù)2525從表二可以看出，以尾節(jié)點(diǎn)最為出發(fā)點(diǎn)進(jìn)行垃圾收運(yùn)，垃圾車行駛的總路程為950194米，較以根節(jié)點(diǎn)為出發(fā)點(diǎn)有很大的改進(jìn)。原因是從尾節(jié)點(diǎn)為出發(fā)點(diǎn)，其到中轉(zhuǎn)站的距離越來(lái)越短，從中轉(zhuǎn)站出發(fā)到下一結(jié)點(diǎn)進(jìn)行垃圾所走的距離同樣也是越來(lái)越小。從結(jié)果可以看出，本文的這種改進(jìn)方案是可行的，且效果良好。5.6.2 一次收運(yùn)垃圾最少量的改進(jìn)通過(guò)時(shí)間及路程的對(duì)比，第二種方案較第一種方案更好，但是仍然存在一定的問(wèn)題。當(dāng)兩個(gè)垃圾收運(yùn)點(diǎn)的距離較遠(yuǎn)時(shí)，此路徑可能會(huì)增加路程量。為了解決此問(wèn)題，當(dāng)垃圾運(yùn)輸

25、車達(dá)到一次收運(yùn)垃圾最少量時(shí)，可以先回到中轉(zhuǎn)站卸下垃圾，再去下一個(gè)收運(yùn)點(diǎn)收運(yùn)，由此可以得到表三數(shù)據(jù)。表三：從鏈的尾節(jié)點(diǎn)出發(fā)的不同最小收運(yùn)垃圾量的對(duì)比表最小收運(yùn)垃圾量()1000950900850800750700總時(shí)間（）62.44960.90160.90561.82760.22160.45765.294總路程（）950194906910903763922520884882889998974278總趟數(shù)25262626272728未裝滿趟數(shù)1567111115由表三可知，當(dāng)最小收運(yùn)垃圾量為800時(shí)，總的時(shí)間最少，且總路程最小，其次是最小收運(yùn)垃圾量為750時(shí)，但是考慮到除最后一趟不需裝滿外，之前每

26、趟必須裝滿，而且為使總的垃圾收運(yùn)車數(shù)量盡量減少，則當(dāng)最小收運(yùn)垃圾量為800時(shí)，垃圾收運(yùn)車的數(shù)量應(yīng)該為輛，同理，當(dāng)最小收運(yùn)垃圾量為750時(shí)，垃圾收運(yùn)車的數(shù)量應(yīng)該為8輛。由表三未滿的趟數(shù)可知，這兩種情況都不滿足條件。由表三分析知，當(dāng)最小收運(yùn)垃圾量為950時(shí)，總的時(shí)間和路程是滿足條件的最有最優(yōu)情況。從而，通過(guò)軟件，即可確定在一輛垃圾收運(yùn)車的情況下，每趟從中轉(zhuǎn)站出發(fā)的收運(yùn)情況，具體如下表：表四:車輛需要總的趟數(shù)、路線及總時(shí)間趟數(shù)編號(hào)第一個(gè)點(diǎn)第二個(gè)點(diǎn)第三個(gè)點(diǎn)第四個(gè)點(diǎn)點(diǎn)的總數(shù)時(shí)間（h）距離（m）114157032.995677484522700011.953927078352461142.87883346

27、4104111725032.8357334504859130022.52048338743613160022.4222535445716234032.48646737796842631032.19235320979318121042.4273263639510102830032.742154234311302219032.5814073977112192029033.128439507911329180023.1867835206914272144033.12311505851544360023.111319497741636400023.27621153302174032423842.718

28、693425221838430022.2313532627195000011.40730716407205041374942.82823343398214947454842.6217674085222484634032.0840929158233435333941.84880725119243932031.9272672661225210020.927400合計(jì)62.449959501945.7 模型三：整數(shù)規(guī)劃模型5.7.1模型描述0-1型整數(shù)規(guī)劃是整數(shù)規(guī)劃的一種特殊形式，它的變量?jī)H取值0或1。這種只能取0或1的變量稱為0-1變量或二進(jìn)制變量。5.7.2模型建立雖然上述模型車行駛的路線是全局

29、最優(yōu)，但是它不一定滿足局部最優(yōu)。而且垃圾收運(yùn)車的出發(fā)點(diǎn)也不是從車庫(kù)，所以在將分配路段分配給垃圾收運(yùn)車時(shí)，需要考慮垃圾收運(yùn)車從車庫(kù)出發(fā)。分析易知，垃圾收運(yùn)車從中轉(zhuǎn)站出發(fā)和從車庫(kù)出發(fā)收運(yùn)垃圾的時(shí)間是不同的，由此，將從車庫(kù)出發(fā)與從中轉(zhuǎn)站出發(fā)相比，從車庫(kù)出發(fā)收運(yùn)垃圾節(jié)約的時(shí)間較多的路段平?jīng)Q分配給垃圾收運(yùn)車，即可以使垃圾收運(yùn)的總時(shí)間減少。設(shè)為從車庫(kù)出發(fā)收運(yùn)第段線路所花費(fèi)的時(shí)間，為從中轉(zhuǎn)站出發(fā)收運(yùn)第段線路所花費(fèi)的時(shí)間：為變量，當(dāng)為時(shí)表示第輛車收運(yùn)第段線路上的收運(yùn)點(diǎn)，當(dāng)為時(shí)表示第j輛車不收運(yùn)第i段線路上的收運(yùn)點(diǎn)；表示所有垃圾收運(yùn)車從車庫(kù)出發(fā)與從中轉(zhuǎn)站出發(fā)相比而節(jié)約的總時(shí)間，為垃圾收運(yùn)車的輛數(shù)，為路段的總數(shù)。

30、建立如下的模型：5.7.3模型求解首先，用軟件計(jì)算出每段線路從中轉(zhuǎn)站出發(fā)與從車庫(kù)出發(fā)收運(yùn)垃圾花費(fèi)的時(shí)間，以及從車庫(kù)節(jié)約的時(shí)間，見表五。由表四可知，第26段線路收運(yùn)的垃圾僅有100，考慮到節(jié)省收運(yùn)的時(shí)間，將第26段線路的100垃圾給未裝滿垃圾的線路裝運(yùn)，即第8、10、16、18段線路，通過(guò)計(jì)算出即第10、16段線路收運(yùn)此100垃圾最節(jié)省時(shí)間。表五：垃圾收運(yùn)車從中轉(zhuǎn)站和車庫(kù)出發(fā)的時(shí)間對(duì)比線路編號(hào)從車站出發(fā)(h)從中轉(zhuǎn)站出發(fā)(h)節(jié)約的時(shí)間(h)12.52227692.9956769230.473421.71721.95390.236732.40543332.8788333330.473442.10

31、553332.8357333330.730252.04708332.5204833330.473461.948852.422250.473472.01306672.4864666670.473481.81908332.2924833330.473491.75748032.4227803030.6653101.54401672.3764166670.8324111.38413332.3766333330.9925122.12903333.1754333331.0464132.092653.178451.0858142.22540443.3112043861.0858152.01837623.10

32、4176191.0858161.484352.027250.5429171.55211672.6379166671.0858181.3182.27530.9573191.41173192.1242318840.7125201.83502222.2305222220.3955212.62906672.6724666670.0434221.58611271.6614127450.0753231.37990931.5525092590.1726241.57886671.410566667-0.168251.841051.23055-0.611261.53050.7481-0.782再用軟件將表五數(shù)據(jù)

33、帶入表五求解，得到表六每輛垃圾收運(yùn)車的負(fù)責(zé)路線。表六：每輛車的路線表垃圾車編號(hào)負(fù)責(zé)的線路編號(hào)路程()時(shí)間()日運(yùn)垃圾量()經(jīng)過(guò)的垃圾點(diǎn)個(gè)數(shù)17、10、13（26）1042727.23913000824、12、141283637.31783000638、9、18849387.08362900842、6、22741467.74533000551、11、19467767.429430006616、17、24、25（26）769936.66954000973、15、201061346.99333000985、21、23890066.528730009合計(jì)-71062857.006724900由此，可以

34、確定每輛垃圾收運(yùn)車的路線，見下表。表七：8輛車的路線表垃圾車編號(hào)路線12345678從上表得到，每輛車經(jīng)過(guò)的垃圾點(diǎn)個(gè)數(shù)最大為9個(gè)，滿足題目條件每天最多經(jīng)過(guò)10個(gè)垃圾點(diǎn)。則此中轉(zhuǎn)站需要用8輛垃圾車，且收運(yùn)的總時(shí)間是57.0067個(gè)小時(shí)，總行駛路程為710628。6 模型評(píng)價(jià)結(jié)合我國(guó)城市生活垃圾的管理情況，盡最大能減少垃圾運(yùn)輸成本。首先根據(jù)城市垃圾分布點(diǎn)的坐標(biāo)，算出它們兩兩之間的距離，建立最小生成樹的變形成鏈的模型，確定車輛運(yùn)輸?shù)娜肿顑?yōu)路線，進(jìn)行車輛分配及路線分配。確定路線時(shí)，運(yùn)用了優(yōu)化模型進(jìn)行優(yōu)化，使得工作時(shí)間能夠平均分配給每輛車。綜合上述，進(jìn)行模型優(yōu)缺點(diǎn)分析如下：優(yōu)點(diǎn)：（1）模型最后進(jìn)行了優(yōu)

35、化，使得總體時(shí)間有所下降，在一定程度上減少了垃圾管理的成本。（2）開始使用最小生成樹模型，求得全局最優(yōu)路線，之后的改進(jìn)也是基于加邊后權(quán)重取最小的方法求得鏈，即得到了每個(gè)垃圾點(diǎn)在一條路線上的最短路線，在整體上使得車輛行駛的路程最短，對(duì)應(yīng)的時(shí)間也最短。（3）理論研究與實(shí)際分析集合緊密。通過(guò)使用真實(shí)的數(shù)據(jù)，并用它進(jìn)行模型求解。從而得到我們所需要的數(shù)據(jù)，可以把所得的結(jié)果在一定條件下運(yùn)用到現(xiàn)實(shí)生活中，具有實(shí)際價(jià)值。缺點(diǎn)：（1）求解的模型的路線是整體最優(yōu)，而它每一個(gè)具體劃分的塊不一定是局部最優(yōu)，因此可采用分區(qū)后，對(duì)每一塊中再計(jì)算它的最優(yōu)，最終使得模型更加的優(yōu)化。（2）所研究的具體數(shù)據(jù)不夠全面，只是對(duì)某個(gè)城

36、市的垃圾的管理進(jìn)行分析，（3）模型雖具有普遍性，還有一些特殊情況沒有考慮。7 模型推廣本文對(duì)問(wèn)題建立的是基于最小生成樹模型的修正模型，它的原理主要是求出全局最優(yōu)。在現(xiàn)實(shí)生活中，有許多管理、組織與計(jì)劃的優(yōu)化問(wèn)題，如企業(yè)管理中，如何制定管理計(jì)劃或設(shè)備購(gòu)置計(jì)劃，使收益最大或最??；在生產(chǎn)管理中，如何使各工序銜接好，才能使生產(chǎn)任務(wù)完成的既快又好；在交通管理中，如何利用現(xiàn)有的交通網(wǎng)絡(luò)，是調(diào)用的物資數(shù)量多且費(fèi)用最小等。這類問(wèn)題都可以用圖論知識(shí)得以解決問(wèn)題的數(shù)學(xué)模型。近年來(lái)的到迅速發(fā)展，且廣泛地應(yīng)用在各個(gè)領(lǐng)域。參考文獻(xiàn)1 趙靜，但琦. 數(shù)學(xué)建模與數(shù)學(xué)實(shí)驗(yàn)m 北京：高等教育出版社，20082 戴明強(qiáng)，李衛(wèi)軍，楊

37、鵬飛. 數(shù)學(xué)模型及其應(yīng)用m 北京：科學(xué)出版社，20073 鐘沅羱. 城市生活垃圾中轉(zhuǎn)站評(píng)價(jià)及車輛收運(yùn)路線優(yōu)化研究南京航空航天大學(xué)20104 姚建華. 用最小生成樹解決tsp問(wèn)題湖北師范學(xué)院學(xué)報(bào)(自然科學(xué)版)2004年04期5 楊秀文，陳振杰，李愛玲，田艷芳. 利用矩陣翻轉(zhuǎn)法求最佳h圈 20086 唐策善，梁維發(fā). 并行圖論算法.合肥：中國(guó)科學(xué)技術(shù)大學(xué)出版社，19917 盧開澄，盧華明. 圖論及其應(yīng)用.北京：清華大學(xué)出版社，19968 席少霖，趙鳳志. 最優(yōu)化計(jì)算方法.上海：上?？茖W(xué)技術(shù)出版社，1983附錄部分程序源代碼1. 最小生成樹matlab代碼x=-8260 -6395 -6328 64

38、00 8034 9691 7415 4010 10163 5770 10510 5287 9842 7486 7418 7988 10736 8104 7528 10414 4838 7540 6491 9998 10235 6050 6802 6192 9687 7521 4150 1895 -4978 -4953 -4990 2847 -4473 -1285 -5243 1237 -2832 1560 -1303 3439 -6146 -4154 -7239 -5951 -4980 -2430;y= 1545 1227 1235 3764 7961 7240 8071 3924 3112

39、1143 5795 3096 3154 8588 8090 3081 3397 -1592 394 -2486 -5557 465 4299 7600 494 3825 -3844 1391 -2781 468 5260 -5548 -966 -1662 -929 -6848 -7832 -4806 -1087 -6936 -5892 -2763 -4798 -6932 -6491 -1775 -10732 -5353 -11965 -4802;%第一點(diǎn)是中轉(zhuǎn)站，以后依次是收運(yùn)點(diǎn)的編號(hào)for i=1:50for j=1:50 a(i,j)=abs(x(i)-x(j)+abs(y(i)-y(j)

40、;%建立鄰接矩陣endendac=krusk(a,1)sums=0;for i=1:50plot(x(i),y(i),'.')text(x(i)+300,y(i),'',num2str(i);for j=1:50if c(i,j)=0 %plot(x,y,'.')plot(x(i) x(j),y(i) y(j)hold onsums=sums+c(i,j); text(x(i)+x(j)/2),(y(i)+y(j)/2),'',num2str(c(i,j),'color','red');endend

41、endhold off%f(c,50);%52為根節(jié)點(diǎn)fprintf('n總共長(zhǎng)度為：%d',sums);fprintf('n');2. 最小生成樹轉(zhuǎn)換成鏈x=-8260 -6395 -6328 6400 8034 9691 7415 4010 10163 5770 10510 5287 9842 7486 7418 7988 10736 8104 7528 10414 4838 7540 6491 9998 10235 6050 6802 6192 9687 7521 4150 1895 -4978 -4953 -4990 2847 -4473 -1285 -

42、5243 1237 -2832 1560 -1303 3439 -6146 -4154 -7239 -5951 -4980 -2430;y= 1545 1227 1235 3764 7961 7240 8071 3924 3112 1143 5795 3096 3154 8588 8090 3081 3397 -1592 394 -2486 -5557 465 4299 7600 494 3825 -3844 1391 -2781 468 5260 -5548 -966 -1662 -929 -6848 -7832 -4806 -1087 -6936 -5892 -2763 -4798 -6932 -6491