數(shù)學(xué)建模大賽貨物運(yùn)輸問題

【摘要】本文是針對(duì)解決某港口對(duì)某地區(qū)

8

個(gè)公司所需原材料

A、B、C

的運(yùn)輸調(diào)度問題合理的優(yōu)化模型，求出較為優(yōu)化的調(diào)配方案。針對(duì)問題一，我們?cè)趦蓚€(gè)大的方面進(jìn)行分析與優(yōu)化。第一方面是對(duì)車次安排二方面我們根據(jù)車載重相對(duì)最大化思想使方案分為兩個(gè)步驟，第一步先是使每個(gè)車次滿載并運(yùn)往同一個(gè)公司，第二步采用分批次運(yùn)輸?shù)姆桨福丛诘谝慌芜\(yùn)輸在第三批次中運(yùn)輸剩下所需的貨物。最后得出耗時(shí)最少、費(fèi)用最少的方案。耗時(shí)為40.5007小時(shí)，費(fèi)用為4685.6元。針對(duì)問題二，加上兩個(gè)定理及其推論數(shù)學(xué)模型與問題一幾乎相同，只是空載路徑不同。我們采取與問題一相同的算法，得出耗時(shí)最少，費(fèi)用最少的方案。耗時(shí)為

26.063

小時(shí)，費(fèi)用為

4374.4

元。針對(duì)問題三的第一小問，我們知道貨車有

4

噸、6

噸和

8

噸三種型號(hào)。我

4

認(rèn)為車輛可以掉頭。然后我們?nèi)耘f采?、?/p>

~④公司順時(shí)針?biāo)拓?，⑤~⑧公司逆時(shí)針?biāo)拓浀姆桨?。最后在滿足公司需求量的條件下，采用不同噸位滿載運(yùn)輸方案，此方案分為三個(gè)步驟：第一，使8

噸位車次滿載并運(yùn)往同一公司；第三，剩下的貨物若在1~6

噸內(nèi)，則用

6

噸貨車運(yùn)輸，若在

7~8

噸內(nèi)用

8

噸貨車運(yùn)輸。最后得出耗時(shí)最少、費(fèi)用最省的方案。耗時(shí)為19.6844

小時(shí)，費(fèi)用為4403.2。一、

問題重述某地區(qū)有

8

個(gè)公司(如圖一編號(hào)①至⑧)，某天某貨運(yùn)公司要派車將各公司所需的三種原材料

A,B,C

從某港口(編號(hào)⑨)分別運(yùn)往各個(gè)公司。路線是唯一的雙向

6

20

從港口出車有固定成本為

10

元/車次(車輛每出動(dòng)一次為一車次)。每輛車平均需要用

15

10

為

60

公里／小時(shí)(不考慮塞車現(xiàn)象)，每日工作不超過

8

小時(shí)。運(yùn)輸車載重運(yùn)費(fèi)1.8

0.4

A,B,C

分別毛重4

噸、3

噸，原材料不能拆分，為了安全，大小件同車時(shí)必須小件在上，要滿足各公司當(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)輸途中可隨時(shí)掉頭，若要使得成本最小，貨運(yùn)公司怎么安排車輛數(shù)？應(yīng)如何調(diào)度？

4

1.8

元/噸公里，空載費(fèi)用分別為

元/公里，其他費(fèi)用一樣，又如何安排車輛數(shù)和調(diào)度方案？(2)當(dāng)各個(gè)公司間都有或者部分有道路直接相通時(shí)，分析運(yùn)輸調(diào)度的難度所在，給出你的解決問題的想法(可結(jié)合實(shí)際情況深入分析)。圖１ 唯一的運(yùn)輸路線圖和里程數(shù)公司材料

①

②

③

④

⑤

⑥

⑦

⑧1)2)3)4)

A

4

1

2

3

1

0

2

5B

1

5

0

1

2

4

2

3C

5

2

4

2

4

3

5

1表１

各公司所需要的貨物量二、模型假設(shè)港口的容量足夠大，多輛運(yùn)輸車同時(shí)到達(dá)港口時(shí)不會(huì)發(fā)生阻塞現(xiàn)象；多輛運(yùn)輸車可以在港口同時(shí)裝車，不必等待；雙向道路上沒有塞車現(xiàn)象；8

個(gè)公司之間沒有優(yōu)先級(jí)別，貨運(yùn)公司只要滿足他們的需求量就可以；貨車完成他們?nèi)粘５乃拓浫蝿?wù)之后，回到港口。5)

假設(shè)運(yùn)輸車不會(huì)因天氣狀況，而影響其行駛速度，和裝載、卸載時(shí)間。6)

運(yùn)輸路不會(huì)影響運(yùn)輸車行駛速度。7)

