1、 題目：送貨問題 摘要本文深入研究了具有供求平衡，有序卸貨特點的運輸問題，建立數學模型求解最小運費，安排每輛車的最佳運載方案。在問題（一），行車路線是一個閉合回路，在受到卸貨順序限制的情況下，使每次運輸的費用最小，從而使總費用最小，應用線性規劃知識求得6輛車的工作時間分別為5.83、5.83、7.08、7.25、7.25、7.25小時，運輸的總費用為4875元，總共運了28次。問題（一）中，運輸車的路程為固定值，在問題（二），運輸車可以隨時掉頭，這樣運輸車的行車路線就不唯一了。而且運輸車可以為距離港口較遠的公司送小件，然后掉頭為距離港口較近的公司送大件。確定約束方程，列出目標函數，求得共派了4

2、輛車，各輛車的工作時間分別為6.3、6.67、6.54、7.04小時，運輸的總費用為4856.8元，總共運27次。在問題（三）中，增加了載重量為4噸和8噸二種類型的運輸車，使問題變得復雜。當空載距離大于公里時，選用載重量為4噸的運輸車較省錢，運輸車行駛的最遠距離是29公里，所以不選擇載重量為4噸的運輸車為公司送貨。選用載重量為6噸、8噸二種類型的運輸車為公司送貨，建立目標函數，約束條件，求得選擇一輛6噸的，二輛8噸的車為公司送貨，運輸車的工作時間分別為6.57、6.38、7.19小時，總費用為4409.2元，總共運21次，與前二種調度方案相比，更節省錢。關鍵字：線性規劃 卸貨順序 一 問題重述

3、某地區有8個公司(如圖一編號至)，某天某貨運公司要派車將各公司所需的三種原材料A,B,C從某港口(編號)分別運往各個公司。路線是唯一的雙向道路(如圖)。貨運公司現有一種載重 6噸的運輸車，派車有固定成本20元/輛，從港口出車有固定成本為10元/車次(車輛每出動一次為一車次)。每輛車平均需要用15分鐘的時間裝車，到每個公司卸車時間平均為10分鐘，運輸車平均速度為60公里小時(不考慮塞車現象)，每日工作不超過8小時。運輸車載重運費1.8元/噸公里，運輸車空載費用0.4元/公里。一個單位的原材料A,B,C分別毛重4噸、3噸、1噸，原材料不能拆分，為了安全，大小件同車時必須小件在上，大件在下。卸貨時必

4、須先卸小件，而且不允許卸下來的材料再裝上車，另外必須要滿足各公司當天的需求量(見表)。 問題： 1、貨運公司派出運輸車6輛，每輛車從港口出發(不定方向)后運輸途中不允許掉頭，應如何調度(每輛車的運載方案，運輸成本)使得運費最小。 2、每輛車在運輸途中可隨時掉頭，若要使得成本最小，貨運公司怎么安排車輛數？應如何調度？3、(1)如果有載重量為4噸、6噸、8噸三種運輸車，載重運費都是1.8元/噸公里，空載費用分別為0.2，0.4，0.7元/公里，其他費用一樣，又如何安排車輛數和調度方案？(2)當各個公司間都有或者部分有道路直接相通時，分析運輸調度的難度所在，給出你的解決問題的想法(可結合實際情況深入

5、分析)。 二 問題分析 運輸過程的最大特點是三種原材料的毛重不同，而且原材料不能拆分。大小件同車時必須小件在上，大件在下。卸貨時必須先卸小件，不允許卸下來的材料再裝上車，當卸下A時，車上沒有B和C，當卸下B時，車上沒有C。在問題一中，運輸途中不能掉頭，運輸車的行駛路線是一個閉合回路，總行程為固定值。運輸車可以為距離港口較近公司送小件，為距離港口較大公司送大件。在問題二中，運輸車可以隨時掉頭，運輸車可以為距離港口較遠的公司送小件，然后掉頭為距離港口較近的公司送大件。在問題三中，有三種運輸車，且空載費用不同，可以選擇適當類型的車降低費用。調度的目的是使運費最小，影響運費的因素有調度的車輛數、總出車

6、次數、每車次載的貨物、行車方向、卸貨地點，由于變量過多，不易求出目標函數的最優解。可以分二個階段求解，第一求出滿足當天公司需求量的車次；第二確定每車次裝載數量及卸貨地點。影響調度的約束條件有：每次運輸不能超過運輸車的載重量。 每日工作不超過8小時。 滿足公司當天需求。 大小件同車時，小件在上，而且要先卸小件。 運輸車從港口出來可以按順時針和逆時針二種方。三 模型假設道路足夠寬闊，不會發生塞車現象。 各運輸車相互獨立，互不影響。多輛運輸車可以同時在一個港口裝貨，同時在一個公司卸貨。各輛車最后一次運完貨物后回到港口。各公司優先級別相同，只要滿足當天需求量即可。 四 符號說明Pijk第i輛車第j次裝

