運(yùn)輸配送貨物的行使路線問題論文

1、運(yùn)輸問題摘要本文主要研究了配送貨物的行使路線問題。根據(jù)題目要求,采用Fleury算法,建立01型整數(shù)規(guī)劃模型，并利用lingo，求出了最短行使路線和裝配方案，使得運(yùn)輸公司運(yùn)貨的總費(fèi)用最少。針對問題一，本文將運(yùn)送路線看作是10個(gè)客戶點(diǎn)作為頂點(diǎn)的有向的網(wǎng)絡(luò)圖，做出賦權(quán)鄰接矩陣，采用Dijkstra算法思想，利用lingo編程,求出從客戶2到客戶10最短的行使路線，最短行使路線為：，路程為85公里。針對問題二，要求設(shè)計(jì)貨車從提貨點(diǎn)到送貨點(diǎn)再返回提貨點(diǎn)的最短路線。本文采用Fleury算法思想，根據(jù)不同的權(quán)值客戶與客戶之間的距離，形成Euler回路，建立線性規(guī)劃模型，利用lingo, 求出有最小權(quán)的Ha

2、milton圈，即最短的行駛路線。最短的行使路線為：路程為225公里。針對問題三，本文首先從每輛車的容量與各個(gè)客戶的需求量之間的關(guān)系考慮，得出每輛車的載貨量在36至50之間，進(jìn)一步分析得出兩種情況：1、兩輛車分別裝5個(gè)和4個(gè)客戶的貨物；2、兩輛車分別裝6個(gè)和3個(gè)客戶的貨物。然后分別對以上兩種情況進(jìn)行討論，分別以其中一輛車行使的最小路程為目標(biāo)函數(shù)，以 每個(gè)客戶必須有車到達(dá)、車的裝載容量和附加變量防止構(gòu)成內(nèi)圈為約束條件，建立01線性規(guī)劃模型，利用lingo，通過比擬優(yōu)化，得出最正確的配送方案如下表：車號(hào)行使路線路徑長度公里總路徑長度公里負(fù)責(zé)的客戶1號(hào)車135 2904,5,8,9,102號(hào)車155

3、 2,3,6,7針對問題四，我們以總運(yùn)費(fèi)最小為目標(biāo)函數(shù)，約束條件和問題三的類似，建立0-1型整數(shù)規(guī)劃模型。運(yùn)用lingo求得當(dāng)有4輛車運(yùn)送貨物時(shí)總費(fèi)用最小，為645元。具體運(yùn)輸方式為：； ；關(guān)鍵詞：0-1型整數(shù)規(guī)劃 Fleury算法 Lingo一、問題重述某運(yùn)輸公司為10個(gè)客戶配送貨物，假定提貨點(diǎn)就在客戶1所在的位置，從第i個(gè)客戶到第j個(gè)客戶的路線距離單位公里用下面矩陣中的位置上的數(shù)表示其中表示兩個(gè)客戶之間無直接的路線到達(dá)。運(yùn)送員在給第二個(gè)客戶卸貨完成的時(shí)候，臨時(shí)接到新的調(diào)度通知，讓他先給客戶10送貨，送給客戶10的貨已在運(yùn)送員的車上，請幫運(yùn)送員設(shè)計(jì)一個(gè)到客戶10的盡可能短的行使路線假定上述矩

4、陣中給出了所有可能的路線選擇。現(xiàn)運(yùn)輸公司派了一輛大的貨車為這10個(gè)客戶配送貨物，假定這輛貨車一次能裝滿10個(gè)客戶所需要的全部貨物，請問貨車從提貨點(diǎn)出發(fā)給10個(gè)客戶配送完貨物后再回到提貨點(diǎn)所行使的盡可能短的行使路線？對所設(shè)計(jì)的算法進(jìn)行分析。現(xiàn)因資源緊張，運(yùn)輸公司沒有大貨車可以使用，改用兩輛小的貨車配送貨物。每輛小貨車的容量為50個(gè)單位，每個(gè)客戶所需要的貨物量分別為8，13，6，9，7，15，10，5，12，9個(gè)單位，請問兩輛小貨車應(yīng)該分別給那幾個(gè)客戶配送貨物以及行使怎樣的路線使它們從提貨點(diǎn)出發(fā)最后回到提貨點(diǎn)所行使的距離之和盡可能短？對所設(shè)計(jì)的算法進(jìn)行分析。如果改用更小容量的車，每車容量為25個(gè)單

