最短路線問題論文

1、最短路線問題摘要： 由于市場的競爭，現(xiàn)在大多公司都采取送貨上門的服務(wù)方式，在這送貨過程中需要考慮路徑最短問題和費(fèi)用最省問題等。本文根據(jù)運(yùn)輸公司提供的提貨點到各個客戶點的路程數(shù)據(jù)和對問題的分析和理解 ，利用最短路徑問題進(jìn)行求解，得到相關(guān)問題的模型。 針對問題一 ，根據(jù)題目提供的數(shù)據(jù)，使用LINGO軟件進(jìn)行編程建立模型，通過運(yùn)行程序并分析求解得出當(dāng)運(yùn)送員在給第二個客戶卸貨完成的時，若要他先給客戶10送貨，此時盡可能短的行使路線為：V V V V V .總行程共85公里。 針對問題二: 通過對問題的理解要找到走完所有的客戶點再回到提貨點的最佳路徑，我們采用Dijkstra算法逐一找到從i第個到第j個

2、客戶的最短路程(i,j=1,2,3,4,5,6,7,8,9,10)，最后得到一條理想的回路是： V V V V V V V V VV 針對問題三，我們首先直接利用問題二得一輛車的最優(yōu)回路，以貨車容量為限定條件，采用Dijkstra算法建立相應(yīng)的規(guī)劃模型并設(shè)計一個簡單的尋路算法，最終可為公司確定合理的運(yùn)輸方案：（兩輛車總和行程280公里）車號行車路線線路長度送貨客戶一號車1 5 2 3 4 8 9 1135公里2、3、4、5、8二號車1 7 6 9 10 1145公里6、7、9、10針對問題四，我們首先用Dijkstra算法確定提貨點到每個客戶點間的最短路線，然后結(jié)合一些限定條件建立一個目標(biāo)模型

3、，設(shè)計一個較好的解決方案進(jìn)行求解可得到一種理想的運(yùn)輸方案：車號線路路線長度載貨量一號車40公里20單位二號車50公里20單位三號車80公里25單位四號車70公里21單位方案總消費(fèi)：645元關(guān)鍵字：配送問題 LINGO軟件 Dijkstra算法 最短路問題 消耗最低一、 問題重述 某運(yùn)輸公司為10個客戶配送貨物，假定提貨點就在客戶1所在的位置。問題：運(yùn)送員在給第二個客戶卸貨完成的時候，臨時接到新的調(diào)度通知，讓他先給客戶10送貨，已知送給客戶10的貨已在運(yùn)送員的車上，請幫運(yùn)送員設(shè)計一個到客戶10的盡可能短的行駛路線。問題：現(xiàn)在運(yùn)輸公司派了一輛大的貨車為這10個客戶配送貨物，假定這輛貨車一次能裝滿1

4、0個客戶所需要的全部貨物嗎，請問貨車從提貨點出發(fā)給10個客戶配送完貨物后再回到提貨點所行駛的盡可能短的行駛路線？對所設(shè)計的算法進(jìn)行分析。問題：現(xiàn)因資源緊張，運(yùn)輸公司沒有大貨車可以使用，改用兩輛小的貨車配送貨物。每輛小貨車的容量為50個單位，每個客戶所需的貨物量分別為8，13，6，9，7，15，10，5，12，9個單位，請問兩輛小貨車應(yīng)該分別給哪幾個客戶陪送貨物以及行駛怎樣的路線使它們從提貨點出發(fā)最后回到提貨點所行駛的距離之和盡可能短？對所設(shè)計的算法進(jìn)行分析。問題：如果改用更小容量的車，每車容量為25個單位，但用車數(shù)量不限，每個客戶所需要的貨物量同第三問，并假設(shè)每出一輛車的出車費(fèi)為100元，運(yùn)貨

5、的價格為1元/公里（不考慮空車返回的費(fèi)用），請問如何安排車輛才能使得運(yùn)輸公司運(yùn)貨的總費(fèi)用最省？二、 問題分析 問題1：運(yùn)送員在給第二個客戶卸完貨后，即從此處趕到第十個客戶處，路程越短越好，是一個最短路徑問題，為此我們采用LINGO軟件進(jìn)行編程，通過程序運(yùn)行的結(jié)果加以分析和驗證，最后得出路徑最短的行使路線。程序?qū)⒃谙挛牧谐?。問題2：很明顯運(yùn)輸公司分別要對10個客戶供貨，必須訪問每個客戶，但問題要求我們建立相應(yīng)模型尋找一條盡可能短的行車路線，我們考慮送貨員送完所有貨以后再返回提貨點的情況。要找到送完貨的最短路徑我們使用Dijkstra算法依次找出從一個客戶點到下一個客戶點的最短距離。再用同樣的方法

