國(guó)家級(jí)精品課程-中南大學(xué)-數(shù)學(xué)建模-lingo-matlab-優(yōu)化建模-數(shù)模培訓(xùn)-全國(guó)賽論文-貨運(yùn)公司的運(yùn)輸問(wèn)題2

1、貨運(yùn)公司的運(yùn)輸問(wèn)題摘要為了節(jié)約成本，提高貨運(yùn)公司的運(yùn)輸效率，本文對(duì)集送貨可拆分的車輛路徑問(wèn)題進(jìn)行了研究。該問(wèn)題允許一個(gè)任務(wù)點(diǎn)被訪問(wèn)多次，也允許同一車輛訪問(wèn)同一任務(wù)點(diǎn)多于一次。針對(duì)此問(wèn)題的特點(diǎn)，利用優(yōu)化思想建立了線性規(guī)劃模型、0-1 規(guī)劃模型和最優(yōu)化模型，解決了運(yùn)輸?shù)淖钚∵\(yùn)費(fèi)問(wèn)題、每輛運(yùn)輸車的運(yùn)輸方案問(wèn)題，從而使運(yùn)輸滿足各公司當(dāng)天的需求量。問(wèn)題一：由問(wèn)題一中的貨運(yùn)問(wèn)題可運(yùn)用線性規(guī)劃模型，在卸貨順序約束下，對(duì)每次出車求局部最小費(fèi)用且盡可能滿載，最后得出全局解。分析問(wèn)題可知，費(fèi)用最少問(wèn)題與出車次數(shù)、調(diào)度安排、運(yùn)輸成本均有關(guān)系，由公司與原材料的關(guān)系、港口與公司間路程的關(guān)系及原材料的重量分別建立3個(gè)矩陣

2、，以公司需求與工作時(shí)間限制為約束條件，最小的運(yùn)輸費(fèi)用為目標(biāo)函數(shù)，建立一個(gè)線性規(guī)劃模型?？紤]到調(diào)度問(wèn)題時(shí)，分兩種情況順時(shí)針與逆時(shí)針。此時(shí)，由于順時(shí)針與逆時(shí)針是處于非此即彼的對(duì)立關(guān)系，想到建立一個(gè) 0-1 規(guī)劃模型，并通過(guò)lingo11.0版本的軟件進(jìn)行求解，得到了運(yùn)輸車次為28，出動(dòng)運(yùn)輸車6輛，所以總費(fèi)用為 4817 元。問(wèn)題二：此問(wèn)題的條件由問(wèn)題一的運(yùn)輸過(guò)程中不允許掉頭改為運(yùn)輸過(guò)程中可以掉頭，因此該問(wèn)題的模型與算法與問(wèn)題一如出一轍。此問(wèn)題的特殊之處即為途中可以掉頭，因此在運(yùn)輸車空載時(shí)，可以對(duì)行走方向進(jìn)行選擇，掉頭回到港口或者繼續(xù)原方向行駛。由于題中路程唯一，車速不變，可以得出如下定理：一、車輛

3、載重行程是各公司到港口最短路，且載重費(fèi)用固定不變；二、車輛當(dāng)且僅當(dāng)運(yùn)完最后一件貨才調(diào)頭；推論：運(yùn)載里程與空載里程相同，且每次出車均不繞圈工作。我們以每次運(yùn)輸量為決策變量，最小總費(fèi)用為目標(biāo)，建立整數(shù)線性規(guī)劃模型，使用lingo軟件編程求解最小運(yùn)費(fèi)及運(yùn)次方案，可以求得總費(fèi)用4680.2元，總運(yùn)次28次。問(wèn)題三：當(dāng)各個(gè)公司間都有或者部分有道路直接相通時(shí)，此問(wèn)題仍然可以使用前面建立的模型,只是運(yùn)輸路程中的最短路徑已經(jīng)發(fā)生了變化,故而此問(wèn)題可以使用同一個(gè)改進(jìn)后的模型實(shí)現(xiàn).關(guān)鍵字：車輛路徑問(wèn)題 線性規(guī)劃模型 0-1 規(guī)劃模型 一、問(wèn)題重述貨運(yùn)公司需要為多個(gè)任務(wù)點(diǎn)提供服務(wù)，各個(gè)任務(wù)點(diǎn)位置已知，具有送貨需求，