5、位，但用車數(shù)量不限，每個(gè)客戶所需要的貨物量同第3問，并假設(shè)每出一輛車的出車費(fèi)為100元，運(yùn)貨的價(jià)格為1元/公里不考慮空車返回的費(fèi)用，請問如何安排車輛才能使得運(yùn)輸公司運(yùn)貨的總費(fèi)用最??？二、問題分析問題一的分析題目要求設(shè)計(jì)一個(gè)盡可能短的行路線，使運(yùn)送員在給第2個(gè)客戶卸貨完成的時(shí)候讓他先給客戶10送貨。從客戶與客戶之間的距離矩陣可以發(fā)現(xiàn)客戶2到客戶10無直接的路線到達(dá)，于是本文將運(yùn)送路線看做是10個(gè)客戶點(diǎn)作為頂點(diǎn)的有向的網(wǎng)絡(luò)圖，然后編寫程序，利用lingo,求出最短的行使路線。問題二的分析題目要求設(shè)計(jì)貨車從提貨點(diǎn)1出發(fā)給10個(gè)客戶配送完貨物后再回到提貨點(diǎn)盡可能短的行使路線。這個(gè)問題與旅行商問題類似，

6、于是，本文將路線轉(zhuǎn)化為Hamilton圈，根據(jù)不同的權(quán)值客戶與客戶之間的距離，利用lingo, 求出有最小權(quán)的Hamilton圈，即最短的行駛路線。 對于問題三，我們將貨物分成兩種情況進(jìn)行分析。第一種情況：兩輛車中一輛車裝載4個(gè)客戶的貨物，另外一輛車裝載5個(gè)客戶的貨物。第二種情況：兩輛車中一輛車裝載3個(gè)客戶的貨物，另外一輛車裝載6個(gè)客戶的貨物。但是每輛車貨物的容量小于50大于36，我們將每輛車的容量作為約束條件。每個(gè)客戶點(diǎn)總會(huì)有一輛車進(jìn)入，然后再離開，我們對這個(gè)問題采用01規(guī)劃模型進(jìn)行運(yùn)算。 將添加一種在原模型上附加充分的約束條件以防止產(chǎn)生子巡回的方法，把額外變量附加到問題中?？梢园堰@些變量看

7、作是連續(xù)的雖然這些變量在最優(yōu)解中取普通的整數(shù)值?，F(xiàn)在附加下面形式的約束條件：將其中一輛車行使的最小路程為目標(biāo)函數(shù)，建立線性規(guī)劃模型。2.4問題四的分析 對于問題四，要使總費(fèi)用最低，必須使出車費(fèi)與運(yùn)費(fèi)的和最少。由于車輛的個(gè)數(shù)不限，我們首先假設(shè)用k輛車來運(yùn)送貨物，又根據(jù)每輛車最多可運(yùn)25個(gè)單位的貨物，所以至少4輛車運(yùn)送貨物。又因?yàn)椴豢紤]空車輛返回時(shí)的費(fèi)用，故只需考慮運(yùn)輸貨物時(shí)的路程最短。我們建立01型整數(shù)規(guī)劃模型，將最小費(fèi)用作為目標(biāo)函數(shù)，運(yùn)用lingo求得最優(yōu)解，得出最正確的配送方案。三、問題假設(shè)1、假設(shè)提貨點(diǎn)就在客戶1所在的位置，客戶1所需的貨物不用裝車配送；2、假設(shè)每個(gè)客戶需要的是同一種貨物。

8、四、符號(hào)說明其中一輛車負(fù)責(zé)的客戶數(shù)第i個(gè)客戶到第j個(gè)客戶的路程，i,j=1,2,10為1時(shí)，表示走過城市i到城市j之間的路i,j=1,2,10Z一輛運(yùn)貨車走過的路程W總費(fèi)用五、模型的建立與求解模型一的建立與求解 由客戶與客戶之間的距離矩陣可以看出，這是一個(gè)有向網(wǎng)絡(luò)圖且圖中有10個(gè)頂點(diǎn)，現(xiàn)需要求從頂點(diǎn)2到頂點(diǎn)10的最短路。設(shè)為賦權(quán)鄰接矩陣，其分量為決策變量為，當(dāng)=1時(shí)，說明弧位于頂點(diǎn)2至頂點(diǎn)n的路上；否那么=0.其數(shù)學(xué)規(guī)劃表達(dá)式為：S.t. 由上面的數(shù)學(xué)規(guī)劃表達(dá)式和客戶與客戶之間的距離矩陣，編寫程序，利用lingo見附錄1,求得從客戶2到客戶10的最短行使路線為：；最短路程為：30+25+10+

