中南大學(xué)-數(shù)學(xué)建模-lingo-matlab-優(yōu)化建模-數(shù)模培訓(xùn)-全國賽論文-貨運(yùn)公司的運(yùn)輸問題

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

2、，以公司需求與工作時間限制為約束條件，最小的運(yùn)輸費(fèi)用為目標(biāo)函數(shù)，建立一個線性規(guī)劃模型?？紤]到調(diào)度問題時，分兩種情況順時針與逆時針。此時，由于順時針與逆時針是處于非此即彼的對立關(guān)系，想到建立一個 0-1 規(guī)劃模型，并通過Lingo11.0版本的軟件進(jìn)行求解，得到了運(yùn)輸車次為28，出動運(yùn)輸車6輛，所以總費(fèi)用為 4817 元。問題二：此問題的條件由問題一的運(yùn)輸過程中不允許掉頭改為運(yùn)輸過程中可以掉頭，因此該問題的模型與算法與問題一如出一轍。此問題的特殊之處即為途中可以掉頭，因此在運(yùn)輸車空載時，可以對行走方向進(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次。問題三：當(dāng)各個公司間都有或者部分有道路直接相通時，此問題仍然可以使用前面建立的模型,只是運(yùn)輸路程中的最短路徑已經(jīng)發(fā)生了變化,故而此問題可以使用同一個改進(jìn)后的模型實現(xiàn).關(guān)鍵字：車輛路徑問題 線性規(guī)劃模型 0-1 規(guī)劃模型 一、問題重述貨運(yùn)公司需要為多個任務(wù)點(diǎn)提供服務(wù)，各個任務(wù)點(diǎn)位置已知，具有送貨需求，

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

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

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

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

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

9、量發(fā)揮其運(yùn)載最大能力時，有如下四種方式： （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公里小時，則行駛完整一圈的時間為1小時?？紤]到運(yùn)輸車的裝卸過程，假

10、設(shè)裝卸各一次，裝貨時間用15分鐘、卸車時間平均為10分鐘，則裝卸各一次后行駛完整一圈的時間共需1小時25分鐘。考慮全天工作不得超過8小時，則照此一輛運(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ù)）,從而解除了時間窗的約束.5.1.2模型建立根據(jù)8個公司和三種原材料的關(guān)系，構(gòu)造一個3行8列的矩陣，以行表示3種原材料、列表示8個公司?？紤]到運(yùn)輸車采用順時針或逆時針的問題，將矩陣分成以下兩種：（1）運(yùn)輸

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

12、1列的矩陣，以行表示8個公司、列表示從港口分別到各個公司的路程值。同理，考慮到運(yùn)輸車采用順時針或逆時針的問題，將矩陣分成以下兩種：（1）運(yùn)輸車采用順時針時，81矩陣表示為：，表示運(yùn)輸車采用順時針行駛從港口到j(luò)公司，行從上到下按照公司的順序依次排列（如圖2）；（2）運(yùn)輸車采用逆時針時，81矩陣表示為：，表示運(yùn)輸車采用逆時針行駛從港口到j(luò)公司，行從上到下按照公司的順序依次排列（如圖3）。10 圖2 矩陣 圖3 矩陣設(shè)運(yùn)費(fèi)最小為此問題的目標(biāo)函數(shù)F，綜上，可得到此問題的目標(biāo)函數(shù)：F=a+k10+620約束條件為：設(shè)5.1.2模型求解Step1通過分析各公司對原材料的需求量，可按照將每輛運(yùn)輸車最大的裝載

13、能力，簡化需處理的數(shù)據(jù)。根據(jù)每輛運(yùn)輸車最多裝載6噸，可得到每輛運(yùn)輸車的裝載方案：(a)1A+2C、 (b)2B、(c)6C、(d)B+3C。據(jù)此，逐個分析各個公司的需求量，將每個公司的需求進(jìn)行拆分，其中可以符合上述四種運(yùn)載方案的最短路徑方案則可以肯定為最優(yōu)解的一部分，因此這部分的數(shù)據(jù)不需要通過建立的模型再計算，從而使得需處理數(shù)據(jù)得到極大的簡化。例如公司：對A、B、C三種原材料需求量分別為：4、1、5。此數(shù)據(jù)可分為兩部分：2、0、4與2、1、1，前一部分按照裝載方案1A+2C通過兩次運(yùn)輸即可完成，后一部分無法套用上面的四種中的任意一種，因此公司仍需處理的數(shù)據(jù)為：2、1、1。由以上方法，可總結(jié)為下

14、表2表2公司編號調(diào)度方案次數(shù)方案21A+2C1A+2C31A+2C2B2B21A+2C1A+2C11A+2C21A+2C2B21B+3C2B31A+2C1A+2C2B12BStep2根據(jù)Step1，可以將原始各個公司對每種材料的需求量（如附表1）簡化為下表2各個公司對每種材料簡化后的需求量。表3 各個公司對每種材料簡化后的需求量公司編號各種材料的需求量（單位/天）ABC211010000210002010001511由此，只需將上表中的數(shù)據(jù)導(dǎo)入Lingo11.0軟件中，即可得出問題的最優(yōu)解了。根據(jù)結(jié)果可知簡化后的需求量的調(diào)配方案為：一次運(yùn)一單位的A和一單位的C到公司；一次運(yùn)一單位的B到公司和一

15、單位的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，出動運(yùn)輸車6輛，所以總費(fèi)用為 4817 元。5.2問題二問題二中的車輛可以掉頭， 但是這只會影響每輛車在運(yùn)行過程中空車運(yùn)行回港口的路費(fèi)，這時候的目標(biāo)函數(shù)F有所變化，這時候的F 的求解是這樣計算的:在每輛車完成了該車的裝載任務(wù)后，看所處的位置在何處，如果掉頭回港口更近的話，則掉頭，否則繼續(xù)前進(jìn)。在假設(shè)下，由

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