運(yùn)輸車正常出車。三、問題分析運(yùn)輸過程的最大特點(diǎn)是三種原料重量不同，分為大小件，當(dāng)大小件同車，卸貨時(shí)必須先卸小件，而且不允許卸下來的材料再裝上車，要區(qū)別對(duì)待運(yùn)輸途中是否可以調(diào)頭的費(fèi)用。在問題一中，運(yùn)輸途中不能調(diào)頭，整個(gè)送貨路線是一個(gè)環(huán)形閉合回路，如果沿著某一方向同時(shí)給多家公司送貨時(shí)，運(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)用和空載費(fèi)用。建立模型時(shí)，要注意以下幾方面的問題：目標(biāo)層：不易求解。由于各輛運(yùn)輸車之間相互獨(dú)立，可以將目標(biāo)轉(zhuǎn)化為兩個(gè)階段的求解過程，第一階段是規(guī)劃車次階段，求解車次總數(shù)和每車次的裝卸方案；第二階段是車輛調(diào)度階段，安排盡量少的車輛數(shù)，每車次盡量滿載，使總的運(yùn)費(fèi)最小。約束層：(1) 運(yùn)輸車可以從順時(shí)針或者逆時(shí)針方向送貨，要考慮不同方向時(shí)的載重用；(2) 大小件的卸車順序要求不同原料搭配運(yùn)輸時(shí)，沿途必須有序卸貨；(3) 每車次的送貨量不能超過運(yùn)輸車的最大載重量；(4) 滿足各公司當(dāng)日需求。四、符號(hào)說明和名詞約定

n公司對(duì)貨物i的實(shí)時(shí)需求量集

2、…、8；

2、…、8；

2、…、8;

第j批運(yùn)至第n公司貨物的重量集

第j批運(yùn)至第n公司次數(shù)集

第j批運(yùn)至第n公司的費(fèi)用集

五、建立模型一、 問題一 車次規(guī)劃階段只涉及到載重費(fèi)用、

費(fèi)用和港口出車費(fèi)用。運(yùn)輸途中不能掉頭，所以每車次都是沿閉合回路繞圈行駛。1)

運(yùn)輸途中不能掉頭，所以為某些公司送貨時(shí)，運(yùn)輸車從港口出發(fā)，按順時(shí)針方向沿閉合回路繞行，為其它公司送貨時(shí)，按逆時(shí)針方向沿閉合回路繞行。公司和港口之間存在順時(shí)針距離和逆時(shí)針距離，如下表：公司編號(hào) ① ② ③ ④ ⑤ ⑥ ⑦ ⑧順時(shí)針距離 8 15 24 29 37 45 49 55逆時(shí)針距離 52 45 36 31 23 15 11 5由表可知，運(yùn)輸過程中不可以掉頭，為使得貨運(yùn)費(fèi)用最低，我們按照問題分析中給出的最佳運(yùn)輸路徑進(jìn)行貨物的分配運(yùn)輸。即若港口按順時(shí)針和逆時(shí)針兩個(gè)不同方向出發(fā)，根據(jù)貨運(yùn)里程短，④點(diǎn)為順時(shí)針貨運(yùn)方向最遠(yuǎn)點(diǎn)，也是空載回港口的最近點(diǎn)，根據(jù)貨運(yùn)里程短，⑤點(diǎn)為逆時(shí)針貨運(yùn)方向最遠(yuǎn)點(diǎn)，也是空載回港口的最近點(diǎn)。結(jié)論：在符合載重相對(duì)最大化情況下，①~④公司順時(shí)針?biāo)拓洖樽罴逊桨?，⑤~⑧公司逆時(shí)針?biāo)拓涀罴逊桨?。如下圖所示：可以搭配運(yùn)輸，而A與B不能同車運(yùn)輸。不論是以順時(shí)針方向送貨還是以逆時(shí)針方向送貨，當(dāng)大小件搭配運(yùn)輸時(shí)，必須首先卸下小件，在后續(xù)公司卸下大件。我們把這種特點(diǎn)總結(jié)如下：1、若在第j個(gè)公司卸下的是大件A，說明本車次的貨物已經(jīng)卸完，不能夠再為后續(xù)公司運(yùn)送小件C（A與B不能同車運(yùn)輸，更不可能有B）；2、若在第j個(gè)公司卸下的是B，說明本車次的貨物已經(jīng)卸完，不能夠再為后續(xù)公司運(yùn)送小件C。 基于以上約束條件建立如下模型：第一步：根據(jù)車載重相對(duì)最大化的基本思想?？梢苑譃閮尚〔剑簜€(gè)單位B。并使每一車次在同一公司卸貨。滿載運(yùn)載方案如下表1：表1車次車輛 公司 貨物 時(shí)間（小時(shí)）運(yùn)費(fèi)（元）

