垃圾運(yùn)輸問(wèn)題建模論文9

1、2012高教社杯全國(guó)大學(xué)生數(shù)學(xué)建模承諾書(shū)我們仔細(xì)閱讀了中國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽的競(jìng)賽規(guī)則 我們完全明白，在競(jìng)賽開(kāi)始后參賽隊(duì)員不能以任何方式（包括電話、電子郵件、網(wǎng) 上咨詢等）與隊(duì)外的任何人（包括指導(dǎo)教師）研究、討論與賽題有關(guān)的問(wèn)題。我們知道，抄襲別人的成果是違反競(jìng)賽規(guī)則的 ，如果引用別人的成果或其他公開(kāi)的 資料（包括網(wǎng)上查到的資料），必須按照規(guī)定的參考文獻(xiàn)的表述方式在正文引用處和參 考文獻(xiàn)中明確列出。我們鄭重承諾，嚴(yán)格遵守競(jìng)賽規(guī)則，以保證競(jìng)賽的公正、公平性。如有違反競(jìng)賽規(guī) 則的行為，我們將受到嚴(yán)肅處理。我們授權(quán)全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽組委會(huì)，可將我們的論文以任何形式進(jìn)行公開(kāi)展 示（包括進(jìn)行網(wǎng)上公示

2、，在書(shū)籍、期刊和其他媒體進(jìn)行正式或非正式發(fā)表等）。我們參賽選擇的題號(hào)是（從 A/B/C/D中選擇一項(xiàng)填寫(xiě)）： 我們的參賽報(bào)名號(hào)為（如果賽區(qū)設(shè)置報(bào)名號(hào)的話） ：所屬學(xué)校（請(qǐng)?zhí)顚?xiě)完整的全名）：江西師范大學(xué)參賽隊(duì)員（打印并簽名）：1.王琨2. 劉莉3. 黃安枝指導(dǎo)教師或指導(dǎo)教師組負(fù)責(zé)人（打印并簽名）：賽區(qū)評(píng)閱編號(hào)（由賽區(qū)組委會(huì)評(píng)閱前進(jìn)行編號(hào)）：賽區(qū)評(píng)閱記錄（可供賽區(qū)評(píng)閱時(shí)使用）：評(píng)閱人評(píng)分OOOOOOOOO備注全國(guó)統(tǒng)一編號(hào)（由賽區(qū)組委會(huì)送交全國(guó)前編號(hào)）：全國(guó)評(píng)閱編號(hào)（由全國(guó)組委會(huì)評(píng)閱前進(jìn)行編號(hào)）：城市垃圾運(yùn)輸問(wèn)題摘要城市垃圾運(yùn)輸問(wèn)題是一個(gè)尋求最優(yōu)路徑的優(yōu)化問(wèn)題。在解決第一問(wèn)運(yùn)輸車的調(diào)度問(wèn)題時(shí)，本文首

3、先確立了一種構(gòu)思，即縮短運(yùn)輸車的總路程。在此基礎(chǔ)上加大空載路程， 縮短載重路程，并做到運(yùn)輸車的數(shù)量盡可能的少。在第一問(wèn)中，根據(jù)以上幾點(diǎn)要求，我們進(jìn)一步將其深入討論得出必須使運(yùn)輸車空載 至最遠(yuǎn)點(diǎn)，運(yùn)用下山法的原理逐步找出下一個(gè)最合適的點(diǎn)，此時(shí)只需滿足橫縱坐標(biāo)都逐 漸減小，而所取點(diǎn)垃圾總量不大于 6噸，最終通過(guò)運(yùn)算我們得出了 10條線路。但是其 中有幾條線路用時(shí)較短，我們對(duì)其進(jìn)行了人工優(yōu)化，將用時(shí)較短的路線進(jìn)行合并，最終 得出只需6輛運(yùn)輸車。在第二問(wèn)鏟車調(diào)度的問(wèn)題中，本文延續(xù)并使用了第一問(wèn)的結(jié)果和上述思想。在保持 運(yùn)輸車線路不變的情況下，本文估算了一下鏟車由第一個(gè)工作點(diǎn)開(kāi)始到最后一個(gè)工作點(diǎn) 結(jié)束的

