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