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

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

2、我們使B材料有優(yōu)先運(yùn)輸權(quán)；在第三批次中運(yùn)輸剩下所需的貨物。最后得出耗時最少、費(fèi)用最少的方案。耗時為40.3333小時，費(fèi)用為4864.0元。針對問題二，加上兩個定理及其推論數(shù)學(xué)模型與問題一幾乎相同，只是空載路徑不同。采取與問題一相同的算法，得出耗時最少，費(fèi)用最少的方案。耗時為26.3小時，費(fèi)用為4487.2元。針對問題三的第一小問，知道貨車有4噸、6噸和8噸三種型號。經(jīng)過簡單的論證，排除了4噸貨車的使用。題目沒有規(guī)定車子不能變向，所以認(rèn)為車輛可以掉頭。然后仍舊采取公司順時針?biāo)拓洠灸鏁r針?biāo)拓浀姆桨?。最后在滿足公司需求量的條件下，采用不同噸位滿載運(yùn)輸方案，此方案分為三個步驟：第一，使8噸車次滿

3、載并運(yùn)往同一公司；第二，6噸位車次滿載并運(yùn)往同一公司；第三，剩下的貨物若在16噸內(nèi)，則用6噸貨車運(yùn)輸，若在78噸內(nèi)用8噸貨車運(yùn)輸。最后得出耗時最少、費(fèi)用最省的方案。耗時為19.6833小時，費(fèi)用為4403.2元。一、問題重述某地區(qū)有8個公司(如圖一編號至)，某天某貨運(yùn)公司要派車將各公司所需的三種原材料A,B,C從某港口(編號)分別運(yùn)往各個公司。路線是唯一的雙向道路(如圖)。貨運(yùn)公司現(xiàn)有一種載重 6噸的運(yùn)輸車，派車有固定成本20元/輛，從港口出車有固定成本為10元/車次(車輛每出動一次為一車次)。每輛車平均需要用15分鐘的時間裝車，到每個公司卸車時間平均為10分鐘，運(yùn)輸車平均速度為60公里小時(

4、不考慮塞車現(xiàn)象)，每日工作不超過8小時。運(yùn)輸車載重運(yùn)費(fèi)1.8元/噸公里，運(yùn)輸車空載費(fèi)用0.4元/公里。一個單位的原材料A,B,C分別毛重4噸、3噸、1噸，原材料不能拆分，為了安全，大小件同車時必須小件在上，大件在下。卸貨時必須先卸小件，而且不允許卸下來的材料再裝上車，另外必須要滿足各公司當(dāng)天的需求量(見表)。 問題：1、貨運(yùn)公司派出運(yùn)輸車6輛，每輛車從港口出發(fā)(不定方向)后運(yùn)輸途中不允許掉頭，應(yīng)如何調(diào)度(每輛車的運(yùn)載方案，運(yùn)輸成本)使得運(yùn)費(fèi)最小。2、每輛車在運(yùn)輸途中可隨時掉頭，若要使得成本最小，貨運(yùn)公司怎么安排車輛數(shù)？應(yīng)如何調(diào)度？3、(1)如果有載重量為4噸、6噸、8噸三種運(yùn)輸車，載重運(yùn)費(fèi)都是

5、1.8元/噸公里，空載費(fèi)用分別為0.2，0.4，0.7元/公里，其他費(fèi)用一樣，又如何安排車輛數(shù)和調(diào)度方案？(2)當(dāng)各個公司間都有或者部分有道路直接相通時，分析運(yùn)輸調(diào)度的難度所在，給出你的解決問題的想法(可結(jié)合實(shí)際情況深入分析)。圖唯一的運(yùn)輸路線圖和里程數(shù)公司材料A41231025B15012423C52424351表各公司所需要的貨物量二、模型假設(shè)1) 運(yùn)輸車正常出車。2) 假設(shè)運(yùn)輸車不會因天氣狀況，而影響其行駛速度，和裝載、卸載時間。3) 運(yùn)輸路不會影響運(yùn)輸車行駛速度。4) 多輛運(yùn)輸車可以在港口同時裝車，不必等待。5) 8個公司之間沒有優(yōu)先級別，貨運(yùn)公司只要滿足他們的需求量就可以。三、問題分