4、同時(shí)再除以4小時(shí)，得出最少要三輛鏟車。將10條運(yùn)輸線路概括為3個(gè)部分， 原則是使這3個(gè)部分的每個(gè)部分內(nèi)鏟車跑的總路程最短，通過(guò)人工的運(yùn)算和時(shí)間的對(duì)照， 我們得出了最終結(jié)果。在第三問(wèn)中，三種型號(hào)車的加入增加了解題的靈活性，此時(shí)我們的構(gòu)思依然是縮短 運(yùn)輸車的總路程，加大空載路程，而利用 8噸車去盡可能的解決遠(yuǎn)處的垃圾顯然可以在 不增加總路程的情況下更加縮短空載路程。我們的結(jié)果如下：第一問(wèn)，求得需要運(yùn)輸車6輛，所需總費(fèi)用為2339.05元，調(diào)度方案見(jiàn)正文表5, 最優(yōu)路徑見(jiàn)正文圖4。第二問(wèn)，求得需要鏟車3輛，所需總費(fèi)用為142.8元，調(diào)度方案見(jiàn)正文表4。第三問(wèn)，求得需要鏟車4輛和運(yùn)輸車5輛，所需總費(fèi)用

5、為2508.63元，運(yùn)輸車和鏟 車的調(diào)度方案見(jiàn)表&表7,運(yùn)輸車的最優(yōu)路徑見(jiàn)圖 & 關(guān)鍵詞：最優(yōu)路徑、哈密頓圈、下山法、模擬退火法一、問(wèn)題的重述為了美化城市環(huán)境，環(huán)衛(wèi)部門(mén)每天夜里都要對(duì)分布在城區(qū)各街道的定點(diǎn)垃圾及時(shí)進(jìn) 行處理。假設(shè)某城區(qū)有37個(gè)垃圾集中點(diǎn)，環(huán)衛(wèi)車輛每天都要從垃圾處理廠（第 38號(hào)節(jié) 點(diǎn)）出發(fā)將垃圾運(yùn)回。現(xiàn)有一種載重量 6噸的運(yùn)輸車，每個(gè)垃圾點(diǎn)需要用8分鐘的時(shí)間 裝車，運(yùn)輸車平均速度為 40公里/小時(shí)（夜里運(yùn)輸，不考慮塞車現(xiàn)象）；每輛車每日 平均工作4小時(shí)；運(yùn)輸車重載運(yùn)費(fèi)為2元/噸公里；運(yùn)輸車和裝垃圾用的鏟車空載費(fèi)用 均為0.5元/公里；并且假定街道方向均平行于坐標(biāo)軸。試給出滿意的

6、運(yùn)輸調(diào)度方案以 及試給出滿意的運(yùn)輸調(diào)度方案以及計(jì)算程序。1. 運(yùn)輸車應(yīng)如何調(diào)度（需要投入多少臺(tái)運(yùn)輸車，每臺(tái)車的調(diào)度方案、運(yùn)營(yíng)費(fèi)用）；2. 鏟車應(yīng)如何調(diào)度（需要多少臺(tái)鏟車，每臺(tái)鏟車的行走路線以及運(yùn)營(yíng)費(fèi)用）；3. 如果改用載重為4噸、6噸、8噸的三種運(yùn)輸車，試給出運(yùn)輸車和鏟車的調(diào)度方案。二、問(wèn)題的分析2.1 .問(wèn)題一的分析問(wèn)題一是圖論中的一個(gè)遍歷問(wèn)題。由于運(yùn)輸車的載重與時(shí)間的約束，問(wèn)題一不再是 最小樹(shù)能解決的問(wèn)題，而是森林，即包含了多個(gè)樹(shù)的圖。每一個(gè)樹(shù)用一輛車去把其上面 的垃圾運(yùn)輸回來(lái)，只要時(shí)間足夠，同一輛車可能運(yùn)輸不止一棵樹(shù)的垃圾。問(wèn)題就變成了 在一個(gè)森林中，找到這樣一些樹(shù)，使其能用盡可能少的車

7、遍歷完所有頂點(diǎn)，且這些樹(shù)構(gòu) 成哈密頓圈。將垃圾集中點(diǎn)抽象成坐標(biāo)平面上的點(diǎn)，該點(diǎn)具有兩個(gè)屬性，即位置屬性和重量屬性： 城市抽象成一個(gè)30 20的一個(gè)坐標(biāo)方格網(wǎng)絡(luò)。該模型符合以上模型假設(shè)。垃圾運(yùn)輸問(wèn)題 最終可以歸結(jié)為最優(yōu)路徑搜索問(wèn)題，但注意到此圖為森林而不是樹(shù)，更具具體問(wèn)題設(shè)計(jì) 出隨即下山法，用計(jì)算模擬搜索，可以搜尋到令人滿意的可行解。通過(guò)分析“單獨(dú)運(yùn)輸” “先遠(yuǎn)點(diǎn)再近點(diǎn)” “先近點(diǎn)再遠(yuǎn)點(diǎn)”三種方面和垃圾是否一次清除的情況可得搜索的基 本原則。2.2.問(wèn)題二的分析當(dāng)加入鏟車后，因?yàn)殓P車的空載費(fèi)用為0.5元/公里，鏟車裝入垃圾后為2元/公里 小時(shí)，我們應(yīng)該讓鏟車將就運(yùn)輸車。若改變一條線，則會(huì)造成幾公