6、找出回到提貨點的最佳路徑。問題3：用兩輛容量為50單位的小貨車運(yùn)貨，在每個客戶所需固定貨物量的情況下，要使得行程之和最短，我們假設(shè)每個客戶的貨物都由同一輛貨車提供，這樣只要找出兩條盡可能短的回路，并保證每條線路客戶總需求量在50個單位以內(nèi)?？筛鶕?jù)貨物需求量的大小將其分為前后兩部分，并將之分別構(gòu)成回路。（注：由于提貨點在客戶1所在的位置，故不必考慮為客戶1送貨的情況。）首先找出兩條提貨點到下一客戶點的最短路，再依次使用Dijkstra算法分別找出到下一客戶點的最短路，充分考慮車的容量和每個客戶需要的貨物量，最后的出最優(yōu)路徑。問題4：由于從第2個客戶到第10個客戶所需的貨物量總和為86個單位，而每

7、輛車的容量為25個單位，則至少需要4輛車，即至少要找4條最短路線。要使得所有路線行程之和最短，并保證每條路線上的客戶總需求量不超過25個單位，我們用Dijkstra算法分別找出到下一客戶點的最短路，充分考慮車的容量和每個客戶需要的貨物量。三、 基本假設(shè)問題1：1：不考慮送貨員走同一個客戶點的情況。問題2：1：不考慮送貨員走同一個客戶點的情況。2：四、 模型的建立與求解問題：模型建立與求解 問題一是由第2客戶送貨去第10客戶，這里就是最解路線問題，我們可以借用LINGO軟件，進(jìn)行最優(yōu)路線選擇。運(yùn)行程序： SETS:CITIES /1.10/:F;ROADS(CITIES,CITIES)/1,4

