數(shù)學(xué)建模城市垃圾運(yùn)輸問題知識(shí)分享

1、數(shù)學(xué)建模城市垃圾運(yùn)輸問題精品文檔貨運(yùn)公司運(yùn)輸問題數(shù)信學(xué)院 14 級(jí)信計(jì)班魏琮【摘要】本文是針對(duì)解決某港口對(duì)某地區(qū)8 個(gè)公司所需原材料A、B、C 的運(yùn)輸調(diào)度問題提出的方案。首先考慮在滿足各個(gè)公司的需求的情況下，所需要的運(yùn)輸?shù)淖钚∵\(yùn)輸次數(shù)，然后根據(jù)卸載順序的約束以及載重費(fèi)用盡量小的原則，提出了較為合理的優(yōu)化模型，求出較為優(yōu)化的調(diào)配方案。針對(duì)問題一，在兩個(gè)大的方面進(jìn)行分析與優(yōu)化。第一方面是對(duì)車次安排的優(yōu)化分析，得出 公司順時(shí)針?biāo)拓洠?公司逆時(shí)針?biāo)拓洖樽罴逊桨浮５诙矫娓鶕?jù)車載重相對(duì)最大化思想使方案分為兩個(gè)步驟，第一步先是使每個(gè)車次滿載并運(yùn)往同一個(gè)公司，第二步采用分批次運(yùn)輸?shù)姆桨?，即在第一批次運(yùn)輸中，

2、我們使 A 材料有優(yōu)先運(yùn)輸權(quán)；在第二批次運(yùn)輸中，我們使B 材料有優(yōu)先運(yùn)輸權(quán)；在第三批次中運(yùn)輸剩下所需的貨物。最后得出耗時(shí)最少、費(fèi)用最少的方案。耗時(shí)為 40.3333小時(shí)，費(fèi)用為4864.0元。針對(duì)問題二，加上兩個(gè)定理及其推論數(shù)學(xué)模型與問題一幾乎相同，只是空載路徑不同。采取與問題一相同的算法，得出收集于網(wǎng)絡(luò)，如有侵權(quán)請(qǐng)聯(lián)系管理員刪除精品文檔耗時(shí)最少，費(fèi)用最少的方案。耗時(shí)為26.3小時(shí)，費(fèi)用為4487.2元。針對(duì)問題三的第一小問，知道貨車有4 噸、6 噸和 8 噸三種型號(hào)。經(jīng)過簡(jiǎn)單的論證，排除了4 噸貨車的使用。題目沒有規(guī)定車子不能變向，所以認(rèn)為車輛可以掉頭。然后仍舊采取 公司順時(shí)針?biāo)拓洠?公司逆

3、時(shí)針?biāo)拓浀姆桨?。最后在滿足公司需求量的條件下，采用不同噸位滿載運(yùn)輸方案，此方案分為三個(gè)步驟：第一，使8 噸車次滿載并運(yùn)往同一公司；第二，6 噸位車次滿載并運(yùn)往同一公司；第三，剩下的貨物若在16 噸內(nèi)，則用 6 噸貨車運(yùn)輸，若在78 噸內(nèi)用 8 噸貨車運(yùn)輸。最后得出耗時(shí)最少、費(fèi)用最省的方案。耗時(shí)為19.6833小時(shí)，費(fèi)用為4403.2元。一、問題重述某地區(qū)有 8個(gè)公司 (如圖一編號(hào)至 )，某天某貨運(yùn)公司要派車將各公司所需的三種原材料 A,B,C從某港口 (編號(hào) )分別運(yùn)往各個(gè)公司。路線是唯一的雙向道路 (如圖 )。貨運(yùn)公司現(xiàn)有一種載重 6噸的運(yùn)輸車，派車有固定成本 20元/ 輛，從港口出車有固定