數(shù)1 1 A,2C 1.4167 107.21 7.08352 1 A,2C 1.4167 107.2234

345678910111213141516

23345772256678

A,2CA,2CA,2CA,2CA,2CA,2CA,2C2B2B2B2B2B2B2B

1.41671.41671.41671.41671.41671.41671.41671.41671.41671.41671.41671.41671.41671.4167

180273.6273.6325.6263.2138.4138.4180180263.2180180138.476

7.08357.0835對(duì)于剩下各公司所需要貨物單位數(shù)量如下表：材料ABC

①211

②010

③000

④210

⑤002

⑥003

⑦001

⑧511第二步：我們采用批次運(yùn)輸方案：第一批次運(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)輸剩下所需的貨物。

A

1

公司還需

1

個(gè)車次的

1A

和一個(gè)車次的

公司還需要

2

個(gè)車次的

公司還需要

4

個(gè)車次的

1A

和

1個(gè)車次的

1A1C；接著處理

B

貨物，1

公司和

2

公司共需要

1

個(gè)車次的

2B,8

公司和

4公司共需要

1

個(gè)車次的

2B;最后處理

C

公司共需要

1

個(gè)車次的

此可知共出車

28

2：表2車次車輛 公司 貨物 時(shí)間（小時(shí)）運(yùn)費(fèi)（元）

各車工作時(shí)間（小時(shí)）數(shù)16 8 2B 1.4167 7617 8 A,C 1.4167 674 7.083518 8 A 1.4167 5819 8 A 1.4167 5820 8 A 1.4167 5821 8 A 1.4167 5822 1 A,C 1.4167 92.85 6.133423 1 A 1.4167 78.424 1，2 2B 1.5833 142.225 4 A 1.4167 221.226 4 A 1.4167 221.26 6.033327 7,6，5 6C 1.75 198.428 8，4 2B 1.5833 2062)

根據(jù)

1）和

2）的結(jié)論及方法，不記派車成本和出車成本的28

車次方案所需運(yùn)費(fèi)

3：表3車次 時(shí)間（小 車輛 公司

貨物 數(shù) 時(shí)） 時(shí)）1 1 A,2C 1.4167 107.22 1 A,2C 1.4167 107.21 3 2 A,2C 1.4167 180 7.08354 3 A,2C 1.4167 273.65 3 A,2C 1.4167 273.66 4 A,2C 1.4167 325.67 5 A,2C 1.4167 263.22 8 7 A,2C 1.4167 138.4 7.08359 7 A,2C 1.4167 138.410 2 2B 1.4167 18011 2 2B 1.4167 18012 5 2B 1.4167 263.23 13 6 2B 1.4167 180 7.083514 6 2B 1.4167 18015 7 2B 1.4167 138.416 8 2B 1.4167 7617 8 A,C 1.4167 674 18 8 A 1.4167 58 7.083519 8 A 1.4167 5820 8 A 1.4167 5821 8 A 1.4167 585 5.833422 1 A,C 1.4167 92.86

232425262728

11，24458，4

A2BAA6C2B

1.41671.58331.41671.41671.751.5833

78.4142.2221.2221.2198.4206

6.1667總

4464

40.5007

n=1、2、…、8；

5； n=1、2、…、8；

3；i=A、B、C；

21； n=1、2、…8；

j=1、2；

5； n=1、2、…、8；

j=1、2；

運(yùn)費(fèi)最小是貨運(yùn)公司調(diào)度運(yùn)輸車的目標(biāo)，運(yùn)費(fèi)包括派車固定成本、從港口出車成本、載重費(fèi)用和空載費(fèi)用。最后經(jīng)過模型的計(jì)算得到最少費(fèi)用為：4840.6元，最少耗時(shí)為：40.4999小時(shí)。

兩個(gè)定理的證明定理一、車輛當(dāng)且僅當(dāng)運(yùn)完最后一件貨物時(shí)才調(diào)頭途中允許調(diào)頭，運(yùn)輸車可以先為較遠(yuǎn)的公司送去小件原料，然后調(diào)頭，為比較近的公司送去大件。從表面上看，這樣運(yùn)輸能夠節(jié)省車次，降低出車費(fèi)用。但我們通過分析，在本題中，載重調(diào)頭運(yùn)輸并不能降低費(fèi)用。證明過程如下：＝1），b為A或B（＝1），b為A或B（

），記運(yùn)費(fèi)用為fS2M S1O在上圖中，記O點(diǎn)為港口，N、M為兩公司。M到港口的距離是S1，NM兩個(gè)公司之間的距離為S2。假設(shè)將兩種貨物a和b（重量分別為x噸、y噸），分別運(yùn)往N和M兩公司，現(xiàn)有兩種運(yùn)輸方案：記運(yùn)費(fèi)用為f