7、載第k種原材料的數量單位Tij第i輛車第j次從港口出發又回到港口用的時間小時Mnk第n個公司所需要的第k種貨物量單位Qijnk第i輛車第j次在第n各公司卸載的k貨物的量單位Gk第k種原材料的重量噸D1n從港口出發到第n公司的順時針距離公里D2n從港口出發到第n公司的逆時針距離公里順時針距離：從港口出發按順時針方向到公司的距離。逆時針距離：從港口出發按逆時針方向到公司的距離。 五 模型的建立與求解運費包括派車固定成本、過港口固定成本、載重運費、空載運費。問題（1）:線性規劃約束條件 原材料A、B、C分別毛重4噸、3噸、1噸，且原材料不能拆分，而運輸車的載重量是6噸，所以A、B不可能同時在一輛車上

8、，在滿足公司當天需求量的條件下，一天最少要發27次車。 Gk 6 運輸車每日工作不超過8小時，所以每輛運貨車每天為公司送貨的累計工作時間應不大于8小時。 8 i=1、2、3、4、5、6 貨運公司每天為各公司送的貨要滿足各公司的需求量，即各車次（車輛每出動一次為一車次）為公司送的貨物的總和正好滿足公司當天需求。 QijnkMnk k=1,2,3 卸貨時必須先卸小件，而且不允許卸下來的材料再裝上車，運貨車在運輸途中不允許掉頭。由于運貨車載重量的限制，A、C可以組合裝車，B、C也可以組合裝車，但是A、B不能組合裝車。運輸車具有以下特點：當在n公司卸下A時，這時貨車是空車；當在n公司卸下B時，不能再為

9、后續公司運送小件C。運輸車的行駛路線是一個閉合回路。順時針行車時（用“”表示順時針行駛） 當在n公司卸下A時，約束方程為 Qijn3Qijnk=0 當在n公司卸下B時，約束方程為 Qijn2Qijnk=0 k=1或3逆時針行車時(用“”表示逆時針行駛) 1 當在n公司卸下A時，約束方程為 Qijn3Qijnk=0 2 當在n公司卸下B時，約束方程為 Qijn2Qijnk=0 k=1或3運輸車不允許掉頭，行駛路線是一個閉合回路，總行程為60公里。從港口出發，從不同方向到公司距離如下表公司行車方向D1n815242937454955D2n524536312315115目標函數分析：運費有派車固定成

10、本費、從港口出車固定成本、空載費用、載重費用幾部分組成。空載費用 運輸車的空載費用為0.4元公里。當在n公司把車上的貨物卸完時，記fn=1，否則記fn=0。設空載費用為Bij j 則Bij=0.460-min（D1n ，D2n）fn載重費用運輸車的載重費用為1.8元噸公里，由于運輸車不能掉頭，貨物只能按順時針或逆時針運至公司，設載重費用為Ei則 Eij= 1.8PijkGkmin（D1n ，D2n） 固定費用 固定費用有二部分組成，即派車固定成本費和從港口出車固定成本，派車固定成本20元/輛，從港口出車有固定成本為10元/車次(車輛每出動一次為一車次)，設每天共出車N次。 則固定費用為 10N

11、+20max（i）綜上所述：設運貨費用為Z，則目標函數為minZ=(Bij+ Eij)+ 10N+20max（i） Gk 6 8 i=1、2、3、4、5、6 QijnkMnk k=1,2,3 Qijn3Qijnk=0 （“”表示順時針行車） s.t. Qijn2Qijnk=0 k=1或3 Qijn3Qijnk=0 （“”表示逆時針行車） Qijn2Qijnk=0 k=1或3 Bij=0.460-min（D1n ，D2n）fn Eij= 1.8PijkGkmin（D1n ，D2n）運車方案的確定：運輸途中不能掉頭，運輸車的行駛路線是一個閉合回路，總行程為固定值。卸貨時必須先卸小件，而且不允許卸下

12、來的材料再裝上車，運輸車可以為距離港口較近公司送小件，為距離港口較遠公司送大件。運貨車載重量為6噸，A、C可以組合裝車，B、C也可以組合裝車，但是A、B不能組合裝車。運貨車應盡量裝滿。調度方案如下 注：“+” “-”分別表示運輸車按順時針、逆時針方向行駛。 公司車次 Ti（小時）運費(元)P11+A2C5.83696P12+2BP13-B-BP14-2BP21+A2C5.83505P22+B+BP23-A2CP24-AP31+A2C7.08802.4P32+ACP33-A2CP34-A2CP35-AP41+A2C7.251044P42+AP43-B-BP44+A2CP45-AP51+A2C7.

