數(shù)學建模—垃圾運輸問題的求解及源代碼(已修改)
2025-04-19 02:42 本頁面
【正文】 垃圾運輸問題*** 信息工程學院 計算機應用專業(yè) **********摘要：本文通過對垃圾站點之間分布位置的分析，構造出解決垃圾運輸問題的模型。首先，我們對所給數(shù)據(jù)繪制其xy散點圖，根據(jù)題設提出自己假設的條件。其次，結合已有的模型，對垃圾點之間的位置分布關系進行討論及證明，從而確定最基本的行車路線原則。然后，編寫c語言程序，利用計算機進行算法的模擬，從而搜索出各運輸車輛的數(shù)量以及最佳的分配方案，使得(1)在不考慮鏟車的情況下運輸費用最少、(2)考慮在有鏟車的模型中的最佳解、(3)對不同運輸量的運輸車進行合理分配調度，使得總費用最少。根據(jù)我們確定的解題思路，最終我們得到了一組可行解，如下：第一問，；第二問：求得需要3輛鏟車；第三問： 元。其中8噸的車4輛，6噸的車3輛，4噸的車3輛。具體的路線分配圖，車輛調度圖見正文部分。本文討論的解題方法模型簡單，得出的結果只是一個近似最優(yōu)解的可行解，所以還有很大的改進空間，比如我們可以采用更加智能的算法等。 關鍵詞：計算機算法模擬 優(yōu)化1． 問題的重述某城區(qū)有 37 個垃圾集中點，每天都要從垃圾處理廠（第 38號節(jié)點）出發(fā)將垃圾運回?，F(xiàn)有一種載重 6 噸的運輸車。每個垃圾點需要用 10 分鐘的時間裝車，運輸車平均速度為 40 公里／小時（夜里運輸，不考慮塞車現(xiàn)象）；每臺車每日平均工作 4 小時。運輸車重載運費 2 元 / 噸公里；運輸車和裝垃圾用的鏟車空載費用 元 / 公里；并且假定街道方向均平行于坐標軸。請你給出滿意的運輸調度方案以及計算程序。問題：（需要投入多少臺運輸車，每臺車的調度方案，運營費用）（需要多少臺鏟車，每臺鏟車的行走路線，運營費用） 4 噸、 6 噸、 8 噸三種運輸車，又如何調度？2． 模型的基本假設與符號說明（一）基本假設1．車輛在拐彎時的時間損耗忽略。2．車輛在任意兩站點中途不停車，保持穩(wěn)定的速率。3．只要平行于坐標軸即有街道存在。4．無論垃圾量多少，都能在十分鐘內裝上運輸車。5． 每個垃圾站點的垃圾只能由一輛運輸車運載。6. 假設運輸車、鏟車從A垃圾站到B垃圾站總走最短路線。7. 任意兩垃圾站間的最短路線為以兩垃圾站連線為斜邊的直角三角形的兩直角邊之和。8. 建設在運輸垃圾過程中沒有新垃圾入站。9. 假設鏟車、運輸車載工作途中不發(fā)生意外也不遇到意外；10. 各垃圾站每天的垃圾量相對穩(wěn)定。（二）符號說明|A| 表示A點到原點的距離，恒正|B| 表示B點到原點的距離，恒正|AB| 表示A,B兩點之間的距離,恒正Ta 表示A點所在地的垃圾量cost：運費；time：時間消耗；裝的足夠多 (垃圾點的最小垃圾量)序數(shù)號 所在點的編號3．模型的建立垃圾運輸問題最終可以歸結為最優(yōu)路徑搜索問題，但注意到此圖為森林而不是樹，不能直接套用Krusal，Prim等現(xiàn)成算法，于是根據(jù)具體問題設計出隨機下山法，用計算模擬搜索，可以搜尋到令人滿意的可行解。先注意到兩點的情況，設兩點分別為A(x1,y1),B(x2,y2)。主要有以下兩種情況：一． A,B明顯有先后次序。遞減狀態(tài)（如圖1） 不妨設x1x2, y1y2,不難看出A在B的后方,即A比B遠。對于前方參考點O,要將A,B對應垃圾點的垃圾全部取回再返回O,一共有三種方式：1． OAO, OBO單獨運輸。這種情況下，總的路程消費等于空載運行費用()與裝載時運行費用（）的總和。所需的總時間等于車輛所走過的總路程與速度（40公里/小時）的比值再加上在A,B兩點停留的時間(每個垃圾點上停留了10分鐘，1/6小時)，于是有：Cost = *|A| + *|A|*Ta + *|B| + *|B|*TbTime = (2*|A| + 2*|B|)/40 + 1/6*22. OABO 先遠點再近點，即先空載至最遠處，裝完A點垃圾后再返回至B,再回O點，有： Cost = *|A| + *|AB|*Ta +*|B|*(Ta+Tb) = *|A| + *|A|*Ta + *|B|*Tb Time = 2*|A|/40 + 1/6*23. OBAO 先近點在遠點，即先裝B點垃圾，然后載著B點的垃圾奔至A點，再回O點，有： Cost= *|B| + *|AB|*Tb + *|A|*(Ta+Tb) = *|B| + *|A|*Ta + *|B|*Tb + *|AB|*2*Tb Time = 2*|A|/40 + 1/6*2比較以上三種情況，遠近點的遍歷順序，可以看出，“先遠后近”絕對比“先近后遠”在花費錢的數(shù)量上要少的多，*|AB|*2*Tb這部分的錢主要是車載著B點的垃圾奔到A點再返回B點。而又注意到兩者的時間花費是相等的。所以在其余同等的情況下選擇“先遠后近”?？紤]到時間上單獨運輸比其余的兩種運輸要大的多，多一一倍，而且花費的錢仍不比“先遠后近”省，*|B|，所以一般情況下，不采用單獨運輸。二．A，B兩點沒有明顯先后順序。 并鄰狀態(tài)（如圖2）還是一共有三種情況： 1． OAO, OBO單獨運輸。這種情況下，跟A,B兩點有先后順序中的情況完全相同，即有：Cost = *|A| + *|A|*Ta + *|B| + *|B|
數(shù)學相關推薦
鄂ICP備17016276號-1