8、里的誤差，甚至十幾公 里的誤差，這一項(xiàng)的數(shù)目就很大。若是鏟車跟隨運(yùn)輸車 ，則即使路線誤差大一點(diǎn)，但所需 費(fèi)用也不會(huì)變得很大，故我們以第一個(gè)方案的路線為準(zhǔn)。這時(shí)我們只要保證前一條線路 的末節(jié)點(diǎn)，與后一條線路的首節(jié)點(diǎn)的路程差分別相加之和最小即可。根據(jù)這一思路，我 們利用模擬退火方法，通過(guò)排列，遍歷每種方案，就求出最優(yōu)解。再考慮最短路徑的情 況及考慮和各車在時(shí)間地銜接，盡量要在規(guī)定的時(shí)間內(nèi)作完，再進(jìn)行相應(yīng)的調(diào)整得出最 優(yōu)解。2.3問(wèn)題三的分析對(duì)于問(wèn)題3中4噸、6噸和8噸3種型號(hào)的運(yùn)輸車，本文先通過(guò)計(jì)算機(jī)分別運(yùn)算出 只使用一種車時(shí)的最優(yōu)解，然后將三者的運(yùn)算結(jié)果人工優(yōu)化，從而得出最終解，得出調(diào) 度方案。

9、三、模型假設(shè)1. 運(yùn)輸車勻速行駛且不計(jì)一切拐彎損耗時(shí)間；2. 車輛在任意兩站點(diǎn)中途不停車；3. 只要平行于坐標(biāo)軸即有街道存在；。4. 無(wú)論垃圾量多少，都能在十分鐘內(nèi)裝上運(yùn)輸車；5. 每個(gè)垃圾站點(diǎn)的垃圾不允許分兩次運(yùn)輸，而且也只需要一輛鏟車。6. 假設(shè)運(yùn)輸車、鏟車從A垃圾站到B垃圾站總走最短路線；7. 任意兩垃圾站間的最短路線為以兩垃圾站連線為斜邊的直角三角形的兩直角邊 之和；8. 如果車可以跑第二趟，中間無(wú)休息時(shí)間；9. 假設(shè)鏟車、運(yùn)輸車載工作途中不發(fā)生意外也不遇到意外；10. 所有運(yùn)輸車和鏟車均從第38號(hào)點(diǎn)出發(fā)，且最后均回到38號(hào)點(diǎn)；四、符號(hào)說(shuō)明1、子點(diǎn)：本點(diǎn)的下一點(diǎn)；2、Spend:運(yùn)費(fèi)；

10、3、Time：時(shí)間消耗；4、|A| : A點(diǎn)橫縱坐標(biāo)之和，；5、垃圾集中點(diǎn)在后面用頂點(diǎn)表示6、vi:第i個(gè)頂點(diǎn)7、vi.X :第i個(gè)頂點(diǎn)的X坐標(biāo)；vi.丫 表示第i個(gè)頂點(diǎn)的丫坐標(biāo)；& vi.laji :第i個(gè)頂點(diǎn)上有的垃圾重量，單位是噸；9、Lij:頂點(diǎn)i到頂點(diǎn)j的距離；10、sumi:頂點(diǎn)i的橫縱坐標(biāo)之和；11、訪問(wèn)一個(gè)頂點(diǎn)表示把它的垃圾裝上車；12、用到的相關(guān)定義設(shè)G = (V, E) 是連通無(wú)向圖，(1) 經(jīng)過(guò)G的每一個(gè)頂點(diǎn)正好一次的路，稱為G的一條哈密頓路或H路;(2) 經(jīng)過(guò)G的每一個(gè)頂點(diǎn)正好一次的圈，稱為G的一條哈密頓圈或H圈; 含H圈的圖稱為哈密頓圖或H圖.| A| A點(diǎn)橫縱坐標(biāo)之