13、25966.2P52-ACP53-2BP54-A-2CP55-AP61+2B7.25843.4P62-2BP63-2BP64-A-CP65-3C總計費用 4857派車方案顯示了派車的數量、各車行駛方向、各車次裝貨數量、卸貨地點及在各地點卸貨的數量。有各車工作時間可以看出各車輛工作時間較長，勞動強度較大。問題（二）： 與問題（一）的不同之處是問題（二）中，運輸車在運輸途中可以隨時掉頭，這樣運輸車的行駛路線不再是一個閉合回路。卸貨時必須先卸小件，而且不允許卸下來的材料再裝上車，當卸下A時，車上沒有B和C，當卸下B時，車上沒有C。運輸車可以為較遠公司送小件，然后掉頭為較近公司送大件。線性規劃約束條件

14、 原材料A、B、C分別毛重4噸、3噸、1噸，且原材料不能拆分，而運輸車的載重量是6噸，所以A、B不可能同時在一輛車上，在滿足公司當天需求量的條件下，一天最少要發27次車。 Gk 6 運輸車每日工作不超過8小時，所以每輛運貨車每天為公司送貨的累計工作時間應不大于8小時。 8 i=1、2 貨運公司每天為各公司送的貨要滿足各公司的需求量，即各車次（車輛每出動一次為一車次）為公司送的貨物的總和正好滿足公司當天需求。 QijnkMnk k=1,2,3運輸車在運輸途中可以隨時掉頭，從港口到各公司的最短距離如下表81524292315115 使運費最小時，應按順時針行駛為公司送貨，按逆時針行駛為公司送貨。貨

15、車送完貨應掉頭沿原路返回港口。 為公司送貨（“”表示運輸車按順時針方向行駛） 當在n公司卸下A時，約束方程為 Qijn3Qijnk=0 （n=1、2、3、4） 當在n公司卸下B時，約束方程為 Qijn2Qijnk=0 k=1或3 （n=1、2、3、4） 為公司送貨（“”表示運輸車按逆時針方向行駛）1 當在n公司卸下A時，約束方程為 Qijn3Qijnk=0 （n=5、6、7、8）2 當在n公司卸下B時，約束方程為 Qijn2Qijnk=0 k=1或3 （n=5、6、7、8）目標函數分析運費有派車固定成本費、從港口出車固定成本、空載費用、載重費用幾部分組成。 空載費用 運輸車的空載費用為0.4元

16、公里。當在n公司把車上的貨物卸完時，記fn=1，否則記fn=0。為公司送貨時，貨車應掉頭沿原路返回 空載費用為 Bij=0.4D1n fn為公司送貨時，貨車應掉頭沿原路返回 空載費用為 Bij=0.4D2n fn以上二式合并為 Bij=0.4min（D1n，D2n）fn 載重費用運輸車的載重費用為1.8元噸公里，貨物按順時針或逆時針運至公司，設載重費用為Ei為公司送貨時，貨車按順時針方向行駛則 Eij= 1.8PijkGkD1n 為公司送貨時，貨車按逆時針方向行駛則Eij= 1.8PijkGkD2n以上二式合并為 Eij= 1.8PijkGkmin（D1n，D2n） 固定成本費 固定成本費有派

17、車固定成本費、從港口出車固定成本二部分組成。 固定成本費 10N+20max（i）綜上所述： 設運貨費用為Z，則目標函數為 minZ=(Bij+ Eij)+ 10N+20max（i） Gk 68 i=1、2QijnkMnk k=1,2,3Qijn3Qijnk=0 （n=1、2、3、4）Qijn2Qijnk=0 k=1或3 （n=1、2、3、4）Qijn3Qijnk=0 （n=5、6、7、8）Qijn2Qijnk=0 k=1或3 （n=5、6、7、8） Bij=0.4min（D1n，D2n）fnEij= 1.8PijkGkmin（D1n，D2n） 注：“+” “-”分別表示運輸車按順時針、逆時針

18、方向行駛。運車方案確定：卸貨時必須先卸小件，而且不允許卸下來的材料再裝上車，運貨車在運輸途中可以隨時掉頭，運輸車可以為距離港口較遠公司送小件，為距離港口較近公司送大件。運貨車載重量為6噸，A、C可以組合裝車，B、C也可以組合裝車，但是A、B不能組合裝車。運貨車應盡量裝滿。調度方案如下 注：“+” “-”分別表示運輸車按順時針、逆時針方向行駛。 公司車次Ti（小時）運費（元）P11+A2C6.31039P12+2BP13-B-BP14-2BP15+A2CP16+B+BP17-A2CP21-2C-A6.671327P22+A2CP23+ACP24-A2CP25-A2CP26-C-AP27+2BP3