9、20=85公里.公司要求用送貨員從客戶1出發(fā)，給其它9個(gè)客戶送貨，最后再返回出發(fā)地，這和旅行商問題類似。于是，設(shè)城市的個(gè)數(shù)為 n, 是兩個(gè)城市i與j之間的距離，=0或11表示走過城市i到城市j之間的路，0表示沒有走過城市i到城市j之間的路，表示集合s中元素個(gè)數(shù)。有s.t. 由上面的數(shù)學(xué)規(guī)劃表達(dá)式和客戶與客戶之間的距離矩陣，編寫程序，利用lingo(見附錄2),求得從客戶1 出發(fā)，經(jīng)過其它各個(gè)客戶點(diǎn)再回到客戶1的最短行使路線為：最短路程為：25+10+25+30+15+20+10+20+20+50=225公里.每輛車的容量要小于50，可以轉(zhuǎn)換為一輛車所裝載的貨物大于36小于50，可建立約束條件為

10、： 因?yàn)槭莾奢v車給顧客送貨，所以說每輛車不需要經(jīng)過所有的顧客點(diǎn)，每個(gè)顧客點(diǎn)只需要有車經(jīng)過，然后在離開即可。因此我們采用01規(guī)劃模型將進(jìn)去顧客點(diǎn)用1表示否那么用0表示，離開顧客點(diǎn)用1表示否那么用0表示。所以我們建立的約束條件為： 故可建立如下模型：運(yùn)用lingo見附錄3可以求得以下結(jié)果表1 其中一輛車經(jīng)過的路徑及長度K的值滿足條件的較短路徑1-1路徑長度單位：公里3955135由以上數(shù)據(jù)我們求出一輛車的最短路徑，第二輛車的行使路徑必須經(jīng)過第一輛車所沒經(jīng)過的客戶點(diǎn)。于是我們建立新的模型，如下所示：運(yùn)用lingo求得結(jié)果如下：表2 另一輛車經(jīng)過的路徑及長度K的值滿足條件的較短路徑2-1路徑長度單位：

11、公里62054155通過表1、表2，我們得出：第一種情況兩輛車中一輛車裝載5個(gè)客戶的貨物，另外一輛車裝載4個(gè)客戶的貨物，總的路徑長度為：135+155=290公里；第二種情況兩輛車中一輛車裝載3個(gè)客戶的貨物，另外一輛車裝載6個(gè)客戶的貨物，總的路徑長度為：95+205=300公里。根據(jù)題目要求行使的距離之和盡可能短，因此，第一種情況的方案較好。在執(zhí)行此方案時(shí)，一號(hào)車的載貨量為：9+7+5+12+9=42；二號(hào)車的載貨量為：13+6+15+10=44，滿足車容量條件。表3 最優(yōu)的配送方案車號(hào)行使路線路徑長度公里總路徑長度公里負(fù)責(zé)的客戶1號(hào)車135 2904,5,8,9,102號(hào)車155 2,3,6

12、,7模型四的建立與求解每個(gè)客戶有一輛車到達(dá)為其送貨，所為我們建立的約束條件為：因?yàn)椴豢紤]返回時(shí)的費(fèi)用，所以我們建立的約束條件為：每輛車的最大容量為25，所以我們建立的約束條件為：以總費(fèi)用最小為目標(biāo)函數(shù)建立如下模型： 運(yùn)用lingo計(jì)算出k等于4時(shí)，總費(fèi)用W最小為645。具體路線如下表：表4 最優(yōu)的配送方案車號(hào)行使路線路徑長度公里負(fù)責(zé)的客戶1號(hào)車402,52號(hào)車803,4,83號(hào)車556,74號(hào)車709,10六、模型的評價(jià)與推廣模型的優(yōu)點(diǎn)模型運(yùn)用01線性規(guī)劃模型和整數(shù)線性規(guī)劃建立的模型比擬簡單明了思路清晰，該模型主要運(yùn)用lingo進(jìn)行計(jì)算，其中還引入Hamilton圈的進(jìn)行求解，使得結(jié)果更加精確