11、和| B| B點(diǎn)橫縱坐標(biāo)之和| A-B|表示A,B兩點(diǎn)之間的距離Ta 表示A點(diǎn)所在地的垃圾量cost:運(yùn)費(fèi)；time :時(shí)間消耗；裝的足夠多運(yùn)輸車當(dāng)前的載重離限載不大于 0.55噸(垃圾點(diǎn)的最小垃圾量)序數(shù)號(hào)所在點(diǎn)的編號(hào)四、模型分析及建立模型4.1問(wèn)題分析這是圖論中的一個(gè)遍歷問(wèn)題。由于運(yùn)輸車的載重與時(shí)間的約束，它不再是最小樹(shù)能 解決的問(wèn)題，而是森林，即包含了多個(gè)樹(shù)的圖。每一個(gè)樹(shù)用一輛車去把其上面的垃圾運(yùn) 輸回來(lái)，只要時(shí)間足夠，同一輛車可能運(yùn)輸不止一棵樹(shù)的垃圾。問(wèn)題就變成了，在一個(gè) 森林中，找到這樣一些樹(shù)，使其能用盡可能少的車遍歷完所有頂點(diǎn)，且這些樹(shù)構(gòu)成哈密 頓圈。將垃圾集中點(diǎn)抽象成坐標(biāo)平面上的

12、點(diǎn)，該點(diǎn)具有兩個(gè)屬性，即位置屬性和重量屬性： 城市抽象成一個(gè)30 20的一個(gè)坐標(biāo)方格網(wǎng)絡(luò)。該模型符合以上模型假設(shè)。垃圾運(yùn)輸問(wèn)題 最終可以歸結(jié)為最優(yōu)路徑搜索問(wèn)題，但注意到此圖為森林而不是樹(shù)，更具具體問(wèn)題設(shè)計(jì) 出隨即下山法，用計(jì)算模擬搜索，可以搜尋到令人滿意的可行解4.11先注意分析兩點(diǎn)的情況，設(shè)兩點(diǎn)分別為A(x1,y1),b(x2,y2)主要有以下兩種情況：1. A,B明顯有先后次序-遞減狀態(tài)(如圖1)O Ao r& ./D 4 -JZ2 -L-.丄L1.J-uj ir ir Tb t1 151rirj101圖1不妨設(shè)x1x2, y1y2,不難看出A在B的后方,即A比B遠(yuǎn)。對(duì)于前方參考點(diǎn) 0,要

13、 將A,B對(duì)應(yīng)垃圾點(diǎn)的垃圾全部取回再返回 0,一共有三種方式：1) 0A0, 0B0單獨(dú)運(yùn)輸。這種情況下，總的路程消費(fèi)等于空載運(yùn)行費(fèi)用 (0.4元/公里)與裝載 時(shí)運(yùn)行費(fèi)用(1.8元/公里噸)的總和。所需的總時(shí)間等于車輛所走過(guò)的總路程與速度 (40 公里/小時(shí))的比值再加上在 A,B兩點(diǎn)停留的時(shí)間(每個(gè)垃圾點(diǎn)上停留了 10分鐘，1/6 小時(shí))，于是有：S=0.4 | A | 1.8 | A| Ta 0.4 |B| 1.8 | B | TbT =(2 | A| 2 | B I) 40 十 6 22) OABO先遠(yuǎn)點(diǎn)再近點(diǎn)，即先空載至最遠(yuǎn)處，裝完A點(diǎn)垃圾后再返回至B,再回0點(diǎn)，有：S =0.4 |

14、 A| 1.8 | A - B | Ta 1.8 | B | (Ta Tb)= 0.4 | A| 1.8 | A| Ta 1.8 | B | TbT =2 | A40 V 6 23) OBAO先近點(diǎn)在遠(yuǎn)點(diǎn)，即先裝B點(diǎn)垃圾，然后載著B(niǎo)點(diǎn)的垃圾奔至A點(diǎn)，再回O點(diǎn),有：S =0.4 | B | 1.8 | A - B | Tb 1.8 | A| (Ta Tb)= 0.4 | B| 1.8 | A| Ta 1.8 | B | Tb 1.8 | A - B | 2 TbT =2 | A p40 V- 6 2比較以上三種情況，遠(yuǎn)近點(diǎn)的遍歷順序，可以看出，“先遠(yuǎn)后近”絕對(duì)比“先近后遠(yuǎn)”在花費(fèi)錢(qián)的數(shù)量上要少的

15、多，省出1.8 | A-B| 2 Tb這部分的錢(qián)主要是車載著 B點(diǎn)的垃圾奔到A點(diǎn)再返回B點(diǎn)。而又注意到兩者的時(shí)間花費(fèi)是相等的。所以在其余同等的情況下選擇“先遠(yuǎn)后近”?？紤]到時(shí)間上單獨(dú)運(yùn)輸比其余的兩種運(yùn)輸要大的多，多一 一倍，而且花費(fèi)的錢(qián)仍不比“先遠(yuǎn)后近”省，還多了0.4 | B|，所以一般情況下，不采用單獨(dú)運(yùn)輸。4.12A還是一共有兩種情況:1）OAO, OBO單獨(dú)運(yùn)輸。這種情況下，總的路程消費(fèi)等于空載運(yùn)行費(fèi)用（0.4元/公里）與裝載 時(shí)運(yùn)行費(fèi)用（1.8元/噸公里）的總和。所需的總時(shí)間等于車輛所走過(guò)的總路程與速度 （35 公里/小時(shí)）的比值再加上再 A,B兩點(diǎn)停留的時(shí)間（每個(gè)垃圾點(diǎn)上停留了 1

