貨車公司對貨運車輛的調(diào)度問題

1、2008高教社杯全國大學(xué)生數(shù)學(xué)建模競賽承 諾 書我們仔細(xì)閱讀了中國大學(xué)生數(shù)學(xué)建模競賽的競賽規(guī)則.我們完全明白，在競賽開始后參賽隊員不能以任何方式（包括電話、電子郵件、網(wǎng)上咨詢等）與隊外的任何人（包括指導(dǎo)教師）研究、討論與賽題有關(guān)的問題。我們知道，抄襲別人的成果是違反競賽規(guī)則的, 如果引用別人的成果或其他公開的資料（包括網(wǎng)上查到的資料），必須按照規(guī)定的參考文獻(xiàn)的表述方式在正文引用處和參考文獻(xiàn)中明確列出。我們鄭重承諾，嚴(yán)格遵守競賽規(guī)則，以保證競賽的公正、公平性。如有違反競賽規(guī)則的行為，我們將受到嚴(yán)肅處理。我們參賽選擇的題號是（從A/B/C/D中選擇一項填寫）： 我們的參賽報名號為（如果賽區(qū)設(shè)置報名

2、號的話）： 所屬學(xué)校（請?zhí)顚懲暾娜?參賽隊員 (打印并簽名) ：1. 2. 3. 指導(dǎo)教師或指導(dǎo)教師組負(fù)責(zé)人 (打印并簽名)： 日期： 年 月 日賽區(qū)評閱編號（由賽區(qū)組委會評閱前進(jìn)行編號）：2008高教社杯全國大學(xué)生數(shù)學(xué)建模競賽編 號 專 用 頁賽區(qū)評閱編號（由賽區(qū)組委會評閱前進(jìn)行編號）：賽區(qū)評閱記錄（可供賽區(qū)評閱時使用）：評閱人評分備注全國統(tǒng)一編號（由賽區(qū)組委會送交全國前編號）：全國評閱編號（由全國組委會評閱前進(jìn)行編號）貨運公司對貨運車輛的調(diào)度問題摘要寫的非常好該題是一個車輛調(diào)度的最優(yōu)化問題，因此是一個數(shù)學(xué)規(guī)劃模型。問題一是在車型固定、車輛不能掉頭、遵循貨物不可拆分及卸貨順序的情況下

3、來進(jìn)行貨物運輸，通過參照運籌學(xué)的數(shù)學(xué)規(guī)劃模型理論，我們得出了在該情況下調(diào)用了6輛車，一共出車29次，得出最終運費為4886元，；問題二是在問題一的基礎(chǔ)上增添了車輛可以中途掉頭的條件，因此，卸空貨物后原路返回港口以減少空載運費。我們得出了在該情況下調(diào)用了4輛車，一共出車29次，最終運費為4488.4元。問題三是增添了貨車的類型下進(jìn)行思考，這是分兩種情況，第一種是在貨車途中不可掉頭的情況下進(jìn)行討論，則可參照問題一，可得調(diào)動了6噸、8噸的車，共出車23次，最終運費為4923.6元，。情況二是在貨車中途可掉頭，此時參照問題二，得出調(diào)用了6噸、8噸的車，共出車23次，最終運費為4548.8元。關(guān)鍵詞：運

4、輸費用 運輸時間 lingo 0-1規(guī)劃模型一、問題重述貨運公司對貨運車輛的調(diào)度問題 某地區(qū)有8個公司(如圖一編號至)，某天某貨運公司要派車將各公司所需的三種原材料A,B,C從某港口(編號)分別運往各個公司。路線是唯一的雙向道路(如圖)。貨運公司現(xiàn)有一種載重 6噸的運輸車，派車有固定成本20元/輛，從港口出車有固定成本為10元/車次(車輛每出動一次為一車次)。每輛車平均需要用15分鐘的時間裝車，到每個公司卸車時間平均為10分鐘，運輸車平均速度為60公里小時(不考慮塞車現(xiàn)象)，每日工作不超過8小時。運輸車載重運費1.8元/噸公里，運輸車空載費用0.4元/公里。一個單位的原材料A,B,C分別毛重4