4、成本為 10元/車次 (車輛每出動(dòng)一次為一車次)。每輛車平均需要用 15分鐘的時(shí)間裝車，到每個(gè)公司卸車時(shí)間平均為10分鐘，運(yùn)輸車平均速度為60公里小時(shí) (不考慮塞車現(xiàn)象 )，每日工作不超過 8小時(shí)。運(yùn)輸車載重運(yùn)費(fèi)1.8元/ 噸公里，運(yùn)輸車空載費(fèi)用0.4元/ 公里。一個(gè)單位的原材料A,B,C分別毛重 4噸、 3噸、 1噸，原材料不能拆分，為了安全，大小收集于網(wǎng)絡(luò)，如有侵權(quán)請(qǐng)聯(lián)系管理員刪除精品文檔件同車時(shí)必須小件在上，大件在下。卸貨時(shí)必須先卸小件，而且不允許卸下來(lái)的材料再裝上車，另外必須要滿足各公司當(dāng)天的需求量(見表 )。 問題：1、貨運(yùn)公司派出運(yùn)輸車 6輛，每輛車從港口出發(fā) (不定方向 )后運(yùn)輸

5、途中不允許掉頭，應(yīng)如何調(diào)度(每輛車的運(yùn)載方案，運(yùn)輸成本)使得運(yùn)費(fèi)最小。2、每輛車在運(yùn)輸途中可隨時(shí)掉頭，若要使得成本最小，貨運(yùn)公司怎么安排車輛數(shù)？應(yīng)如何調(diào)度？3、(1)如果有載重量為 4噸、 6噸、 8噸三種運(yùn)輸車，載重運(yùn)費(fèi)都是1.8元/ 噸公里，空載費(fèi)用分別為 0.2，0.4，0.7元/ 公里，其他費(fèi)用一樣，又如何安排車輛數(shù)和調(diào)度方案？ (2)當(dāng)各個(gè)公司間都有或者部分有道路直接相通時(shí)，分析運(yùn)輸調(diào)度的難度所在，給出你的解決問題的想法 (可結(jié)合實(shí)際情況深入分析 )。圖唯一的運(yùn)輸路線圖和里程數(shù)收集于網(wǎng)絡(luò)，如有侵權(quán)請(qǐng)聯(lián)系管理員刪除精品文檔公司材料A41231025B15012423C52424351表

6、各公司所需要的貨物量二、模型假設(shè)1) 運(yùn)輸車正常出車。2) 假設(shè)運(yùn)輸車不會(huì)因天氣狀況，而影響其行駛速度，和裝載、卸載時(shí)間。3) 運(yùn)輸路不會(huì)影響運(yùn)輸車行駛速度。4) 多輛運(yùn)輸車可以在港口同時(shí)裝車，不必等待。5) 8 個(gè)公司之間沒有優(yōu)先級(jí)別，貨運(yùn)公司只要滿足他們的需求量就可以。三、問題分析運(yùn)輸過程的最大特點(diǎn)是三種原料重量不同，分為大小件，當(dāng)大小件同車，卸貨時(shí)必須先卸小件，而且不允許卸下來(lái)的材料再裝上車，要區(qū)別對(duì)待運(yùn)輸途中是否可以調(diào)頭的費(fèi)用。在問題一中，運(yùn)輸途中不能調(diào)頭，整個(gè)送貨路線是一個(gè)環(huán)形閉合回路，如果沿著某一方向同時(shí)給多家公司送貨時(shí)，運(yùn)輸車必須為距離港口近的公司卸下小件，為距離港口遠(yuǎn)的公司運(yùn)送