16、0分鐘，1/6 小時(shí)），于是有：S=0.4 |A| 1.8 | A| vA.laji 0.4 | B | vB.lajiT = (2 | A| 2 | B |)“ 35 十 6 22）OABC或 OBAO先空載到A或B,即先空載到其中的一個(gè)點(diǎn)，裝完 A（ B）點(diǎn)的垃圾再返回B（ A）， 再回到O點(diǎn)，有：S=0.4 |A| 1.8 vA.laji LAB 1.8 (vA.laji vB.laji) | B | - 1 T =2 | A | LA B通過(guò)上面兩種方式的比較，第1種遍歷的費(fèi)用少，但時(shí)間稍多。綜合分析，由于時(shí) 間可調(diào)，我們選擇費(fèi)用少的，時(shí)間稍多的遍歷，即第 1種方式。兩點(diǎn)選擇趨勢(shì)的討論

17、。（如圖3）AZU佔(zhàn)-71B 1 1 1 Jl1 II1 I ii I I1 丨 1 1 111 G 1 4 1 1 Hill1 1 11 1 1 1 fill111 II il |1 II 111w1 1 1 12111111 1 1 1 121 1 1 1 D圖3由圖中看到B,C兩點(diǎn)沒(méi)有明顯的先后順序，屬于并鄰點(diǎn)。因?yàn)楫?dāng)運(yùn)輸車載重行駛時(shí) 費(fèi)用會(huì)成倍的增長(zhǎng)，比其空載時(shí)所花費(fèi)用要大的多，所以排除ABC或A C B這樣的一次經(jīng)過(guò)3點(diǎn)的往返路線，僅選擇 B,C中的某一點(diǎn)與A完成此次運(yùn)輸，將另一點(diǎn) 留到下次。那么A點(diǎn)選擇B還是C呢？不妨假設(shè)|B| C,即B點(diǎn)離原點(diǎn)的距離比C點(diǎn)的更遠(yuǎn)，因?yàn)锳在B,C之

18、后，所以也 就是B點(diǎn)離A點(diǎn)更近。這樣，此次的運(yùn)輸我們更趨向于選擇A B,因?yàn)榫瓦@三點(diǎn)而論，A無(wú)論是選B還是C,三點(diǎn)的垃圾總要運(yùn)完，所以花費(fèi)的錢(qián)是一樣的。但選擇 A B下 次運(yùn)輸車運(yùn)C點(diǎn)垃圾時(shí)就無(wú)需跑的更遠(yuǎn)。4.2關(guān)于垃圾點(diǎn)的垃圾是否一次清除的討論由假設(shè)4知，每天的垃圾必須清除完畢，全部運(yùn)往 37點(diǎn)。這里說(shuō)的一次清除問(wèn)題 不是指一天，而是指當(dāng)一輛運(yùn)輸車已經(jīng)裝載了足夠多的垃圾，不能完全清理下一個(gè)垃圾 點(diǎn)的時(shí)候，車在下一個(gè)站點(diǎn)停還是不停的問(wèn)題。我們認(rèn)為前者更好，就是車在裝的足夠多的情況下應(yīng)該直接返回原點(diǎn)（37點(diǎn)）。這是因?yàn)閷?duì)于下一垃圾點(diǎn)（假設(shè)為A點(diǎn)）內(nèi)的垃圾而言，無(wú)論是一次裝完還是分兩次裝完， 將它

19、們運(yùn)回所花費(fèi)用是恒定的。整體而言，兩者花費(fèi)的錢(qián)是相等的，但分兩次裝要多 花10分鐘的裝車時(shí)間，所以選擇前者。綜上所述，得出搜索的基本原則：1. 在兩點(diǎn)遞減的情況下，不采用單獨(dú)運(yùn)輸，選擇“先遠(yuǎn)后近”，2. 不要求時(shí)間的情況下對(duì)于并鄰兩點(diǎn)，采用單獨(dú)運(yùn)輸?shù)姆绞阶罟?jié)約錢(qián)；3. 車在裝的足夠多的情況下應(yīng)該直接返回原點(diǎn)（37點(diǎn)）；4. 每條線路的搜索都由未搜點(diǎn)中的最大值開(kāi)始。五、模型的求解5.1 問(wèn)題1的求解在不考慮鏟車的情況下，運(yùn)輸車的最優(yōu)路線如下：（見(jiàn)圖4）綜合兩點(diǎn)的分布情況與遍歷路線分析，先空載至最遠(yuǎn)點(diǎn)，即哈密頓距離（橫縱坐標(biāo) 和）最遠(yuǎn)點(diǎn)，如果它沒(méi)有被訪問(wèn)，貝U訪問(wèn)它。然后試著返回，途中找它的子點(diǎn)，