6、析運(yùn)輸過程的最大特點(diǎn)是三種原料重量不同，分為大小件，當(dāng)大小件同車，卸貨時必須先卸小件，而且不允許卸下來的材料再裝上車，要區(qū)別對待運(yùn)輸途中是否可以調(diào)頭的費(fèi)用。在問題一中，運(yùn)輸途中不能調(diào)頭，整個送貨路線是一個環(huán)形閉合回路，如果沿著某一方向同時給多家公司送貨時，運(yùn)輸車必須為距離港口近的公司卸下小件，為距離港口遠(yuǎn)的公司運(yùn)送大件；而在問題二中，運(yùn)輸途中可以調(diào)頭，可以首先為遠(yuǎn)處公司運(yù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)用和

7、空載費(fèi)用。建立模型時，要注意以下幾方面的問題：目標(biāo)層：如果將調(diào)度車數(shù)、車次以及每車次的載重和卸貨點(diǎn)都設(shè)為變量，模型中變量過多，不易求解。由于各輛運(yùn)輸車之間相互獨(dú)立，可以將目標(biāo)轉(zhuǎn)化為：求解車次總數(shù)和每車次的裝卸方案，安排盡量少的車輛數(shù)，每車次盡量滿載，使總的運(yùn)費(fèi)最小。約束層：(1)運(yùn)輸車可以從順時針或者逆時針方向送貨，要考慮不同方向時的載重費(fèi)用；(2)大小件的卸車順序要求不同原料搭配運(yùn)輸時，沿途必須有序卸貨;(3)每車次的送貨量不能超過運(yùn)輸車的最大載重量；(4)滿足各公司當(dāng)日需求。四、符號說明和名詞約定表2符號含義單位備注s1(n)從港口到各個公司的貨運(yùn)最短里程集公里n=1、2、8;s2(n)卸

8、載后從各公司返回港口的最短空載里程集公里n=1、2、8;w(n)兩批次貨物運(yùn)至第n公司貨物的總重量集噸n=1、2、8;times(n)兩批次貨物運(yùn)至第n公司的總次數(shù)集次n=1、2、8;times(j,n)兩類貨車運(yùn)至第n公司的次數(shù)集次n=1、2、8;j=1、2;yd第d問中組合運(yùn)輸?shù)馁M(fèi)用集元d=1、2、3；charge(d)第d問中所有的運(yùn)輸費(fèi)用集元d=1、2、3；ttd第d問中組合運(yùn)輸?shù)暮臅r集小時d=1、2、3；Time(d)第d問中所有的運(yùn)輸耗時集小時d=1、2、3；五、建立模型一、問題一i. 車次規(guī)劃模型的分析在符合載重相對最大化情況下，公司順時針?biāo)拓洖樽罴逊桨?，公司逆時針?biāo)拓涀罴逊桨浮?/p>

9、ii. 模型建立根據(jù)車輛載重條件，可分為四種滿載方案：第1種是每個車次裝載2個單位B；第2種是每個車次裝載6個單位C；第3種是每個車次裝載1個單位A和2個單位C；第4種是每個車次裝載1個單位B和3個單位C。但基于要使總運(yùn)費(fèi)最少以及滿足各公司每日需求。篩選出兩種運(yùn)載方案：第1種為每個車次裝載1單位A和2單位C；第2種是每個車次裝載2個單位B。并使每一車次在同一公司卸貨。具體程序見附錄一。然后，第一批次運(yùn)輸，我們使A材料有優(yōu)先運(yùn)輸權(quán)，在保證滿足各公司對A需求量條件下，1C與1A搭配滿足載重相對最大化方法運(yùn)輸；第二批次運(yùn)輸，我們使B材料有優(yōu)先運(yùn)輸權(quán)，在此次運(yùn)輸我們滿足各公司尚缺B材料的量小于或等于2