5、噸、3噸、1噸，原材料不能拆分，為了安全，大小件同車時必須小件在上，大件在下。卸貨時必須先卸小件，而且不允許卸下來的材料再裝上車，另外必須要滿足各公司當(dāng)天的需求量(見表)。 問題： 1、貨運公司派出運輸車6輛，每輛車從港口出發(fā)(不定方向)后運輸途中不允許掉頭，應(yīng)如何調(diào)度(每輛車的運載方案，運輸成本)使得運費最小。 2、每輛車在運輸途中可隨時掉頭，若要使得成本最小，貨運公司怎么安排車輛數(shù)？應(yīng)如何調(diào)度？3、(1)如果有載重量為4噸、6噸、8噸三種運輸車，載重運費都是1.8元/噸公里，空載費用分別為0.2，0.4，0.7元/公里，其他費用一樣，又如何安排車輛數(shù)和調(diào)度方案？(2)當(dāng)各個公司間都有或者部

6、分有道路直接相通時，分析運輸調(diào)度的難度所在，給出你的解決問題的想法(可結(jié)合實際情況深入分析)。圖唯一的運輸路線圖和里程數(shù)公司材料A41231025B15012423C52424351 表各公司所需要的貨物量二、基本假設(shè)1. 貨車在運輸途中沒有拋錨。2. 工人的日工資固定的，不受上班時間的影響。3. 工人在裝完貨、卸完貨后能立即出發(fā)。4. 港口能滿足多車同時裝貨，無需排隊等待。三、符號說明符號意義單位a派車數(shù)輛b出車次數(shù)輛j公司每天對A貨的需求量噸j公司每天對B貨的需求量噸j公司每天對B貨的需求量噸第i趟車運到j(luò)公司的貨物A數(shù)噸第i趟車運到j(luò)公司的貨物B數(shù)噸第i趟車運到j(luò)公司的貨物C數(shù)噸第i趟車

7、運貨重量噸當(dāng)=1，代表第i趟車運載貨物A。當(dāng)=0，代表第i趟車不運載貨物A當(dāng)=1，代表第i趟車運載貨物B。當(dāng)=0，代表第i趟車不運載貨物B當(dāng)=1，代表第i趟車運載貨物C。當(dāng)=0，代表第i趟車不運載貨物C當(dāng)=1，代表第i趟車用4噸的貨車。當(dāng)=0，代表第i趟車不用4噸的貨車。當(dāng)=1，代表第i趟車用6噸的貨車。當(dāng)=0，代表第i趟車不用6噸的貨車。當(dāng)=1，代表第i趟車用8噸的貨車。當(dāng)=0，代表第i趟車不用8噸的貨車。第i趟車，貨車從港口出發(fā)到j(luò)公司的距離公里四、問題分析本題根據(jù)貨運公司所供車型噸位、所規(guī)定的運費、8個公司對三種原材料的需求量以及各公司之間路程關(guān)系，建立模型尋找最優(yōu)方案，使得在滿足各種限

8、制條件下運費最小化。三種原材料（重量不同）要求不能拆分，則三種貨物運送時只能按整數(shù)個單位進(jìn)行。放置順序應(yīng)滿足大小件同車時必須小件在上，大件在下。卸貨順序必須先卸小件，而且不允許卸下來的材料再裝上車，這樣限制了卸貨方式只有三種：在某一公司卸下全部貨物在不同公司卸下同種貨物在不同公司卸下不同貨物，需滿足小件在據(jù)港口近處的公司卸下，剩余貨物在距離遠(yuǎn)處卸下。由于每日每輛車8小時的工作時間約束，每輛車應(yīng)盡量滿足最大載貨量和充分利用工作時間。途中貨車是否可以掉頭按各個問題不同做了以下分析。問題一：由于車型固定，介于派車固定成本和出車固定成本，盡量減少出車次數(shù)，達(dá)到滿載的四種運輸方式：（a）6C、（b）B+