20、即沒(méi)有 被訪問(wèn)過(guò)的哈密頓距離且車能裝下其垃圾的頂點(diǎn)，找到后，訪問(wèn)子點(diǎn)：再以子點(diǎn)為本點(diǎn),以同樣的方式找子點(diǎn)，直到?jīng)]有子點(diǎn)可找，或車不能裝下找到的子點(diǎn)為止。這樣就將圖 分成了多個(gè)哈密頓圈。對(duì)上圖中的結(jié)果，可以在不改變最佳哈密頓圈且考慮到車載量的約束的基礎(chǔ)上改進(jìn) 哈密頓圈，可得下表路線：途經(jīng)頂點(diǎn)垃圾量（噸）耗時(shí)A: 28-26-21-25-195.73小時(shí)02分B: 30-29-275.32小時(shí)48分C: 36-23-33-325.52小時(shí)46分D: 34-17-16-252小時(shí)07分E: 24-18-35-205.22小時(shí)22分F: 14-31-5-65.851小時(shí)46分G: 15-13-7-45

21、.62小時(shí)04分H: 12-8-35.551小時(shí)30分I : 11-9-141小時(shí)30分J: 22-103.31小時(shí)23分表1運(yùn)輸耗時(shí)通過(guò)表1與圖4,得一下兩種車輛分配與路線運(yùn)輸車路線時(shí)間總時(shí)間1A3小時(shí)02分3小時(shí)02分2B2小時(shí)48分2小時(shí)48分3C2小時(shí)46分2小時(shí)46分4D2小時(shí)07分4小時(shí)11分G2小時(shí)04分5E2小時(shí)22分4小時(shí)06分r f1小時(shí)46分6H1小時(shí)20分4小時(shí)13分I1小時(shí)30分J1小時(shí)23分表2運(yùn)輸線路時(shí)間安排1運(yùn)輸車路線時(shí)間總時(shí)間1A3小時(shí)02分3小時(shí)02分2B2小時(shí)48分2小時(shí)48分3C2小時(shí)46分4小時(shí)06分H1小時(shí)20分4J1小時(shí)23分3小時(shí)30分D2小時(shí)0

22、7分5E2小時(shí)22分3小時(shí)52分I1小時(shí)30分6G2小時(shí)04分3小時(shí)50分F1小時(shí)46分表3運(yùn)輸車的調(diào)度方案經(jīng)比較分析表2中的路線時(shí)間安排更為合理。我們算出所需總費(fèi)用為2339.05元。5.2 問(wèn)題2的求解當(dāng)加入鏟車后,因?yàn)殓P車的空載費(fèi)用為0.4元/小時(shí)，鏟車裝入垃圾后為1.8元/公 里小時(shí)，我們應(yīng)該讓鏟車將就運(yùn)輸車。若改變一條線，則會(huì)造成幾公里的誤差，甚至十幾 公里的誤差，這一項(xiàng)的數(shù)目就很大。若是鏟車跟隨運(yùn)輸車 ，則即使路線誤差大一點(diǎn)，但所 需費(fèi)用也不會(huì)變得很大，故我們以第一個(gè)方案的路線為準(zhǔn)。這時(shí)我們只要保證前一條線 路的末節(jié)點(diǎn)，與后一條線路的首節(jié)點(diǎn)的路程差分別相加之和最小即可。根據(jù)這一思路

23、， 我們利用模擬退火方法，設(shè)一個(gè)結(jié)構(gòu)數(shù)組變量，他有11個(gè)元素（代表11條元素）。其中 每個(gè)元素里面有兩個(gè)結(jié)構(gòu)成員，這樣一個(gè)元素就代表一條線路，對(duì)這11個(gè)元素進(jìn)行排列， 這樣每一個(gè)排列就是一個(gè)線路方案，這樣便能通過(guò)排列 ，遍歷每種方案，就求出最優(yōu)解。 再考慮了最短路徑的情況下，由于要考慮和各車在時(shí)間地銜接，以及盡量要在規(guī)定的時(shí) 間內(nèi)作完，我們進(jìn)行相應(yīng)的調(diào)整。這部分由于考慮到計(jì)算復(fù)雜性，我們用手工調(diào)整，由于前面有最短路徑的保證，我們調(diào)整的結(jié)果接近最優(yōu)解。車次發(fā)車時(shí) 間線路線內(nèi)時(shí)間110點(diǎn)A11點(diǎn)06分-0點(diǎn)11.5分E0點(diǎn)22分-1點(diǎn)21.5分D1點(diǎn)50.5分-3點(diǎn)14分210點(diǎn)B11點(diǎn)09分-1