4、且需求量可以超過(guò)車輛容量，車輛從貨運(yùn)公司出發(fā)，載運(yùn)一定的貨物到達(dá)任務(wù)點(diǎn)，采用先卸小件、后卸大件的方式完成任務(wù)，且不得將已卸的貨物裝車，車內(nèi)貨物可以根據(jù)裝卸貨物的實(shí)際情況進(jìn)行很好的位置調(diào)整，或者能夠滿足裝卸貨物的要求，任務(wù)點(diǎn)的送貨需求量可以拆分，由不同車輛或同一車輛多次完成，所有車輛保證途中不得超載，合理安排車輛的行駛路線，在行駛途中可調(diào)頭和不可調(diào)頭兩種情況下，使得運(yùn)費(fèi)之和最小。分析當(dāng)各個(gè)公司間都有或者部分有道路直接相通時(shí)，運(yùn)輸調(diào)度的的難度及解決的辦法。所需要的具體數(shù)據(jù)圖如下圖1、圖2：圖1 唯一的運(yùn)輸路線圖和里程數(shù)圖2 各個(gè)公司對(duì)每種材料的需求量（單位/天）公司編號(hào)各種材料的需求量（單位/天）

5、abc415152204312124043225531二、問(wèn)題分析由題意可知，目的就是為了建立一種模型，解決運(yùn)輸?shù)淖钚∵\(yùn)費(fèi)問(wèn)題，每輛運(yùn)輸車的運(yùn)輸方案問(wèn)題，從而使運(yùn)輸滿足各公司當(dāng)天的需求量。2.1問(wèn)題1的分析問(wèn)題一中，將貨運(yùn)問(wèn)題轉(zhuǎn)化為線性規(guī)劃模型，題中給出6輛可用的運(yùn)輸車，考慮到每輛車只能裝載6噸重的貨物，并優(yōu)先考慮發(fā)揮每輛運(yùn)輸車最大的裝載能力，可得出每輛車的裝載方案有以下四種：6個(gè)c、2個(gè)b、1個(gè)a 2個(gè)c、1個(gè)b 3個(gè)c。由此，根據(jù)8個(gè)公司對(duì)三種原材料的每日需求量，即可建立一個(gè)線性規(guī)劃模型。此外，還要考慮運(yùn)輸車的調(diào)度問(wèn)題，由于出車方向不定，分為逆時(shí)針和順時(shí)針兩種情況，而且這兩種情況是非此即彼

6、的對(duì)立關(guān)系，這屬于 0-1 規(guī)劃問(wèn)題。我們令p表示采用順時(shí)針運(yùn)輸?shù)那闆r，令q表示采用逆時(shí)針運(yùn)輸?shù)那闆r。再結(jié)合題目中給出的其他相關(guān)數(shù)據(jù)，即可求得最優(yōu)解。2.2問(wèn)題2的分析問(wèn)題二中的解決方法和第一問(wèn)中的解決方法是類似的，不過(guò)由于這時(shí)候運(yùn)輸車可以掉頭，故可以減少由于運(yùn)輸車在途中空載的路程。根據(jù)題中路程唯一、車速不變的條件，及卸貨順序約束，車容量約束，公司需求約束，我們以每次運(yùn)輸量為決策變量，最小總費(fèi)用為目標(biāo)，建立混合整數(shù)線性規(guī)劃模型，使用lingo軟件編程求解最小運(yùn)費(fèi)及運(yùn)次方案2.3問(wèn)題3的分析問(wèn)題三中，當(dāng)各個(gè)公司間都有或者部分有道路直接相通時(shí)，此問(wèn)題仍然可以使用前面建立的模型,只是運(yùn)輸路程中的最短