8、1,2 1,5 1,7 1,92,3 2,5 2,6 2,83,4 3,6 3,7 3,8 3,104,5 4,6 4,7 4,8 4,9 4,105,6 5,7 5,8 5,106,7 6,8 6,97,8 7,9 7,108,99,10/:D;ENDSETSDATA:D=40 50 25 30 5030 35 50 6015 30 50 25 60 45 30 55 20 40 6560 10 30 55 25 55 35 30 45 6010 20;ENDDATAF(SIZE(CITIES)=0;FOR(CITIES(i)|i#LT#SIZE(CITIES):F(i)=MIN(ROADS

9、(i,j):D(i,j)+F(j);END 運(yùn)行結(jié)果： 0 Variable Value F( 1) 70.00000 F( 2) 85.00000 F( 3) 55.00000 F( 4) 50.00000 F( 5) 55.00000 F( 6) 55.00000 F( 7) 60.00000 F( 8) 30.00000 F( 9) 20.00000 F( 10) 0.000000 D( 1, 4) 40.00000 D( 1, 2) 50.00000 D( 1, 5) 25.00000 D( 1, 7) 30.00000 D( 1, 9) 50.00000 D( 2, 3) 30.00

10、000 D( 2, 5) 35.00000 D( 2, 6) 50.00000 D( 2, 8) 60.00000 D( 3, 4) 15.00000 D( 3, 6) 30.00000 D( 3, 7) 50.00000 D( 3, 8) 25.00000 D( 3, 10) 60.00000 D( 4, 5) 45.00000 D( 4, 6) 30.00000 D( 4, 7) 55.00000 D( 4, 8) 20.00000 D( 4, 9) 40.00000 D( 4, 10) 65.00000 D( 5, 6) 60.00000 D( 5, 7) 10.00000 D( 5,

11、8) 30.00000 D( 5, 10) 55.00000 D( 6, 7) 25.00000 D( 6, 8) 55.00000 D( 6, 9) 35.00000 D( 7, 8) 30.00000 D( 7, 9) 45.00000 D( 7, 10) 60.00000 D( 8, 9) 10.00000 D( 9, 10) 20.00000 Row Slack or Surplus 1 0.000000 2 0.000000 3 0.000000 4 0.000000 5 0.000000 6 0.000000 7 0.000000 8 0.000000 9 0.000000 10

12、0.000000所以又程序結(jié)果可以的出由2到10的最短距離為：V問題：模型建立與求解、首先與1有直接相連的線路點有2、4、5、7、9 S= V , =V,V,V,V,V L(V) =0 L(V)=L(V)+W=50用同樣的方法可有： S= V，V , =V,V,V,V L(V)=L(V)+W=40 S= V，V , V , = V ,V,V L(V)=L(V)+W=25 S= V，V , V, V , = V,V L(V)=L(V)+W=30 S= V，V , V, V , V , = V L(V)=L(V)+W=50由上面運(yùn)算可以看出，最短路線為1到5.、與5由直接相連的點有1,2,4,6,

13、7,8,10 S= V , = V，V，V ，V, V，V L(V) =0 L(V)=L(V)+W=15 S= V ，V , = V，V ，V, V，V L(V)=L(V)+W=45依此方法，類推有：L(V)=60 L(V)=10 L(V)=30 L(V)=55 所以由運(yùn)算結(jié)果可知，最短路線為：5到7.、與7直接由連線的點有3、5、6、8、9、10 S= V , = V，V ，V, V，V L(V) =0 L(V)=L(V)+W=50 S= V ，V , = V ， V，V ，V L(V)=L(V)+W=25依此方法，類推有：L(V)=30 L(V)=45 L(V)=60所以由運(yùn)算結(jié)果可知，最

14、短路線為：7到6.、與6有直接相連的線路點有3,4，8,9 S= V , = V，V ，V, V L(V) =0 L(V)=L(V)+W=30 S= V ，V , = V ， V，V L(V)=L(V)+W=30依此方法，類推有：L(V)=30 L(V)=55 L(V)=35所以由運(yùn)算結(jié)果可知，最短路線為：6到3.、與3有直接相連的路線點有2、4、8、10 S= V , = V， V， V,V L(V) =0 L(V)=L(V)+W=30 S= V ，V , = V ， V，V L(V)=L(V)+W=15依此方法，類推有：L(V)=20 L(V)=60所以由運(yùn)算結(jié)果可知，最短路線為：3到4.

15、、與4直接相連的路線點有8、9、10 S= V , = V, V，V L(V) =0 L(V)=L(V)+W=20 S= V ，V , = V ，V L(V)=L(V)+W=40依此方法，類推有： L(V)=65所以由運(yùn)算結(jié)果可知，最短路線為：4到8.、與8有直接連接的線路點有 2,9 S= V , = V ， V L(V) =0 L(V)=L(V)+W=60 S= V ，V , = V L(V)=L(V)+W=10所以由運(yùn)算結(jié)果可知，最短路線為：8到9.、與9直接相連的就是10 L(V)=20 ，與9相連的最短距離就是客戶10.與10直接相連的就是2 L(V)=20與2直接相連的就是1 L(

16、V)=50 結(jié)論：所以，貨車從提貨點出發(fā)給10個客戶配送完貨物后再回到提貨點所行使的盡可能短的方便的行使路線為：1 5 7 6 3 4 8 9 10 2 1行使的總路程為225公里問題：模型建立與求解公司派出兩輛容量為50個單位的小貨車配送貨物，則需找出兩條最短路線。首先找第1個客戶到第j個客戶的最短路線，最短路線為1 5，其次是1 7，即為兩車出發(fā)路線。第一輛車的路線：現(xiàn)在找第5個客戶到第j個客戶的最短路線，此時與5直接相連且和第二輛車的路線中的節(jié)點不重復(fù)的有2，4，6，8，10，于是有：S=V，=V，V，V，V，VL(V)=0L(V)= L(V)+W=15S= V，V，= V，V，V，VL

17、(V)= L(V)+W=45依此類推，L(V)=60， L(V)=30， L(V)=55，則最短路線為5 2，此時車的載貨量為7+13=20個單位。第2個客戶到第j個客戶的最短路線，此時與2直接相連且與以上路線中的節(jié)點不重復(fù)的有3，6，8，于是有： S=V，=V，V，VL(V)=0L(V)= L(V)+W=30S=V，V，= VL(V)= L(V)+W=50依此類推，L(V)=60，則最短路線為2 3，此時車的載貨量為20+6=26個單位。第3個客戶到第j個客戶的最短路線，此時與3直接相連且與以上路線中的節(jié)點不重復(fù)的有4，6，8，10，于是有： S=V，=V，V，V，VL(V)=0L(V)=

18、L(V)+W=15S=V，V，= V，V，VL(V)= L(V)+W=15 依此類推，有L(V)=25， L(V)=60，則最短路線為3 4，此時車的載貨量為26+9=35個單位。第4個客戶到第j個客戶的最短路線，此時與4直接相連且與以上路線中的節(jié)點不重復(fù)的有6，8，9，10，于是有： S=V，=V，V，V，VL(V)=0L(V)= L(V)+W=30 S=V，V，= V，V，VL(V)= L(V)+W=20依此類推，L(V)=40，L(V)=65，則最短路線為4 8，此時車的載貨量為35+5=40個單位。此車最多能加10個單位的貨物，滿足此條件的有第7、10個客戶?，F(xiàn)在考慮與第二輛車所走路線

19、中的節(jié)點不重復(fù)，而第8個與第10個客戶之間無直接的路線到達(dá)，所以此車只為2、3、4、5、8這幾個客戶送貨?，F(xiàn)在找地8個客戶到提貨點的最短路線，第8個客戶沒有直接到達(dá)地1個客戶的路線，而與第8個客戶直接相連的有2，3，4，5，6，7，9，于是有: S=V，=V，V，V，V，V，V，VL(V)=0L(V)= L(V)+W=60S= V，V，= V，V，V，V，V，VL(V)= L(V)+W=25依此類推，L(V)=20， L(V)=30， L(V)=55， L(V)=30， L(V)=10 ，則最短路線為8 9，而第9個客戶有直接到第1個客戶的路線，且路線長度是最小的。所以第一輛車的路線為1 5

20、2 3 4 8 9 1第二輛車的路線：此車應(yīng)先從1到7，此時車的載貨量為10個單位。現(xiàn)在找第7個客戶到第j個客戶的最短路線，此時與7直接相連且與第一輛車的送貨點不重復(fù)的有6，9，10，于是有： S=V，=V，V，VL(V)=0L(V)= L(V)+W=25S= V，V，= V，VL(V)= L(V)+W=45 依此類推，L(V)=60，則最短路線為7 6，此時車的載貨量為10+15=25個單位。現(xiàn)在只有第9、10個客戶的貨沒有送，而第8個客戶到第10個客戶沒有直接路線到達(dá)，且不考慮重復(fù)走，所以此時第二輛車的路線已確定，路線為：1 7 6 9 10 1由以上方案得出，運(yùn)輸公司派出的兩輛車的行駛路

21、線、路線長度及每條路線上的貨物量總需求量如下表：車號行駛路線路線長度貨物需求量該車負(fù)責(zé)的客戶一號車1 5 2 3 4 8 9 1135402，3，4，5，8二號車1 7 6 9 10 1145466，7，9，1，0輛車行駛?cè)炭偤蜑?80公里。問題：模型建立與求解由于第2到第10個客戶所需貨物量總和為86個單位，而每輛車的容量為25個單位，則至少需要4輛車。、第一輛車的路線：首先找第1個客戶到第j個客戶的最短路；與1直接相連的客戶j有2，4，5，7，9于是有： S= V , =V,V,V,V,V L(V) =0 L(V)=L(V)+W=50 用同樣的方法可有： S= V，V , =V,V,V,

22、V L(V)=L(V)+W=40 S= V，V , V , = V ,V,V L(V)=L(V)+W=25 S= V，V , V, V , = V,V L(V)=L(V)+W=30 S= V，V , V, V , V , = V L(V)=L(V)+W=50則，從第1個客戶到第j個客戶的路線距離從近到遠(yuǎn)的排序為1 到5，1到 7，到4,1到9,1到2最短路為1 5，此時車的載重量為第5個客戶所需要貨物量7個單位；接下來找第5個客戶到第j（j=2，3，4，6，7，8，9，10）個客戶的最短路，此時與5直接相連的j客戶有2,4,6,7,8,10； S= V , = V，V，V ，V, V，V L(

23、V) =0 L(V)=L(V)+W=15 S= V ，V , = V，V ，V, V，V L(V)=L(V)+W=45結(jié)論：用同樣的方法，我們可以依此類推得到L(V)=60 L(V)=30 L(V)=55;則最短路線為5 2，此時車的載貨量為第5個客戶與第2個客戶所需要貨物量的總和20；這時，此車最多能再裝5個單位的貨物，所需要貨物量為5的只有第8個客戶，但是第2個客戶到第8 個客戶的距離為60公里，顯然這不是最短的路線，所以此車只為第2、5個客戶送貨，路線為1 5 2.、第二輛車的路線：由知：第二輛車應(yīng)先從1到7，此時車的載貨量為10個單位?，F(xiàn)在找與第7個客戶到第j個客戶的最短路線，與7相連

24、的最短路線的點有1、3、6、8、10.于是有： S= V , = V ，V ， V ， V，V L(V) =0 L(V)=L(V)+W=30 S= V ，V , = V，V ， V，V L(V)=L(V)+W=50依此方法，類推有： L(V)=25 L(V)=30 L(V)=60 則最短路線為 7 6，此時車的載貨量為25個單位，已經(jīng)是達(dá)到了最大載重量，所以此車路線為: 1 7 6 、第三輛車的路線：由知，第三輛車應(yīng)先從1到4，此時車的載貨量為9個單位，現(xiàn)在找第4個客戶到第j個客戶的最短路線，此時與4直接相連的點有3、8、9、10.于是有： S= V , = V ， V ，V ，V L(V)

25、=0 L(V)=L(V)+W=15 S= V ，V , = V ，V ，V L(V)=L(V)+W=20依此方法，類推有： L(V)=40 L(V)=65 則最短路線為4 3，此時車的載貨量為15個單位，再找第3個客戶到第j個客戶的最短路線，此時與3直接相連的有8、10于是有： S= V , = V ， V L(V) =0 L(V)=L(V)+W=25 S= V ，V , = V L(V)=L(V)+W=60則最短路線為3 8，此時車的載貨量為20個單位，此車不能再加貨，所以此車只為了第3、4、8個客戶送貨，路線為：1 4 3 8、第四輛車的路線：由和知，此車應(yīng)先從1到9，此時車的載重量為12

26、個單位，再由、知道，只有第10個客戶沒有車送貨，則第四輛車就會有最后的送貨線路，及：1 9 10 此時車的載重量為21個單位。結(jié)論：由、輛車就可以將獲送完，而且線路最短，花銷最少。路線長度及每條路線上的貨物總需求如下表：車號行車路線路線長度貨物需求量一號車1 5 2. 40 20二號車1 7 6 55 20三號車1 4 3 8 80 25四號車1 9 10 70 21顯然每條發(fā)車路線上貨物載重量沒有超過25個單位，故方案可行，公司運(yùn)貨的總費(fèi)用為： Z=（40+55+80+70）*1+4*100=645 （元）五、模型評價從我們建立的模型來看，無論是理論上或者是和現(xiàn)實的接近性上，都是比較合理的，

27、我們主要從模型的假設(shè)合理性、建模的創(chuàng)造性、運(yùn)算的效率和結(jié)果的正確性對其做出客觀的評價：1，我們的假設(shè)均考慮客觀性合乎情理，模型(1)與模型(2)在現(xiàn)實中也可以廣泛的應(yīng)用，與現(xiàn)實狀況緊密相連；例如：最優(yōu)路徑問題，在現(xiàn)實生活已經(jīng)應(yīng)運(yùn)范圍很廣了。2.對模型（1）我們使用的LINGO軟件較為簡單，便于使用，容易懂，是問題簡單化，準(zhǔn)確性較高。3.我們使用的Dijkstra算法能得出路徑的最優(yōu)方案，但步驟較為復(fù)雜，要計算的節(jié)點多，計算效率較低。4.就是模型求解的效率性了，由于本題目的數(shù)據(jù)量不大，我們的程序運(yùn)行均能瞬間完成。5.就是結(jié)果的正確性了，通過模型的求解，我們得到與現(xiàn)實很接近的結(jié)果，可以說是合理、正

28、確的。六、 模型推廣 最短路問題是圖論理論的一個經(jīng)典問題。尋找最短路徑就是在指定網(wǎng)絡(luò)中兩結(jié)點間找一條距離最小的路。最短路不僅僅指一般地理意義上的距離最短,還可以引申到其它的度量,如時間、費(fèi)用、線路容量等。最短路問題在實際生活中有廣泛的運(yùn)用，如在運(yùn)輸網(wǎng)絡(luò)結(jié)構(gòu)的分析，交通運(yùn)輸線路的選擇，通訊線路的建造與維護(hù)，運(yùn)輸貨量的最小成本分析等都有直接的應(yīng)用價值。七、 參考文獻(xiàn)八、 附錄 程序1：SETS:CITIES /1.10/:F;ROADS(CITIES,CITIES)/1,4 1,2 1,5 1,7 1,92,3 2,5 2,6 2,83,4 3,6 3,7 3,8 3,104,5 4,6 4,7 4,8 4,9 4,105,6 5,7 5,8 5,106,7 6,8 6,97,8 7,9 7,108,99,10/:D;ENDSETSDATA:D=40 50 25 30 5030 35 50 6015 30 50 25 60 45 30 55 20 40 6560 10 30 55 25 55 35 30 45 6010 20;ENDDATAF(SIZE(CITIES)=0;FO