。?

兩種方案需要的車輛相同時(shí)，若f

>

0恒成立，則載重調(diào)頭送貨不節(jié)省費(fèi)用，通過數(shù)據(jù)處理提取函數(shù)：代入到

f

中，化簡(jiǎn)得到令得到而港口到所有公司最短路的最大值為29公里，所以為比較兩種運(yùn)輸方式費(fèi)用的大小，兩種運(yùn)輸?shù)姆N類質(zhì)量均相同，記：若f

>

0恒成立，則載重調(diào)頭送貨不節(jié)省費(fèi)用，通過數(shù)據(jù)處理提取函數(shù)：代入到

f

中，化簡(jiǎn)得到令得到而港口到所有公司最短路的最大值為29公里，所以因?yàn)?/p>

并且N、M兩公司在本題中的最小距離

說明前一種花費(fèi)較高。

恒成立。得到因?yàn)楦劭诘剿泄镜淖疃搪窂剿跃C上，載重調(diào)頭運(yùn)輸花費(fèi)較高。證明了以運(yùn)費(fèi)用最小為目標(biāo)時(shí)，車輛當(dāng)且僅當(dāng)運(yùn)?

方案二比方案一需要的車輛多時(shí)得到因?yàn)楦劭诘剿泄镜淖疃搪窂剿跃C上，載重調(diào)頭運(yùn)輸花費(fèi)較高。證明了以運(yùn)費(fèi)用最小為目標(biāo)時(shí)，車輛當(dāng)且僅當(dāng)運(yùn)第二種方案是出車兩次，運(yùn)輸時(shí)間較長，在8

小時(shí)的工作時(shí)間內(nèi)，可能會(huì)比調(diào)頭載重運(yùn)輸時(shí)多安排車輛，派車費(fèi)用增加。我們考慮一種最差情況，因多運(yùn)一次而增派一輛車，此時(shí)有

完最后一件貨物時(shí)才調(diào)頭。

28

車均不繞圈工作。定理二、車輛載重行程是各公司到港口的最短路，且載重費(fèi)用固定不變?cè)诙ɡ硪坏幕A(chǔ)上，車輛當(dāng)且僅當(dāng)運(yùn)完最后一件貨才調(diào)頭，且每次出車均不繞圈工作，那么每一單位的原料都可以由最短路徑運(yùn)至需貨公司。我們變換視角，從宏觀的角度看去，對(duì)

8

個(gè)公司所需貨物的數(shù)量分別乘以公司和港口的最短距離和載重

公司和港口的最短距離、載重單價(jià)都是定值，因此，載重費(fèi)用是固定不變的。即貨車可以送完貨沿原路返回港口。 方案，⑤~⑧逆時(shí)針?biāo)拓涀罴逊桨?。此結(jié)論也可以適用貨車可以掉頭的情況。加上上面兩個(gè)定理，數(shù)學(xué)模型與問題一幾乎相同，只是空載路徑不同。故同樣分為兩步驟：第一步分為兩種滿載方案：第1種為每個(gè)車次裝載1單位A和2單位C；第2種是每個(gè)車次裝載2個(gè)單位B。并使每一車次在同一公司卸貨。第二步滿足各公司對(duì)A需求量條件下，C與A搭配滿足載重相對(duì)最大化方法運(yùn)輸；第二批次個(gè)單位；第三批次運(yùn)輸剩下的貨物。

4：表4車輛 車次1231 4567892 101112

公司112334577225

貨物A,2CA,2CA,2CA,2CA,2CA,2CA,2CA,2CA,2C2B2B2B

時(shí)間（小時(shí)）0.68340.68340.91671.21671.21671.38341.18340.78340.78340.91670.91671.1834

運(yùn)費(fèi)89.689.6168268.8268.8324.8257.6123.2123.2168168257.6

各車工作時(shí)間（小時(shí)）7.28377.7838131415161718193 2021222324254 262728

667888888111，2448，4

2B2B2B2BA,CAAAAA,CA2BAA2B2B

0.91670.91670.78340.58340.58340.58340.58340.58340.58340.68340.68341.08331.38341.38341.51671.5833

168168123.256473838383875.260.8130.2220.4220.4192.8206

4.28386.9501總

4127.2

26.3014 運(yùn)費(fèi)最小是貨運(yùn)公司調(diào)度運(yùn)輸車的目標(biāo)，運(yùn)費(fèi)包括派車固定成本、從港口出車成本、載重費(fèi)用和空載費(fèi)用。由表

4

得知，第二問的總