7、路徑已經(jīng)發(fā)生了變化,故而此問(wèn)題可以使用同一個(gè)改進(jìn)后的模型實(shí)現(xiàn).三、模型假設(shè)1. 假設(shè)貨運(yùn)公司都是先考慮如何安排運(yùn)輸方式以減少經(jīng)費(fèi)支出，再考慮節(jié)省人力和出車次數(shù)最少的情況；2. 假設(shè)運(yùn)輸車行駛過(guò)程中不考慮塞車拋錨現(xiàn)象，運(yùn)輸過(guò)程中所有路況相同，以保證每輛車每天可以達(dá)到最大的作業(yè)時(shí)間；四、符號(hào)說(shuō)明 =(e，f，g)：一單位a、b、c原材料的凈重量； ：第j個(gè)公司對(duì)第i種原材料的總的需求量；m ：運(yùn)輸車采用順時(shí)針運(yùn)輸?shù)拇螖?shù)； n ：運(yùn)輸車采用逆時(shí)針運(yùn)輸?shù)拇螖?shù)；k ：總車次； : x次中某一次順時(shí)針運(yùn)貨方案； ：y次中某一次逆時(shí)針運(yùn)貨方案； p=1：表示車采用順時(shí)針運(yùn)輸；p=0：表示車不采用順時(shí)針運(yùn)輸；

8、 q=1：表示采用逆時(shí)針運(yùn)輸；q=0：表示第 i 輛車不采用逆時(shí)針運(yùn)輸； t ：運(yùn)輸車在第t公司處全部卸完貨物； a ：載重運(yùn)費(fèi) b ：空載運(yùn)費(fèi) c ：運(yùn)輸車容量； s ：總路程；（另外有些變量為局部變量，將在該符號(hào)具體的位置予以說(shuō)明）五、模型的建立與求解5.1問(wèn)題一首先，建立求解出滿足每個(gè)公司的需求的線性規(guī)劃模型，在卸貨順序,車次總數(shù),每次載貨量等的約束下，對(duì)每次出車求局部最小費(fèi)用且盡可能滿載，最后得出全局解。5.1.1模型準(zhǔn)備時(shí)間窗轉(zhuǎn)換為車次約束分析因?yàn)槊枯v運(yùn)輸車有八小時(shí)的工作時(shí)間限制,此處因?yàn)橹豢紤]總費(fèi)用最小,所以計(jì)劃把時(shí)間窗的約束轉(zhuǎn)換成車次使用次數(shù).以下將通過(guò)對(duì)貨物總量的當(dāng)考慮運(yùn)輸車盡

9、量發(fā)揮其運(yùn)載最大能力時(shí)，有如下四種方式： （a）1a+2c、（b）2b、（c）6c、（d）b+3c。我們分別設(shè)這四種方式需要調(diào)度的次數(shù)為 q1、q2、q3、q4，這樣我們就可以建立如下數(shù)學(xué)模型: min s=q1+q2+q3+q4 s.t. q1=18 2q2+q4=18 2q1+6q3+3q4=26 q1、q2、q3、q4>=0用lingo 進(jìn)行求解可以得到 s=27，q1=18，q2=9，q3=0，q4=0。即可得理想的總出車次數(shù)為27次。下面運(yùn)算出車次數(shù)的最大值。從港口出發(fā)行駛完整的一圈的路程為60公里，運(yùn)輸車平均速度為60公里小時(shí)，則行駛完整一圈的時(shí)間為1小時(shí)?？紤]到運(yùn)輸車的裝卸

10、過(guò)程，假設(shè)裝卸各一次，裝貨時(shí)間用15分鐘、卸車時(shí)間平均為10分鐘，則裝卸各一次后行駛完整一圈的時(shí)間共需1小時(shí)25分鐘?？紤]全天工作不得超過(guò)8小時(shí)，則照此一輛運(yùn)輸車最多一天行駛5次。由于考慮總費(fèi)用最少，所以不可能讓運(yùn)輸車空載行駛完整的一圈，每輛運(yùn)輸車行駛途中至少要卸一次貨。綜上，一輛運(yùn)輸車在一天內(nèi)，最多行駛5次。港口處共有6輛運(yùn)輸車，因此，一天內(nèi)，港口發(fā)車次數(shù)最大為30。綜上可得：（m+n為發(fā)車總次數(shù)）,從而解除了時(shí)間窗的約束.5.1.2模型建立根據(jù)8個(gè)公司和三種原材料的關(guān)系，構(gòu)造一個(gè)3行8列的矩陣，以行表示3種原材料、列表示8個(gè)公司?？紤]到運(yùn)輸車采用順時(shí)針或逆時(shí)針的問(wèn)題，將矩陣分成以下兩種：（