10、個單位；第三批次運(yùn)輸剩下所需的貨物。由此可知共出車28次。如下表：表3車輛車次數(shù)公司貨物時間（小時）運(yùn)費(fèi)（元）各車工作時間（小時）111A,2C1.4167107.27.083521A,2C1.4167107.232A,2C1.416718043A,2C1.4167273.653A,2C1.4167273.6264A,2C1.4167325.67.083575A,2C1.4167263.287A,2C1.4167138.497A,2C1.4167138.41022B1.416718031122B1.41671807.08351252B1.4167263.21362B1.41671801462B

11、1.41671801572B1.4167138.441682B1.4167767.0835178A,C1.416767188A1.416758198A1.416758208A1.4167585218A1.4167586.1334221A,C1.416792.8231A1.416778.4241，22B1.5833142.26254A1.4167221.26.0333264A1.4167221.2277,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)用。符號說明和名詞約定見表

12、2。操作程序見附錄二。最后經(jīng)過模型的計(jì)算, 運(yùn)輸總費(fèi)用為4864元，運(yùn)輸總時間為40.3333小時。二、問題二i. 車次規(guī)劃模型的分析運(yùn)載里程與空載里程相同（表四中的第28車次例外），且每次出車均不繞圈工作。車輛載重行程是各公司到港口的最短路，且載重費(fèi)用固定不變。ii. 模型建立根據(jù)第（1）問的分析，分為兩種滿載方案：第1種為每個車次裝載1單位A和2單位C；第2種是每個車次裝載2個單位B。并使每一車次在同一公司卸貨。然后，采用批次運(yùn)輸方案：第一批次運(yùn)輸，使A材料有優(yōu)先運(yùn)輸權(quán)，在保證滿足各公司對A需求量條件下，C與A搭配滿足載重相對最大化方法運(yùn)輸；第二批次運(yùn)輸，使B材料有優(yōu)先運(yùn)輸權(quán)，在此次運(yùn)輸滿

13、足各公司尚缺B材料的量小于2個單位；第三批次運(yùn)輸剩下的貨物。最終車次運(yùn)載方案如下表：表4車輛車次公司貨物時間（小時）運(yùn)費(fèi)各車工作時間（小時）111A,2C0.683489.67.283721A,2C0.683489.632A,2C0.916716843A,2C1.2167268.853A,2C1.2167268.864A,2C1.3834324.875A,2C1.1834257.6287A,2C0.7834123.27.783897A,2C0.7834123.21022B0.91671681122B0.91671681252B1.1834257.61362B0.91671681462B0.91

14、671681572B0.7834123.21682B0.5834563178A,C0.5834474.2838188A0.583438198A0.583438208A0.583438218A0.583438221A,C0.683475.2231A0.683460.84241，22B1.0833130.26.9501254A1.3834220.4264A1.3834220.4277，6，56C1.5167192.8288，42B1.5833206iii. 目標(biāo)分析運(yùn)費(fèi)最小是貨運(yùn)公司調(diào)度運(yùn)輸車的目標(biāo)，運(yùn)費(fèi)包括派車固定成本、從港口出車成本、載重費(fèi)用和空載費(fèi)用。符號說明和名詞約定見表2。操作程序見附錄

15、三。最后經(jīng)過模型的計(jì)算, 運(yùn)輸總費(fèi)用為4487.2元，運(yùn)輸總時間為26.3000小時。三、問題三第（1）小問：根據(jù)第題目分析，題目中給出了3種型號的貨車，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)>33.3時，使用4噸貨車運(yùn)輸比8噸貨車更省費(fèi)用。然而在允許掉頭的情況下，按之前方案進(jìn)行運(yùn)送，沒有超過33.3公里。所以不需要使用4噸貨車，只使用