9、3C、（c）2B、（d）1A+2C。結(jié)合各公司所需減少裝載的貨物，并考慮到限制了運輸途中不可掉頭，則按各公司與港口間最短路程決定貨車方向：順時針方向往公司而公司應(yīng)逆針方向出車，由此建立0-1模型。問題二：與問題一不同僅在于途中可以掉頭，但為減少運費，不考慮將貨物往回運，即問題一的方案中當(dāng)貨車卸空貨物后原路返回港口，以較少空載路程和運送時間，可以增加每輛車出車次數(shù)，來達(dá)到降低運費。問題三：根據(jù)三種不同的貨車的載運量、載重費用、空載費用，分為能否掉頭兩種情況進(jìn)行討論， 運往某公司的出車方向與問題一、二相同，并滿足距離港口近的公司盡可能用大載運量貨車，遠(yuǎn)距離運送用小載運量貨車?？梢缘纛^的情況則讓貨車

10、原路返回。二問中假設(shè)各個公司間都有或者部分有道路直接相通，根據(jù)問一指定的車輛運載分配方案，并選取距離短的路線運載目的地。五、模型的建立與求解5.1 問題一模型建立與求解5.1.1 問題一模型的建立目標(biāo)函數(shù)分析：Min(所求的總費用)=總車輛的派車固定成本+出車固定成本+總運費約束條件分析：1） 貨車載重量約束：貨車載重量（6噸）所載A類貨物重量+ 所載B類貨物重量+ 所載C類貨物重量2） 各公司需求量約束：A類貨物需求量每趟去往該公司所載A類貨物重量之和B類貨物需求量每趟去往該公司所載B類貨物重量之和C類貨物需求量每趟去往該公司所載C類貨物重量之和根據(jù)以上問題分析與限制條件，可列出以下目標(biāo)函數(shù)

11、與方程組：5.1.2 問題一模型的求解運輸方案見附錄表格1，最終求得總運費為4886元，出車總次數(shù)為29次。5.1.3 問題一結(jié)果的分析及驗證求解結(jié)果表明每輛車每天的工作均滿足8小時時間限制，滿足各公司每日各類貨物的需求量，所求模型符合實際情況。5.2 問題二模型建立與求解5.2.1 問題二模型的建立在問題一的基礎(chǔ)上，卸空貨物后采用原路返回的方式，對問題進(jìn)行求解。目標(biāo)函數(shù)分析與條件約束分析與問題一一致。可列求解方程組如下：5.2.2 問題二模型的求解運輸方案見附錄表格2，最終求得總運費為4488.4元，出車總次數(shù)為29次。5.2.3 問題二結(jié)果的分析及驗證求解結(jié)果表明每輛車每天的工作均滿足8小

12、時時間限制，滿足各公司每日各類貨物的需求量，所求模型符合實際情況。5.3 問題三模型建立與求解 問題三模型的建立目標(biāo)函數(shù)分析：Min(所求的總費用)=總車輛的派車固定成本+出車固定成本+總運費約束條件分析：3） 貨車載重量約束：貨車載重量（分別為8、6、4噸）所載A類貨物重量+ 所載B類貨物重量+ 所載C類貨物重量4） 各公司需求量約束：A類貨物需求量每趟去往該公司所載A類貨物重量之和B類貨物需求量每趟去往該公司所載B類貨物重量之和C類貨物需求量每趟去往該公司所載C類貨物重量之和情況一（中途不可以掉頭） 情況二（中途可以掉頭）各個公司間都有或者部分有道路直接相通，根據(jù)問一指定的車輛運載分配方案

13、，并選取距離短的路線運載目的地。5.3.2 問題三模型的求解情況一：運輸方案見附錄表格3，最終求得總運費為4923.6元，出車總次數(shù)為26次。情況二：運輸方案見附錄表格4，最終求得總運費為4548.8元，出車總次數(shù)為26次。5.3.3 問題三結(jié)果的分析及驗證求解結(jié)果表明每輛車每天的工作均滿足8小時時間限制，滿足各公司每日各類貨物的需求量，但所求模型的總運費不滿足最優(yōu)化要求。六、模型的評價與推廣7.1 模型的評價問題一、二的模型比較符合實際的要求。但問題三的模型未能達(dá)到最優(yōu)7.2 模型的推廣可運用于上班的人數(shù)安排。七、參考文獻(xiàn)1 刁在筠等, 運籌學(xué)（第三版），高等教育出版社，2007年1月2 姜