7、大件；而在問題二中，運(yùn)輸途中可以調(diào)頭，可以首先為遠(yuǎn)處公司運(yùn)送小件，在返回途中為距離較近的收集于網(wǎng)絡(luò)，如有侵權(quán)請(qǐng)聯(lián)系管理員刪除精品文檔公司卸下大件。從表面上看，這樣運(yùn)輸能夠節(jié)省車次，降低出車費(fèi)用。但通過分析，在本題中，載重調(diào)頭運(yùn)輸并不能降低費(fèi)用。運(yùn)費(fèi)最小是貨運(yùn)公司調(diào)度運(yùn)輸車的目標(biāo)，運(yùn)費(fèi)包括派車固定成本、從港口出車成本、載重費(fèi)用和空載費(fèi)用。建立模型時(shí)，要注意以下幾方面的問題：目標(biāo)層：如果將調(diào)度車數(shù)、車次以及每車次的載重和卸貨點(diǎn)都設(shè)為變量，模型中變量過多，不易求解。由于各輛運(yùn)輸車之間相互獨(dú)立，可以將目標(biāo)轉(zhuǎn)化為：求解車次總數(shù)和每車次的裝卸方案，安排盡量少的車輛數(shù)，每車次盡量滿載，使總的運(yùn)費(fèi)最小。約束層

8、：(1)運(yùn)輸車可以從順時(shí)針或者逆時(shí)針方向送貨，要考慮不同方向時(shí)的載重費(fèi)用；(2)大小件的卸車順序要求不同原料搭配運(yùn)輸時(shí)，沿途必須有序卸貨;(3)每車次的送貨量不能超過運(yùn)輸車的最大載重量；(4)滿足各公司當(dāng)日需求。四、符號(hào)說明和名詞約定表 2符號(hào)含義單位備注s1(n)從港口到各個(gè)公司的貨運(yùn)最短里程集公里n=1、2、 、8;收集于網(wǎng)絡(luò)，如有侵權(quán)請(qǐng)聯(lián)系管理員刪除s2(n)w(n)times(n)times(j,n)ydcharge(d)ttdTime(d)精品文檔卸載后從各公司返回港口的最短空載里程集公里n=1、2、 、8;n=1、兩批次貨物運(yùn)至第 n公司貨物的總重量集噸、 、28;n=1、兩批次貨

9、物運(yùn)至第 n公司的總次數(shù)集次、 、28;兩類貨車運(yùn)至第 n 公司的次數(shù)集次n=1、2、 、8;j=1 、2;第d問中組合運(yùn)輸?shù)馁M(fèi)用集元d=1、2、3；第d問中所有的運(yùn)輸費(fèi)用集元d=1、2、3；第d問中組合運(yùn)輸?shù)暮臅r(shí)集小時(shí)d=1、2、3；第d問中所有的運(yùn)輸耗時(shí)集小時(shí)d=1、2、3；五、建立模型一、問題一i. 車次規(guī)劃模型的分析在符合載重相對(duì)最大化情況下， 公司順時(shí)針?biāo)拓洖樽罴逊桨福?公司逆時(shí)針?biāo)拓涀罴逊桨?。ii. 模型建立根據(jù)車輛載重條件，可分為四種滿載方案：第1種是每個(gè)車次裝載2個(gè)單位 B；第 2種是每個(gè)車次裝載 6個(gè)單位 C；第 3種是每個(gè)車次裝載1個(gè)單位 A和2個(gè)單位 C；第 4種是每個(gè)車

10、次裝載 1個(gè)單位 B和3個(gè)單位收集于網(wǎng)絡(luò)，如有侵權(quán)請(qǐng)聯(lián)系管理員刪除精品文檔C。但基于要使總運(yùn)費(fèi)最少以及滿足各公司每日需求。篩選出兩種運(yùn)載方案：第 1種為每個(gè)車次裝載 1單位 A和2單位 C；第 2種是每個(gè)車次裝載 2個(gè)單位 B。并使每一車次在同一公司卸貨。具體程序見附錄一。然后，第一批次運(yùn)輸，我們使 A 材料有優(yōu)先運(yùn)輸權(quán)，在保證滿足各公司對(duì) A 需求量條件下， 1C 與 1A 搭配滿足載重相對(duì)最大化方法運(yùn)輸；第二批次運(yùn)輸，我們使 B 材料有優(yōu)先運(yùn)輸權(quán)，在此次運(yùn)輸我們滿足各公司尚缺 B 材料的量小于或等于 2 個(gè)單位；第三批次運(yùn)輸剩下所需的貨物。由此可知共出車 28 次。如下表：表 3時(shí)間運(yùn)費(fèi)各