19、1-AC6.541105P32-2BP33-A-2CP34-AP35-2BP36-2BP37+AP41+A2C7.041385.8P42+AP43-B-BP44+A2CP45-C-AP46+A2C總計費用 4856.8派車方案顯示了派車的數量、各車行駛方向、各車次裝貨數量、卸貨地點及在各地點卸貨的數量。與問題（一）中的調度方案相比較，各車工作時間較短，勞動強度較小，而且派車的數量減少了。問題（三）： 與問題（二）的不同之處是問題（三）中，運輸車增加了載重量為4噸和8噸的二種運輸車，這樣貨物的組合類型就增加了，運輸車可以同時運送A、B，而且還可以同時運送2單位的A原料。運輸車在運輸途中可以隨時掉

20、頭，卸貨時必須先卸小件，而且不允許卸下來的材料再裝上車，當卸下A時，車上沒有B和C，當卸下B時，車上沒有C。運輸車可以為較遠公司送小件，然后掉頭為較近公司送大件。線性規劃約束條件 運輸車在運輸途中可以隨時掉頭，從港口到各公司的最短距離如下表81524292315115 當為公司運送相等的貨物時，如果選用載重量為4噸和8噸的二種運輸車，二種運輸車的載重運費相等。載重量為4噸的運輸車比載重量為8噸的運輸車多了10元的過港費。載重量為4噸和8噸的運輸車的空載費用分別為0.4元公里、0.7元公里。 =即當空載距離大于公里時，選用載重量為4噸的運輸車較省錢，由上表可知運輸車行駛的最遠距離是29公里，所以

21、該題不選擇載重量為4噸的運輸車為公司送貨。 原材料A、B、C分別毛重4噸、3噸、1噸，且原材料不能拆分，運輸車的載重量是6噸、8噸，A與B，A與A都可以組合裝車，這是與問題二的不同之處。 Gk 8 運輸車每日工作不超過8小時，所以每輛運貨車每天為公司送貨的累計工作時間應不大于8小時。 8 i=1、2 貨運公司每天為各公司送的貨要滿足各公司的需求量，即各車次（車輛每出動一次為一車次）為公司送的貨物的總和正好滿足公司當天需求。 QijnkMnk k=1,2,3 使運費最小時，應按順時針行駛為公司送貨，按逆時針行駛為公司送貨。貨車送完貨應掉頭沿原路返回港口。 為公司送貨（“”表示運輸車按順時針方向行

22、駛） 當在n公司卸下A時，約束方程為 Qijn3Qijnk=0 k=1或2 （n=1、2、3、4） 當在n公司卸下B時，約束方程為 Qijn2Qijn3=0 （n=1、2、3、4） 為公司送貨（“”表示運輸車按逆時針方向行駛）3 當在n公司卸下A時，約束方程為 Qijn3Qijnk=0 k=1或2 （n=5、6、7、8）4 當在n公司卸下B時，約束方程為 Qijn2Qijn3=0 （n=5、6、7、8）目標函數分析運費有派車固定成本費、從港口出車固定成本、空載費用、載重費用幾部分組成。 空載費用 運輸車的空載費用為0.4元公里，0.7元公里。當在n公司把車上的貨物卸完時，記fn=1，否則記fn

23、=0。選擇載重量為6噸的運輸車時：為公司送貨時，貨車應掉頭沿原路返回 空載費用為 Bij=0.4D1n fn為公司送貨時，貨車應掉頭沿原路返回 空載費用為 Bij=0.4D2n fn以上二式合并為 Bij=0.4min（D1n，D2n）fn選擇載重量為8噸的運輸車時： Bij=0.7min（D1n，D2n）fn 載重費用運輸車的載重費用為1.8元噸公里，貨物按順時針或逆時針運至公司，設載重費用為Ei為公司送貨時，貨車按順時針方向行駛則 Eij= 1.8PijkGkD1n 為公司送貨時，貨車按逆時針方向行駛則Eij= 1.8PijkGkD2n以上二式合并為 Eij= 1.8PijkGkmin（D1n，D2n） 固定成本費 固定成本費有派車固定成本費、從港口出車固定成本二部分組成。 固定成本費 10N+20max（i）綜上所述： 設運貨費用為Z，則目標函數為 minZ=(Bij+ Eij)+ 10N+20max（i） Gk 8 8 i=1、2 QijnkMnk k=1,2,3Qijn3Qijnk=0 k=1或2 （n=1、2、3、4） s.t. Qijn2Qijn3=0 （n=1、2、3、4）Qijn3Qijnk=0