13、。我們還用統(tǒng)一的模型同時(shí)計(jì)算出兩輛車的最優(yōu)路線，得出最優(yōu)解。模型的缺點(diǎn)及改良該模型計(jì)算量較大，數(shù)據(jù)較多，計(jì)算過程比擬繁瑣。我們可以改良模型使得計(jì)算量減少，防止在計(jì)算中產(chǎn)生的錯(cuò)誤。模型的推廣該模型可應(yīng)用于物流行業(yè)，運(yùn)費(fèi)減少公司獲得的利潤增大。還可應(yīng)用于郵遞員投遞問題，使郵遞員走的路程最短，提高工作效率。七、參考文獻(xiàn)1?運(yùn)籌學(xué)?教材編寫組，運(yùn)籌學(xué)修訂版，北京：清華大學(xué)出版社，1990.2謝金星，薛毅編著，優(yōu)化建模與LINDO/LINGO 軟件，北京：清華大學(xué)出版社， 2005。3白其崢主編，數(shù)學(xué)建模案例分析，北京：海洋出版社，2000。4萬保成 王田蛾，?lingo9.0 for windows軟

14、件及應(yīng)用?，吉林農(nóng)業(yè)大學(xué)數(shù)學(xué)教研室，2004。5Frank R. Giordano 著，葉其孝 姜起源譯，?數(shù)學(xué)建模?，機(jī)械工程出版社，2006。八、附錄附錄1model:data: n=10;enddatasets: points/1.n/: F; !10個(gè)客戶點(diǎn); roads(points,points)/ 1,2 2,3 2,5 2,6 2,8 3,4 3,6 3,7 3,8 3,10 4,5 4,6 4,7 4,8 4,9 4,10 5,6 5,7 5,8 5,10 6,7 6,8 6,9 7,8 7,9 7,10 8,9 9,10/: D, P;endsetsdata:D= 50 3

15、0 35 50 60 15 30 50 25 60 45 30 55 20 40 65 60 10 30 55 25 55 35 30 45 60 10 20;enddata F(n)=0; for(points(i) | i #lt# n: F(i)=min(roads(i,j): D(i,j)+F(j);); !顯然，如果P(i,j)=1,那么點(diǎn)i到點(diǎn)n的最短路徑的第一步是i - j，否那么就不是。 由此，我們就可方便確實(shí)定出最短路徑; for(roads(i,j): P(i,j)=if(F(i) #eq# D(i,j)+F(j),1,0) );End附錄2MODEL:SETS: CUST

16、OMERS / 1. 10/: U; LINK( CUSTOMERS, CUSTOMERS): DIST,X; ENDSETS DATA: DIST = 0 50 100000 40 25 100000 30 100000 50 100000 50 0 30 100000 35 50 100000 60 10000 100000 100000 30 0 15 100000 30 50 25 100000 60 40 10000 15 0 45 30 55 20 40 65 25 15 100000 45 0 60 10 30 100000 55 100000 50 30 30 60 0 25

17、55 35 1000000 30 100000 50 100000 10 25 0 30 45 60 100000 60 25 20 30 55 30 0 10 100000 20 100000 100000 40 100000 15 25 45 0 20 35 20 10 45 20 100000 60 100000 30 0;ENDDATA N = SIZE( CUSTOMERS); MIN = SUM( LINK: DIST * X); FOR( CUSTOMERS( K): SUM( CUSTOMERS( I)| I #NE# K: X( I, K) = 1; SUM( CUSTOME

18、RS( J)| J #NE# K: X( K, J) = 1; FOR( CUSTOMERS( J)| J #GT# 1 #AND# J #NE# K: U( J) = U( K) + X ( K, J) - ( N - 2) * ( 1 - X( K, J) + ( N - 3) * X( J, K) ); ); FOR( LINK: BIN( X); FOR( CUSTOMERS( K)| K #GT# 1: U( K) = 1 + ( N - 2) * X( K, 1) );END附錄3model:sets: CUSTOMERS/ 1.10/: u,D; link( CUSTOMERS,

19、 CUSTOMERS):C, x; endsets min = sum( link: C*x); sum(CUSTOMERS( I)| I #ne# 1: x(I, 1)=1; sum(CUSTOMERS( I)| I #ne# 1: x(1,I)=1; FOR( CUSTOMERS(K): sum( CUSTOMERS( I)| I #ne# K: x( I, K)1; sum( CUSTOMERS( J)| J #ne# K: x(K,J)K;sum(link(I,J)|I #ne# J:x(I,J)*D(J)36;sum(link(I,J)|I #ne# J:x(I,J)*D(J)86;for(CUSTOMERS