11、車工作時(shí)間車輛車次數(shù)公司貨物（?。ㄔㄐr(shí)）時(shí)）11A,2C1.4167107.221A,2C1.4167107.2132A,2C1.41671807.083543A,2C1.4167273.653A,2C1.4167273.664A,2C1.4167325.675A,2C1.4167263.2287A,2C1.4167138.47.083597A,2C1.4167138.41022B1.41671801122B1.416718031252B1.4167263.27.08351362B1.41671801462B1.4167180收集于網(wǎng)絡(luò)，如有侵權(quán)請(qǐng)聯(lián)系管理員刪除精品文檔1572B1.41

12、67138.41682B1.416776178A,C1.4167674188A1.4167587.0835198A1.416758208A1.416758218A1.4167585221A,C1.416792.86.1334231A1.416778.4241，22B1.5833142.2254A1.4167221.26264A1.4167221.26.0333277,6，56C1.75198.4288，42B1.5833206iii. 目標(biāo)分析運(yùn)費(fèi)最小是貨運(yùn)公司調(diào)度運(yùn)輸車的目標(biāo)，運(yùn)費(fèi)包括派車固定成本、從港口出車成本、載重費(fèi)用和空載費(fèi)用。符號(hào)說明和名詞約定見表 2。8ch arge( d )y(

13、 d )1. 8 * s1( n) *w( n) 0. 4 * s2( n) * times ( n) 10 * times ( n);n 18time ( d )tt( d)times ( n) * ( 15 / 12);n1其中 d1；操作程序見附錄二。最后經(jīng)過模型的計(jì)算 , 運(yùn)輸總費(fèi)用為 4864元，運(yùn)輸總時(shí)間為40.3333小時(shí)。二、問題二i. 車次規(guī)劃模型的分析收集于網(wǎng)絡(luò)，如有侵權(quán)請(qǐng)聯(lián)系管理員刪除精品文檔運(yùn)載里程與空載里程相同（表四中的第28 車次例外），且每次出車均不繞圈工作。車輛載重行程是各公司到港口的最短路，且載重費(fèi)用固定不變。ii.模型建立根據(jù)第（ 1）問的分析，分為兩種滿載

14、方案：第1 種為每個(gè)車次裝載 1 單位 A 和 2 單位 C；第 2 種是每個(gè)車次裝載2 個(gè)單位 B。并使每一車次在同一公司卸貨。然后，采用批次運(yùn)輸方案：第一批次運(yùn)輸，使 A 材料有優(yōu)先運(yùn)輸權(quán)，在保證滿足各公司對(duì)A 需求量條件下， C 與 A 搭配滿足載重相對(duì)最大化方法運(yùn)輸；第二批次運(yùn)輸，使B 材料有優(yōu)先運(yùn)輸權(quán)，在此次運(yùn)輸滿足各公司尚缺B 材料的量小于2 個(gè)單位；第三批次運(yùn)輸剩下的貨物。最終車次運(yùn)載方案如下表：表 4車輛車次公司貨物時(shí)間（小運(yùn)費(fèi)各車工作時(shí)間時(shí)）（小時(shí)）11A,2C0.683489.621A,2C0.683489.632A,2C0.9167168143A,2C1.2167268.

15、87.283753A,2C1.2167268.864A,2C1.3834324.875A,2C1.1834257.687A,2C0.7834123.2297A,2C0.7834123.27.78381022B0.9167168收集于網(wǎng)絡(luò)，如有侵權(quán)請(qǐng)聯(lián)系管理員刪除精品文檔1122B0.91671681252B1.1834257.61362B0.91671681462B0.91671681572B0.7834123.21682B0.583456178A,C0.583447188A0.583438198A0.5834383208A0.5834384.2838218A0.583438221A,C0.6