11、1）運(yùn)輸車采用順時(shí)針時(shí)，3×8矩陣表示為：（其中i表示第i種原材料、j表示第j個(gè)公司、m表示運(yùn)輸車采用順時(shí)針運(yùn)輸?shù)拇螖?shù)），列從左到右按照公司的順序依次排列；（如圖1）（2）運(yùn)輸車采用逆時(shí)針時(shí)，3×8矩陣表示為：（其中i表示第i種原材料、j表示第j個(gè)公司、n表示運(yùn)輸車采用逆時(shí)針運(yùn)輸?shù)拇螖?shù)），列從左到右按照公司的順序依次排列（如圖1）。該3×8矩陣中其中的一個(gè)數(shù)字表示順時(shí)針運(yùn)輸?shù)牡趚次在第j個(gè)公司卸載了第i種原材料。例如下圖中表示某一運(yùn)輸車在公司處卸下1單位c材料，在公司處卸下2單位c材料、1單位b材料，之后運(yùn)輸全部卸完貨物，之后空載行駛回港口。 abc 例： 圖1

12、、矩陣根據(jù)港口到8個(gè)公司的路程，構(gòu)造一個(gè)8行1列的矩陣，以行表示8個(gè)公司、列表示從港口分別到各個(gè)公司的路程值。同理，考慮到運(yùn)輸車采用順時(shí)針或逆時(shí)針的問(wèn)題，將矩陣分成以下兩種：（1）運(yùn)輸車采用順時(shí)針時(shí)，8×1矩陣表示為：，表示運(yùn)輸車采用順時(shí)針行駛從港口到j(luò)公司，行從上到下按照公司的順序依次排列（如圖2）；（2）運(yùn)輸車采用逆時(shí)針時(shí)，8×1矩陣表示為：，表示運(yùn)輸車采用逆時(shí)針行駛從港口到j(luò)公司，行從上到下按照公司的順序依次排列（如圖3）。10 圖2 矩陣 圖3 矩陣設(shè)運(yùn)費(fèi)最小為此問(wèn)題的目標(biāo)函數(shù)f，綜上，可得到此問(wèn)題的目標(biāo)函數(shù)：f=a×+k×10+6×2

13、0約束條件為：設(shè)5.1.2模型求解step1通過(guò)分析各公司對(duì)原材料的需求量，可按照將每輛運(yùn)輸車最大的裝載能力，簡(jiǎn)化需處理的數(shù)據(jù)。根據(jù)每輛運(yùn)輸車最多裝載6噸，可得到每輛運(yùn)輸車的裝載方案：(a)1a+2c、 (b)2b、(c)6c、(d)b+3c。據(jù)此，逐個(gè)分析各個(gè)公司的需求量，將每個(gè)公司的需求進(jìn)行拆分，其中可以符合上述四種運(yùn)載方案的最短路徑方案則可以肯定為最優(yōu)解的一部分，因此這部分的數(shù)據(jù)不需要通過(guò)建立的模型再計(jì)算，從而使得需處理數(shù)據(jù)得到極大的簡(jiǎn)化。例如公司：對(duì)a、b、c三種原材料需求量分別為：4、1、5。此數(shù)據(jù)可分為兩部分：2、0、4與2、1、1，前一部分按照裝載方案1a+2c通過(guò)兩次運(yùn)輸即可完

