數(shù)學(xué)建?！\(yùn)輸問題的求解及源代碼-展示頁
2025-04-16 02:42本頁面
【正文】 返回原點(diǎn)（37點(diǎn)）；5． 每一次布局和每條線路的搜索不妨由剩下未搜點(diǎn)中的最大值開始。這是因?yàn)閷τ谙乱焕c(diǎn)(假設(shè)為A點(diǎn))內(nèi)的垃圾而言，無論是一次裝完還是分兩次裝完，將它們運(yùn)回所花費(fèi)用是恒定的，*Ta*|A|。例如，一輛運(yùn)輸車選擇了3026183520的路線（即先將空車開往30，清理裝載30點(diǎn)的垃圾，然后依次到26，18，35，20），(，稱這種情況為“裝的足夠多”)。四． 關(guān)于垃圾點(diǎn)的垃圾是否一次清除的討論（以6噸車?yán)┯杉僭O(shè)2知，每天的垃圾必須清除完畢，全部運(yùn)往37點(diǎn)。這樣，此次的運(yùn)輸我們更趨向于選擇AB,因?yàn)榫瓦@三點(diǎn)而論，A無論是選B還是C，三點(diǎn)的垃圾總要運(yùn)完，所以花費(fèi)的錢是一樣的。因?yàn)楫?dāng)運(yùn)輸車載重行駛時(shí)費(fèi)用會成倍的增長，比其空載時(shí)所花費(fèi)用要大的多，所以排除ABC或ACB這樣的一次經(jīng)過3點(diǎn)的往返路線，僅選擇B,C中的某一點(diǎn)與A完成此次運(yùn)輸，將另一點(diǎn)留到下次。三． 兩點(diǎn)選擇趨勢的討論。上式 0時(shí)， 選 OBAO。這種情況下，跟A,B兩點(diǎn)有先后順序中的情況完全相同，即有：Cost = *|A| + *|A|*Ta + *|B| + *|B|*Tbtime = (2*|A| + 2*|B|)/40 + 1/6*22． OABOCost = *|A| + *|AB|*Ta + *|B|*(Ta+Tb) 〈1〉Time = (|A| + |AB| + |B|)/40 + 1/6*2BAOCost = *|B| + *|AB|*Tb + *|A|*(Ta+Tb) 〈2〉Time = (|A| + |AB| + |B|)/40 +1/6*2相比之下，清晰可見并鄰狀態(tài)下的單獨(dú)運(yùn)輸所花的費(fèi)用最少，所以在不要求時(shí)間的情況下對于并鄰兩點(diǎn)，采用單獨(dú)運(yùn)輸?shù)姆绞阶罟?jié)約錢。二．A，B兩點(diǎn)沒有明顯先后順序。所以在其余同等的情況下選擇“先遠(yuǎn)后近”。所需的總時(shí)間等于車輛所走過的總路程與速度（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點(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)后近”絕對比“先近后遠(yuǎn)”在花費(fèi)錢的數(shù)量上要少的多，*|AB|*2*Tb這部分的錢主要是車載著B點(diǎn)的垃圾奔到A點(diǎn)再返回B點(diǎn)。對于前方參考點(diǎn)O,要將A,B對應(yīng)垃圾點(diǎn)的垃圾全部取回再返回O,一共有三種方式：1． OAO, OBO單獨(dú)運(yùn)輸。主要有以下兩種情況：一． A,B明顯有先后次序。（二）符號說明|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ù)號 所在點(diǎn)的編號3．模型的建立垃圾運(yùn)輸問題最終可以歸結(jié)為最優(yōu)路徑搜索問題，但注意到此圖為森林而不是樹，不能直接套用Krusal，Prim等現(xiàn)成算法，于是根據(jù)具體問題設(shè)計(jì)出隨機(jī)下山法，用計(jì)算模擬搜索，可以搜尋到令人滿意的可行解。8. 建設(shè)在運(yùn)輸垃圾過程中沒有新垃圾入站。6. 假設(shè)運(yùn)輸車、鏟車從A垃圾站到B垃圾站總走最短路線。4．無論垃圾量多少，都能在十分鐘內(nèi)裝上運(yùn)輸車。2．車輛在任意兩站點(diǎn)中途不停車，保持穩(wěn)定的速率。請你給出滿意的運(yùn)輸調(diào)度方案以及計(jì)算程序。每個(gè)垃圾點(diǎn)需要用 10 分鐘的時(shí)間裝車，運(yùn)輸車平均速度為 40 公里／小時(shí)（夜里運(yùn)輸，不考慮塞車現(xiàn)象）；每臺車每日平均工作 4 小時(shí)。 關(guān)鍵詞：計(jì)算機(jī)算法模擬 優(yōu)化1． 問題的重述某城區(qū)有 37 個(gè)垃圾集中點(diǎn)，每天都要從垃圾處理廠（第 38號節(jié)點(diǎn)）出發(fā)將垃圾運(yùn)回。具體的路線分配圖，車輛調(diào)度圖見正文部分。根據(jù)我們確定的解題思路，最終我們得到了一組可行解，如下：第一問，；第二問：求得需要3輛鏟車；第三問： 元。其次，結(jié)合已有的模型，對垃圾點(diǎn)之間的位置分布關(guān)系進(jìn)行討論及證明，從而確定最基本的行車路線原則。垃圾運(yùn)輸問題*** 信息工程學(xué)院 計(jì)算機(jī)應(yīng)用專業(yè) **********摘要：本文通過對垃圾站點(diǎn)之間分布位置的分析，構(gòu)造出解決垃圾運(yùn)輸問題的模型。首先，我們對所給數(shù)據(jù)繪制其xy散點(diǎn)圖，根據(jù)題設(shè)提出自己假設(shè)的條件。然后，編寫c語言程序，利用計(jì)算機(jī)進(jìn)行算法的模擬，從而搜索出各運(yùn)輸車輛的數(shù)量以及最佳的分配方案，使得(1)在不考慮鏟車的情況下運(yùn)輸費(fèi)用最少
數(shù)學(xué)相關(guān)推薦
鄂ICP備17016276號-1