24、1點(diǎn)57分G0點(diǎn)06分-1點(diǎn)11.5分F2點(diǎn)11分-3點(diǎn)12分310點(diǎn)C11點(diǎn)03分-0點(diǎn)05.5分J0點(diǎn)14.5分-0點(diǎn)45分H1點(diǎn)26分-2點(diǎn)12.5分I2點(diǎn)33分3點(diǎn)25.5分表4:鏟車的調(diào)度運(yùn)輸車線路發(fā)車時(shí)間到達(dá)該線起點(diǎn)時(shí)間從該線返回時(shí)間1A10點(diǎn)11點(diǎn)06分0點(diǎn)11.5分2B10點(diǎn)11點(diǎn)09分11點(diǎn)57分3C10點(diǎn)11點(diǎn)03分0點(diǎn)05.5分H0點(diǎn)45.5分（等待40.5分）2點(diǎn)12.5分4J11點(diǎn)43分0點(diǎn)14.5分0點(diǎn)45分D1點(diǎn)59.5分3點(diǎn)14分5E11點(diǎn)31分0點(diǎn)22分1點(diǎn)21.5分I2點(diǎn)33分3點(diǎn)25.5分6G11點(diǎn)24分0點(diǎn)06分1點(diǎn)11.5分F2點(diǎn)11分3點(diǎn)12分表5運(yùn)

25、輸車的調(diào)度5.3問(wèn)題3的求解對(duì)于問(wèn)題3中4噸、6噸和8噸3種型號(hào)的運(yùn)輸車，本文先通過(guò)計(jì)算機(jī)分別運(yùn)算出 只使用一種車時(shí)的最優(yōu)解，然后將三者的運(yùn)算結(jié)果人工優(yōu)化，從而得出最終解。僅使用4噸、6噸和8噸的最優(yōu)路徑如下圖4、5、6所示:1）只使用4噸運(yùn)輸車時(shí):X30172629211G27313653312832311220151835 圖42）只使用6噸運(yùn)輸車時(shí)：3）只使用8噸運(yùn)輸車時(shí):圖6對(duì)圖7進(jìn)行人工優(yōu)化得出下表6中運(yùn)輸車的調(diào)度方案:車次噸數(shù)線路發(fā)車時(shí)間到該線起點(diǎn)時(shí)間從該線返回時(shí)間18A10點(diǎn)11點(diǎn)06分0點(diǎn)29分D1點(diǎn)12分2點(diǎn)03分3點(diǎn)21.5分28B10點(diǎn)11點(diǎn)09分0點(diǎn)38分C1點(diǎn)18分2

26、點(diǎn)31分3點(diǎn)52.5分36E1點(diǎn)38分2點(diǎn)21.5分3點(diǎn)36分F2點(diǎn)56分3點(diǎn)39.5分4點(diǎn)54分46G0點(diǎn)17分0點(diǎn)47分1點(diǎn)23.5分H3點(diǎn)42分4點(diǎn)03分:4點(diǎn)42.5分54I0點(diǎn)58分1點(diǎn)19分1點(diǎn)48分表6運(yùn)輸車的調(diào)度依據(jù)題2中建立的模型和人工的優(yōu)化可得到鏟車的調(diào)度方案如下表:車 次出發(fā)時(shí)間線路線內(nèi)時(shí)間回到0點(diǎn)的時(shí) 間110點(diǎn)A11點(diǎn)06分-0點(diǎn)29分1點(diǎn)50分F0點(diǎn)36.5分-1點(diǎn)11.5分I1點(diǎn)19分-1點(diǎn)38分210點(diǎn)B11點(diǎn)09分-0點(diǎn)38分1點(diǎn)37分G0點(diǎn)47分-1點(diǎn)23.5分31點(diǎn)18分C2點(diǎn)31分-3點(diǎn)2.5分4點(diǎn)50分H4點(diǎn)03分-4點(diǎn)42.5分41點(diǎn)12分D2點(diǎn)03