16、83475.2231A0.683460.8241， 22B1.0833130.2254A1.3834220.44264A1.3834220.46.95017，276C1.5167192.86， 5288， 42B1.5833206iii. 目標(biāo)分析運(yùn)費(fèi)最小是貨運(yùn)公司調(diào)度運(yùn)輸車的目標(biāo)，運(yùn)費(fèi)包括派車固定成本、從港口出車成本、載重費(fèi)用和空載費(fèi)用。符號(hào)說明和名詞約定見表 2。8ch arge( d)y( d)1. 8 * s1( n) * w( n)0. 4 * s1( n) * times ( n) 10 * times ( n);n 18time ( d)tt( d )times ( n) * (

17、 s（1 n)/305 / 12);n1其中 d2；操作程序見附錄三。收集于網(wǎng)絡(luò)，如有侵權(quán)請(qǐng)聯(lián)系管理員刪除精品文檔最后經(jīng)過模型的計(jì)算 , 運(yùn)輸總費(fèi)用為 4487.2元，運(yùn)輸總時(shí)間為26.3000小時(shí)。三、問題三第（ 1）小問：根據(jù)第題目分析，題目中給出了3 種型號(hào)的貨車， 4 噸， 6 噸， 8噸。而且沒有規(guī)定不能掉頭，故認(rèn)為可以掉頭。假設(shè)在距離港口公里的地方，需要貨物噸，則使用4 噸和 8 噸貨車運(yùn)送的費(fèi)用如下（因?yàn)閷嵷浳镞\(yùn)送到目的地的載重費(fèi)是相同的，故只關(guān)注空載費(fèi)用和出車費(fèi)用）4 噸貨車運(yùn)送費(fèi)用， M/4*(0.2*+10) ；8 噸貨車運(yùn)送費(fèi)用， M/8*(0.7*+10) ；當(dāng) &g

18、t;33.3 時(shí)，使用 4 噸貨車運(yùn)輸比 8 噸貨車更省費(fèi)用。然而在允許掉頭的情況下，按之前方案進(jìn)行運(yùn)送，沒有超過33.3公里。所以不需要使用 4 噸貨車，只使用6 噸， 8 噸貨車搭配運(yùn)貨即可。i. 模型建立第一步，使 8 噸車次滿載并運(yùn)往同一公司；第二步，使 6 噸位車次滿載并運(yùn)往同一公司；運(yùn)載方案如下表：表 5車輛車次公司貨物時(shí)間（小各車工作時(shí)間時(shí)）運(yùn)費(fèi)（小時(shí)）第一輛 8112A0.6834120.8噸車212A0.68346.9504120.8收集于網(wǎng)絡(luò)，如有侵權(quán)請(qǐng)聯(lián)系管理員刪除精品文檔31B,5C0.6834120.842A,B,C0.9167226.5532A1.2167362.4

19、642A1.3834437.974A,B,C1.3834437.985A,B,C1.1834347.3962B,2C0.9167226.51072A0.7834166.1第二輛 872B,2C0.7834166.15.417111噸車82A0.583475.5121382A0.583475.5148A,B,C0.583475.51522B0.91671687.31691622B0.9167168第一輛 65B,3C1.1834257.617噸車62B0.9167168181982B0.583456第三步，經(jīng)計(jì)算可知只剩下2,3,4,6,7公司需要 C貨物 10噸，必須要用至少兩個(gè)車次來(lái)運(yùn)。為了