16、6噸，8噸貨車搭配運(yùn)貨即可。i. 模型建立第一步，使8噸車次滿載并運(yùn)往同一公司；第二步，使6噸位車次滿載并運(yùn)往同一公司；運(yùn)載方案如下表：表5車輛車次公司貨物時間（小時）運(yùn)費(fèi)各車工作時間（小時）第一輛8噸車112A0.6834120.86.9504212A0.6834120.831B,5C0.6834120.842A,B,C0.9167226.5532A1.2167362.4642A1.3834437.974A,B,C1.3834437.9第二輛8噸車85A,B,C1.1834347.35.4171962B,2C0.9167226.51072A0.7834166.11172B,2C0.78341

17、66.11282A0.583475.51382A0.583475.5148A,B,C0.583475.5第一輛6噸車1522B0.91671687.31691622B0.9167168175B,3C1.1834257.61862B0.91671681982B0.583456第三步，經(jīng)計(jì)算可知只剩下2,3,4,6,7公司需要C貨物10噸，必須要用至少兩個車次來運(yùn)。為了使費(fèi)用降低，決定用2個6噸車次來運(yùn)貨，具體運(yùn)載方案如下表：表6車輛車次公司貨物時間（小時）運(yùn)費(fèi)各車工作時間（小時）第一輛6噸車202，3，41C，4C，1C1.7167263.61.7167217,63C,1C1.083392.41

18、.0833ii. 目標(biāo)分析運(yùn)費(fèi)最小是貨運(yùn)公司調(diào)度運(yùn)輸車的目標(biāo)，運(yùn)費(fèi)包括派車固定成本、從港口出車成本、載重費(fèi)用和空載費(fèi)用。符號說明和名詞約定見表2。操作程序見附錄四。最后經(jīng)過模型的計(jì)算, 運(yùn)輸總費(fèi)用為4403.2元，運(yùn)輸總時間為19.6833小時。第（2）小問：當(dāng)部分公司接通后，對于各個車輛的運(yùn)輸安排并不改變，就是找到通往該公司的路徑最短，使總的運(yùn)輸費(fèi)用最少，但是由于連通了各個公司的路徑變得復(fù)雜，因此我們就忽略空載時的返回路徑，僅僅考慮每一噸貨物以最短的路徑到達(dá)目的地。此問題就可以看作是無向圖來研究路線拓?fù)鋱D，將所有公司和港口看作是節(jié)點(diǎn)，得到各節(jié)點(diǎn)之間最短的距離矩陣如下，A9*9=a11,a12

19、a19;a21,a22a29;a91,a92a99其中aij表示公司i到公司j的最短路徑，當(dāng)aij不存在時，記為無窮大，由Dijkstra算法得到港口九到其他公司的最短路徑，按照最短路徑運(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ù)sum(num(i):c

20、(i)*x(i)>=26; !滿足C類貨物總數(shù)end附錄二：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:8 sum1=sum1+1.8*s1(n)*w(n); sum2=sum2+0.4*s2(n)*times(n); sum3=sum3+10*times(n);endchange(1)=120+y1+sum1+sum2+sum3;

21、disp('問題一運(yùn)輸總費(fèi)用：');disp(change(1);tt=0;for n=1:8 tt=tt+times(n)*(1+5/12);endTime(1)=tt1+tt;disp('問題一運(yùn)輸總時間 ：');disp(Time(1);結(jié)果為：問題一運(yùn)輸總費(fèi)用：4.8640e+003問題一運(yùn)輸總時間：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:8 sum1=sum1+1.8*s1(n)*w(n); sum2=sum2+0.4*s1(n)*times(n); sum3=sum3+10*times(n);endchange(2)=80+y2+sum1+sum2+sum3