27、分-3點(diǎn)21.5分5點(diǎn)03分E3點(diǎn)39.5分-4點(diǎn)54分表7鏟車的調(diào)度六、模型的優(yōu)缺點(diǎn)分析優(yōu)點(diǎn)：該模型算法簡(jiǎn)單容易實(shí)現(xiàn)，易懂；缺點(diǎn)：我們較多的采用人工方法，導(dǎo)致精度下降，有待改善。七、模型的推廣及應(yīng)用本文主要運(yùn)用下山法原理，在回收垃圾的過(guò)程中，讓重量由遠(yuǎn)到近逐漸增加，從而 達(dá)到節(jié)約成本的目的。如果我們從相反方向來(lái)看，似乎可以得到一個(gè)上山法的原理，我 們可以將其運(yùn)用到貨物的配送中，由近及遠(yuǎn)逐漸減輕重量，同時(shí)，由近及遠(yuǎn)尋找下一個(gè) 最優(yōu)點(diǎn)，從而達(dá)到實(shí)現(xiàn)最優(yōu)路徑，節(jié)省更多的成本。參考文獻(xiàn)：1戴朝壽，孫世良 數(shù)學(xué)建模簡(jiǎn)明教程 北京：高等教育出版社2. 葉其孝大學(xué)生數(shù)學(xué)建模競(jìng)賽輔導(dǎo)教材湖南：湖南教育出版社

28、3. 趙靜，但琦 數(shù)學(xué)建模與數(shù)學(xué)實(shí)驗(yàn)北京：高等教育出版社4. 劉育興，鐘劍 贛南師范學(xué)院學(xué)報(bào)2006年03期5譚浩強(qiáng)C+程序設(shè)計(jì) 清華大學(xué)出版社出版14附錄(C+運(yùn)算程序:#in clude #in clude #defi ne M 37 #defi ne N M-1 int sumM; int sortM; in t visitM; int fin al=0; int LMM; int m,vmi n,u; double weight; typedef struct no de double laji; int X; int Y;n ode;node vM;void aroun d(i nt

29、 w)int i,mi n=1000;for(i=1;i=N;i+)&if(Lwimin&vi.X=vw.X&vi.Y=vw.Yvisiti=0)mi n=Lwi;vmi n=i;if(u!=vmi n)weight=weight+vvmi n.laji;if(weight=6)visitvmi n=1;coutvmi n -;u=vmin;aroun d(v min);elsecout#;else coutvv#;void mai n()int maxin dex;v1.laji=1.50;v1.X=3;v1.Y=2;v2.laji=1.50;v2.X=1;v2.Y=5;v3.laji=0.

30、55;v3.X=5;v3.Y=4;v4.laji=1.20;v4.X=4;v4.Y=7; v5.laji=0.85;v 5.X=0;v5.Y=8;v6.laji=1.30;v6.X=3;v6.Y=11; v7.laji=1.20;v7.X=7;v7.Y=9; v8.laji=2.30;v8.X=9;v8.Y=6;v9.laji=1.40;v9.X=10;v9.Y=2; v10.laji=1.50;v10.X=14;v10.Y=0;v11.laji=1.10;v1.X=17;v1.Y=3;v12.laji=2.70;v2.X=14;v2.Y=6;v13.laji=1.80;v3.X=12;v3.

31、Y=9; v14.laji=1.80;v4.X=10;v4.Y=12;v15.laji=1.40;v5.X=19;v5.Y=9;v16.laji=1.50;v6.X=2;v6.Y=16;v17.laji=0.80;v7.X=6;v7.Y=18; v18.laji=1.50;v8.X=11;v8.Y=17; v19.laji=0.80;v9.X=15;v9.Y=12; v20.laji=0.60;v10.X=7;v10.Y=14; v21.laji=1.30;v1.X=17;v1.Y=16;v22.laji=1.80;v2.X=21;v2.Y=0;v23.laji=1.40;v3.X=27;v3

32、.Y=9; v24.laji=1.60;v4.X=15;v4.Y=19; v25.laji=1.60;v5.X=15;v5.Y=14; v26.laji=1.00;v6.X=20;v6.Y=17; v27.laji=2.00;v7.X=21;v7.Y=13; v28.laji=1.00;v8.X=24;v8.Y=20; v29.laji=2.10;v9.X=25;v9.Y=16;v30.laji=1.20;v10.X=28;v10.Y=18; v31.laji=1.90;v1.X=5;v1.Y=12; v32.laji=1.20;v2.X=22;v2.Y=5; v33.laji=1.60;v3.X=25;v3.Y=7; v34.laji=1.20;v4.X=9;v4.Y=20; v35.laji=1.50;v5.X=9;v 5.Y=15; v36.laji=1.30;v6.X=30;v6.Y=12;v37.laji=0.00;v7.X=0;v7.Y=0;int i,j,k;for(i=1;i=N;i+) f