20、使費(fèi)用降低，決定用2個(gè)6噸車次來(lái)運(yùn)貨，具體運(yùn)載方案如下表：表6時(shí)間各車工作車輛車次公司貨物（小運(yùn)費(fèi)時(shí)間（小時(shí)）時(shí)）第一輛202，3，41C，4C，1.7167263.61.71671C6 噸車217,63C,1C1.083392.41.0833收集于網(wǎng)絡(luò)，如有侵權(quán)請(qǐng)聯(lián)系管理員刪除精品文檔ii. 目標(biāo)分析運(yùn)費(fèi)最小是貨運(yùn)公司調(diào)度運(yùn)輸車的目標(biāo)，運(yùn)費(fèi)包括派車固定成本、從港口出車成本、載重費(fèi)用和空載費(fèi)用。符號(hào)說明和名詞約定見表2。81. 8*（(1)2)）（）（）ch arg e( d)y( d)s1(n) * W( n)10 *times(1)( n) times( 2)( n) ;n 18time(

21、 d)tt ( d)times(n) * (s（1n) / 305 / 12);n1其中d3；操作程序見附錄四。最后經(jīng)過模型的計(jì)算 , 運(yùn)輸總費(fèi)用為 4403.2元，運(yùn)輸總時(shí)間為19.6833小時(shí)。第（ 2）小問：當(dāng)部分公司接通后，對(duì)于各個(gè)車輛的運(yùn)輸安排并不改變，就是找到通往該公司的路徑最短，使總的運(yùn)輸費(fèi)用最少，但是由于連通了各個(gè)公司的路徑變得復(fù)雜，因此我們就忽略空載時(shí)的返回路徑，僅僅考慮每一噸貨物以最短的路徑到達(dá)目的地。此問題就可以看作是無(wú)向圖來(lái)研究路線拓?fù)鋱D，將所有公司和港口看作是節(jié)點(diǎn)，得到各節(jié)點(diǎn)之間最短的距離矩陣如下，A9*9=a11,a12a19;a21,a22a29;a91,a92

22、a99其中 aij 表示公司i 到公司 j 的最短路徑，當(dāng) aij 不存在時(shí)，記為無(wú)窮大，由Dijkstra 算法得到港口九到收集于網(wǎng)絡(luò)，如有侵權(quán)請(qǐng)聯(lián)系管理員刪除精品文檔其他公司的最短路徑，按照最短路徑運(yùn)輸貨物可以將費(fèi)用降到最低。六、附錄附錄一 :model:sets :num/1.4/:x,a,b,c;endsetsdata :a=0,0,1,0;b=2,0,0,1;c=0,6,2,3;enddatamin=sum(num(i):x(i);sum(num(i):a(i)*x(i)>=18;!滿足 A類貨物總數(shù)sum(num(i):b(i)*x(i)>=18;!滿足 B類貨物總數(shù)s

23、um(num(i):c(i)*x(i)>=26;!滿足 C類貨物總數(shù)end收集于網(wǎng)絡(luò)，如有侵權(quán)請(qǐng)聯(lián)系管理員刪除精品文檔附錄二：clcs1=8,15,24,29,23,15,11,5;s2=52,45,36,31,37,45,49,55;w=21,18,12,14,12,12,18,27;times=4,3,2,3,2,2,3,6;tt1=4.9166;y1=576.6;sum1=0;sum2=0;sum3=0;for n=1:8sum1=sum1+1.8*s1(n)*w(n);sum2=sum2+0.4*s2(n)*times(n);sum3=sum3+10*times(n);endch

24、ange(1)=120+y1+sum1+sum2+sum3;disp('問題一運(yùn)輸總費(fèi)用： ');disp(change(1);tt=0;for n=1:8tt=tt+times(n)*(1+5/12);endTime(1)=tt1+tt;disp('問題一運(yùn)輸總時(shí)間：');收集于網(wǎng)絡(luò)，如有侵權(quán)請(qǐng)聯(lián)系管理員刪除精品文檔disp(Time(1);結(jié)果為：?jiǎn)栴}一運(yùn)輸總費(fèi)用： 4.8640e+003問題一運(yùn)輸總時(shí)間： 40.3333附錄三：clcs1=8,15,24,29,23,15,11,5;w=21,18,12,14,12,12,18,27;times=4,3,2,3,2,2,3,6;tt2=4.1833;Y2=559;sum1=0;sum2=0;sum3=0;for n=1:8sum1=sum1+1.8*s1(n)*w(n);sum2=sum2+0.4*s1(n)*times(n);sum3=sum3+10*time