14、啟源等，數(shù)學(xué)模型（第四版），高等教育出版社，2011年1月八、附錄 表一貨車編號行駛方向次數(shù)公司編號載貨方案載貨時間/每人每天運費/每人每天總運費/每天1111A+2C435597.848861211A+2C1311A+1C1411A 151，21B+1B1121A+2C4251157.21222B1322B1431A+2C1531A+2C1141A+2C4251270.21241A 1341A 1441B0552B0151A+2C4259700262B0362B0472B0571A+2C0171A+2C445445025，6，72C，3C，1C0381A+1C0481A 0581A 0181

15、A 3403010281A 0382B0481B貨車編號行駛方向次數(shù)公司編號載貨方案載貨時間/每人每天運費/每人每天總運費/每天1111A+2C448分1328.24488.41211A+2C1311A+1C1411A 151，21B+1B1621A+2C1722B1822B1931A+2C1131A+2C476分1540.21241A+2C1341A 1441A 1541B0652B0151A+2C413分12460262B0362B0472B0571A+2C0671A+2C075，6，72C，3C，1C0181A+1C2453740281A 0381A 0481A 0581A 0682B0

16、781B表二 表三貨車編號行駛方向次數(shù)公司編號載貨方案運費/每人每天總運費/每天111A+B+C1186.34923.6121A+4C1312A142、32A1522B+2C113A+4C1211.61242A0382A0482A058A+B+C017A+B+C792.5027A+B+C035A+B+C1122B10601222B134A+2C0482B056、76C0162B673.20000262B035B+3C 表四貨車編號行駛方向次數(shù)公司編號載貨方案運費/每人每天總運費/每天111A+B+C1064.54548.8121A+4C1312A142、32A1522B+2C113A+4C10

17、96.81242A0382A0482A058A+B+C017A+B+C729.5027A+B+C035A+B+C1122B1014.41222B134A+2C0482B056、76C0162B643.60262B035B+3C問題一1車：20+5*10+27*1.8*8+0.4*4*52+7*1.8*3+45*0.4= 597.80002車：20+5*10+18*1.8*15+0.4*3*45+12*24*1.8+2*0.4*36= 1.1572e+0033車：20+5*10+17*1.8*29+0.4*4*31+23*6*1.8+37*0.4= 1.2702e+0034車：20+5*10+6

18、*1.8*23+0.4*37+12*15*1.8+45*0.4*2+11*12*1.8+0.4*2*49=970.00005車：20+5*10+13*5*1.8+3*0.4*55+6*11*1.8+0.4*49+6*11*1.8+5*4*1.8+2*8*1.8+0.4*37= 589.80006車：20+4*10+17*5*1.8+4*0.4*55=301總運費：4886問題二1車：20+9*10+27*1.8*8+0.4*4*8+7*1.8*3+15*0.4+18*1.8*15+0.4*3*15+6*24*1.8+0.4*24= 1.3282e+0032車：20+6*10+6*24*1.8+

19、0.4*24+17*1.8*29+0.4*4*29+23*6*1.8+23*0.4= 1.5402e+0033車：20+7*10+6*1.8*23+0.4*23+12*15*1.8+15*0.4*2+11*12*1.8+0.4*2*11+6*11*1.8+0.4*11+6*11*1.8+5*4*1.8+2*8*1.8+0.4*23= 12464車：20+7*10+30*5*1.8+5*0.4*7= 374總運費：4.4884e+003（1車是1到9共448分，2車是10到15共476分，3車是16到22共413分，4車是23到29共245分）問題三情況一（不掉頭）1車8噸：20+5*10+24*8*1.8+52*0.7*3+15*16*1.8+24*4*1.8+36*0.7+45*0.7= 1.1863e+0032車8噸：20+5*10+24*8*1.8+36*0.7+8*29*1.8+31*0.7+8*5*1.8*3+55*0.7*3= 1.2116e+003