14、成，后一部分無(wú)法套用上面的四種中的任意一種，因此公司仍需處理的數(shù)據(jù)為：2、1、1。由以上方法，可總結(jié)為下表2表2公司編號(hào)調(diào)度方案次數(shù)方案21a+2c1a+2c31a+2c2b2b21a+2c1a+2c11a+2c21a+2c2b21b+3c2b31a+2c1a+2c2b12bstep2根據(jù)step1，可以將原始各個(gè)公司對(duì)每種材料的需求量（如附表1）簡(jiǎn)化為下表2各個(gè)公司對(duì)每種材料簡(jiǎn)化后的需求量。表3 各個(gè)公司對(duì)每種材料簡(jiǎn)化后的需求量公司編號(hào)各種材料的需求量（單位/天）abc211010000210002010001511由此，只需將上表中的數(shù)據(jù)導(dǎo)入lingo11.0軟件中，即可得出問(wèn)題的最優(yōu)解了

15、。根據(jù)結(jié)果可知簡(jiǎn)化后的需求量的調(diào)配方案為：一次運(yùn)一單位的a和一單位的c到公司；一次運(yùn)一單位的b到公司和一單位的b到公司；兩次運(yùn)一單位的b到公司；一次運(yùn)一單位的b到公司和公司；四次運(yùn)一單位的a到公司；一次運(yùn)一單位的a和一單位的c到公司；一次運(yùn)一單位的c到公司，三單位的c到公司，二單位的c到公司。再加上上面求出的局部調(diào)配方案可以得出總的調(diào)配方案.結(jié)論：根據(jù)lingo11.0軟件，可得運(yùn)輸車次為28，出動(dòng)運(yùn)輸車6輛，所以總費(fèi)用為 4817 元。5.2問(wèn)題二問(wèn)題二中的車輛可以掉頭， 但是這只會(huì)影響每輛車在運(yùn)行過(guò)程中空車運(yùn)行回港口的路費(fèi)，這時(shí)候的目標(biāo)函數(shù)f有所變化，這時(shí)候的f 的求解是這樣計(jì)算的:在每輛

16、車完成了該車的裝載任務(wù)后，看所處的位置在何處，如果掉頭回港口更近的話，則掉頭，否則繼續(xù)前進(jìn)。在假設(shè)下，由于題中路程唯一，車速不變，可以得出如下兩點(diǎn)：(1)車輛載重行程是各公司到港口最短路，且載重費(fèi)用固定不變；(2)車輛當(dāng)且僅當(dāng)運(yùn)完最后一件貨才調(diào)頭；推論：運(yùn)載里程與空載里程相同，且每次出車均不繞圈工作。以所有定理為基礎(chǔ)，加入卸貨順序約束，車容量約束，公司需求約束，以每次運(yùn)輸量為決策變量，最小總費(fèi)用為目標(biāo)，建立混合動(dòng)態(tài)規(guī)劃模型，使用lingo軟件編程求解最小運(yùn)費(fèi)及運(yùn)次方案，可以求得總費(fèi)用4680.2元，總運(yùn)次28次。5.3問(wèn)題三當(dāng)各個(gè)公司間都有或者部分有道路直接相通時(shí)，此問(wèn)題仍然可以使用前面建立的模型,只是運(yùn)輸路程中的最短路徑已經(jīng)發(fā)生了變化,所以需要更改表示路程的矩陣,而且這些矩陣的數(shù)目非常多,會(huì)因?yàn)檫\(yùn)輸貨物的量而變化,此外,運(yùn)輸貨物的矩陣中只體現(xiàn)了順時(shí)針或者逆時(shí)針也不可用,就是編號(hào)j的順序號(hào)會(huì)因?yàn)榫唧w的調(diào)運(yùn)方案改變,所以這就是一個(gè)難點(diǎn),尤其其中的數(shù)據(jù)處理和矩陣編排.六、模型評(píng)價(jià)優(yōu)點(diǎn)：1，此模型通過(guò)優(yōu)化后，運(yùn)算簡(jiǎn)便、直觀，易于理解。2.此模型易于推廣,對(duì)于時(shí)間窗,單類型貨運(yùn)車,多種貨物,不同的運(yùn)輸路徑等特點(diǎn)只需要在模型里面更改相應(yīng)的數(shù)據(jù)的約束條件即可使用.缺點(diǎn)：1.