數(shù)學(xué)建模送貨線路設(shè)計(jì)問題

1、送貨路線設(shè)計(jì)問題1、 問題重述現(xiàn)今社會(huì)網(wǎng)絡(luò)越來越普及，網(wǎng)購已成為一種常見的消費(fèi)方式，隨之物流行業(yè)也漸漸興盛，每個(gè)送貨員需要以最快的速度及時(shí)將貨物送達(dá)，而且他們往往一人送多個(gè)地方，請(qǐng)?jiān)O(shè)計(jì)方案使其耗時(shí)最少?，F(xiàn)有一快遞公司，庫房在圖1中的O點(diǎn)，一送貨員需將貨物送至城市內(nèi)多處，請(qǐng)?jiān)O(shè)計(jì)送貨方案，使所用時(shí)間最少。該地形圖的示意圖見圖1，各點(diǎn)連通信息見表3，假定送貨員只能沿這些連通線路行走，而不能走其它任何路線。各件貨物的相關(guān)信息見表1，50個(gè)位置點(diǎn)的坐標(biāo)見表2。 假定送貨員最大載重50公斤，所帶貨物最大體積1立方米。送貨員的平均速度為24公里/小時(shí)。假定每件貨物交接花費(fèi)3分鐘，為簡(jiǎn)化起見，同一地點(diǎn)有多件貨

2、物也簡(jiǎn)單按照每件3分鐘交接計(jì)算?，F(xiàn)在送貨員要將100件貨物送到50個(gè)地點(diǎn)。請(qǐng)完成以下問題。1. 若將130號(hào)貨物送到指定地點(diǎn)并返回。設(shè)計(jì)最快完成路線與方式。給出結(jié)果。要求標(biāo)出送貨線路。2. 假定該送貨員從早上8點(diǎn)上班開始送貨，要將130號(hào)貨物的送達(dá)時(shí)間不能超過指定時(shí)間，請(qǐng)?jiān)O(shè)計(jì)最快完成路線與方式。要求標(biāo)出送貨線路。3. 若不需要考慮所有貨物送達(dá)時(shí)間限制(包括前30件貨物)，現(xiàn)在要將100件貨物全部送到指定地點(diǎn)并返回。設(shè)計(jì)最快完成路線與方式。要求標(biāo)出送貨線路，給出送完所有快件的時(shí)間。由于受重量和體積限制，送貨員可中途返回取貨?？刹豢紤]中午休息時(shí)間。2、 問題分析送貨路線問題可以理解為：已知起點(diǎn)和終

3、點(diǎn)的圖的遍歷問題的合理優(yōu)化的路線設(shè)計(jì)。圖的遍歷問題的指標(biāo)：路程和到達(dá)的時(shí)間，貨物的質(zhì)量和體積，以及最大可以負(fù)載的質(zhì)量和體積。在路線的安排問題中，考慮所走的路程的最短即為最合理的優(yōu)化指標(biāo)。對(duì)于問題二要考慮到所到的點(diǎn)的時(shí)間的要求是否滿足題意即采用多次分區(qū)域的假設(shè)模型從而找出最優(yōu)的解對(duì)于問題三則要考慮到體積和質(zhì)量的雙重影響，每次到達(dá)后找到達(dá)到最大的體積和質(zhì)量的點(diǎn)然后返回，再依次分析各個(gè)步驟中可能存在的不合理因素達(dá)到模型的進(jìn)一步合理優(yōu)化得到最合理的解。3、 模型假設(shè)與符號(hào)說明3.1、模型的假設(shè)（1）、到同一地點(diǎn)的貨物要一次拿上，即不考慮再以后又經(jīng)過時(shí)再帶些貨物（2）、要求達(dá)到不超過的時(shí)間不包括此次在該

4、點(diǎn)交易的時(shí)間。（3）、所用的距離數(shù)據(jù)都精確到米而時(shí)間則精確到0.0001h（4）、同一地點(diǎn)有多件貨物也簡(jiǎn)單按照每件3分鐘交接計(jì)算。3.2、符號(hào)說明其中i，j=1、2、350并且M=50kg V=1m34、 模型的建立及求解模型四模型三模型二模型一最短路徑模型圖的遍歷模型多區(qū)域最短路多階段最短路任意兩點(diǎn)之間的最短路距離由起始點(diǎn)遍歷路徑回到原點(diǎn)多區(qū)域無返回起點(diǎn)的最短路多階段有返回起點(diǎn)的最短路模型一1.1模型的建立我們?yōu)榱饲蟪龈鱾€(gè)點(diǎn)的之間的最短的路徑，使用Dijstra算法求解。 Dijkstra算法是圖論中非常有名的一個(gè)算法。圖采用鄰接矩陣的形式描述，w（i,j）表示結(jié)點(diǎn)i到結(jié)點(diǎn)j間的最短距離，如

5、果沒有直接連通，則為無窮大，計(jì)算機(jī)中可以用一個(gè)很大的數(shù)據(jù)代替（如matlab中的inf）。但dijkstra算法只能求出從結(jié)點(diǎn)i到其它各結(jié)點(diǎn)的最短路徑。算法引入這樣兩個(gè)集合s和t，s是那些已經(jīng)確定了到i結(jié)點(diǎn)的最短路徑的結(jié)點(diǎn)，t為全集u和s的差集，即那些還未確定最短路徑的結(jié)點(diǎn)。而且s的初值是i，t的初值是u-i。另外再引入一個(gè)標(biāo)記數(shù)組dn，其中在某一步dk表示當(dāng)前從i到k的較短路徑，dk的初值為w（i，k）。整個(gè)算法過程如下：、 在t中選擇一個(gè)dk最小的結(jié)點(diǎn)k，將k并入s，并從t中去掉，如果t為則轉(zhuǎn)到；、 用k結(jié)點(diǎn)和t中其余結(jié)點(diǎn)進(jìn)行一遍比較，如果di>dk+mki，則用dk+mki取代原來

6、的di，重復(fù)；、 算法結(jié)束，此時(shí)dk中保存的就是從i到k結(jié)點(diǎn)的最短路徑。算法就以這樣非常簡(jiǎn)單的形式完成了求解，時(shí)間復(fù)雜度是O(n2)，確定了從i到其余各結(jié)點(diǎn)的最短路徑。1.2模型的求解根據(jù)算法和相鄰的點(diǎn)的距離可以用dijkstra求出任意兩點(diǎn)的最短路徑。圖1相鄰的點(diǎn)的距離使用循環(huán)的結(jié)構(gòu)求出1-50各個(gè)點(diǎn)之間的最短距離。程序1見附錄2.1可以求出w和aa為最短路徑是的所過的的地點(diǎn)如從O開始到其余50個(gè)點(diǎn)的a(0)= 0 7 4 8 3 15 1 18 12 14 18 13 13 18 21 12 23 21 0 24 22 0 29 17 31 19 0 31 30 25 22 26 23 2

7、8 31 38 21 40 36 27 34 37 43 38 41 36 41 40 46 42 40要從O點(diǎn)到16點(diǎn)則要先到23即0-23-16要從O點(diǎn)到23點(diǎn)則要先到17即0-17-23-16要從o點(diǎn)到17點(diǎn)則要先到21即0-21-17-23-16而O可以直接到21所以從0到16的最優(yōu)路徑是0-21-17-23-16最短的距離是w（0,16）=7493m模型二 對(duì)于問題一的求解2.1模型的建立由前30件貨物可以到達(dá)的地點(diǎn)可以知道i，j= 13、14、16、17、18、21、23、24、26、27、31、32、34、36、38、39、40、42、43、45、49。圖2需要達(dá)到的點(diǎn)（紅點(diǎn)標(biāo)注

8、的）其中共經(jīng)過21個(gè)點(diǎn)，運(yùn)送30件貨物該30件貨物m=47.3kg<50kg v=0.8371m3,所以可以一次把貨物攜帶進(jìn)行運(yùn)送。由T與W關(guān)系可知要使所用的時(shí)間最小即所走的距離最短。即目標(biāo)函數(shù)是：T=W÷V+t0×30 約束條件是：必須全部遍歷回到0點(diǎn)即求出從O出發(fā)遍歷這圖的21個(gè)點(diǎn)的并回到o的最短的距離要距離最短則每一步也要最短，即從O開始找最短的點(diǎn)到達(dá)后繼續(xù)找未遍歷的最短的點(diǎn)則可求出最短的距離。本題要求出回到O點(diǎn)則可以看到兩個(gè)開始最短遍歷的點(diǎn)在某點(diǎn)重合即可完成最短的遍歷。2.2模型的求解由圖可以明顯得出距離O最近的點(diǎn)是21點(diǎn)和26點(diǎn)。由于32點(diǎn)到38點(diǎn)的距離小于

9、32點(diǎn)到16點(diǎn)的距離為使從21點(diǎn)出來的線遍歷右下的點(diǎn)完后再和26點(diǎn)出來的匯合則安排32點(diǎn)到35點(diǎn)斷開。有程序2（附錄2.2）可得：013112132321314334141643615175381618639172174018238421924943202610452127114922遍歷節(jié)點(diǎn)路線是：0-21-17-23-32-16-14-18-13-24-34-40-45-49-42-43-38-36-39-27-31-26-0最優(yōu)的路線是：0-21-17-23-32-23-16-14-21-18-13-19-24-31-34-40-45-42-49-42-43-38-36-27-39-27

10、-31-26-0總路程是：W=53787m 最優(yōu)時(shí)間是：T=3.7411h模型三 對(duì)于問題二的求解3.1模型的建立 由第一個(gè)模型建立的可以求出到達(dá)24時(shí)所用的時(shí)間是:可知到24點(diǎn)的時(shí)間是：t(24)=2.0880由表2.1可知必須在9點(diǎn)之前把貨物送到24點(diǎn)即t(24)<1故模型一不適用于問題二的求解.由下圖3可知：圖3.考慮時(shí)間的點(diǎn)的位置由于右邊的點(diǎn)的地點(diǎn)需要的時(shí)間要比左邊的早，所以先分兩個(gè)階段，即先走左邊后走右邊即先走圈內(nèi)的元素由程序3（附錄2.3）可得：從O出發(fā)經(jīng)過13、18、24、26、27、31、34、39、40到達(dá)455260.10807310.22206270.3165929

11、0.44074240.68353280.89542131.07518311.439310401.557311451.7413而到13點(diǎn)時(shí)必須在9點(diǎn)之前到達(dá)但1.0751>1，到45點(diǎn)時(shí)必須在9點(diǎn)半之前到達(dá)而1.7412>1.5故分成兩個(gè)階段不成功，所以分四個(gè)階段，求出各個(gè)階段的最短距離和到達(dá)時(shí)的時(shí)間即可。目標(biāo)函數(shù)：ti=Wi÷v+t0約束條件是：T到個(gè)點(diǎn)的時(shí)間最大值3.2模型的求解圖4.4個(gè)階段的圈圖對(duì)四個(gè)階段分別求出到達(dá)的時(shí)間，由程序4（附錄2.4）可知l 分4個(gè)階段3180.09092130.27064240.55871. 從0出發(fā)經(jīng)過13、18到24。滿足t<

12、1的條件故路線為：0-18-13-242310.73293340.92974401.04775451.23172. 從24出發(fā)經(jīng)過31、34、40到45。 滿足t<1.5故路線為：24-31-34-40-453421.42975491.56184431.73222381.89133. 從45出發(fā)經(jīng)過38、42、43到49。滿足t<2.25所以路線為：45-42-49-43-384. 從38出發(fā)經(jīng)過14、16、17、21、23、26、27、32、36、39回到O。10362.00548272.147211392.32147262.55405212.74544172.87146232.

13、99539323.15003163.44202143.6007滿足t<4故路線為：38-36-27-39-27-31-26-21-17-23-32-16-14-21-0所以總的遍歷點(diǎn)順序是：0-18-13-24-31-34-40-45-42-49-43-38-36-27-39-26-21-17-23-32-16-14-0總時(shí)間是T=3.9130h總距離是W=57912m最優(yōu)路線是：0-18-13-19-24-31-34-40-45-42-49-42-43-38-36-27-39-27-31-26-21-17-23-32-23-16-14-21-0到每個(gè)點(diǎn)的時(shí)間見附錄1.4模型四 對(duì)于問題

14、三的求解4.1模型的建立本題中要遍歷所有的50個(gè)點(diǎn)但由于M總=147kg，v 總 =2.8m3而M<50kg,V<1m3故應(yīng)該以M<50kg和V<1m3判斷的標(biāo)準(zhǔn)到達(dá)的最遠(yuǎn)的點(diǎn)后返回。目標(biāo)函數(shù)：W=150w(i,j)約束條件：M<50kg,V<1m34.2模型的求解由O開始逐漸依次找出最近的點(diǎn)后再找出離該點(diǎn)最近的點(diǎn)直到不滿足約束條件。見程序5（附錄2.5）圖5.改進(jìn)后的遍歷圖1第一階段2. 第二階段3. 第三階段 4.第四階段4.3模型的優(yōu)化由于總的m=148kg v=2.8m3 所以最少要分四個(gè)階段，但由于每次不可能剛好帶滿50kg而如果只要3次則最多只能

15、帶150kg只比原貨物多2kg所以不可能是三次就把貨物帶完，最少要四次。故只需要把上述的模型進(jìn)行數(shù)據(jù)處理就好了。過程如下： 1.由于到21點(diǎn)時(shí)M=49 V=0.8757若走過14則M大于了50故直接從21點(diǎn)返回。最優(yōu)路線為： 0-26-31-27-39-27-36-38-35-32-23-17-21-0走的距離W=27122m，花費(fèi)的時(shí)間T=1.73012.若按程序給出的從13到8的路線是13-12-11-12-8而當(dāng)為13-11-12-8時(shí)更短故修改之；同時(shí)到達(dá)40后如果選擇34則45的周圍全被遍歷過。到45后M=46.83,V=1.0247不滿足要求，故從40到34后沿21-26返回。最優(yōu)

16、路線為:0-18-13-11-12-8-3-1-6-1-7-10-9-14-16-23-32-35-38-43-42-49-50-40-45-36-21-0走得距離是：W=83220，所用的時(shí)間是T=4.46753. 當(dāng)?shù)竭_(dá)45點(diǎn)時(shí)若要去20點(diǎn)放貨物的話則需要遍歷許多已經(jīng)遍歷過的地點(diǎn)，故從45點(diǎn)沿36-21-0返回最優(yōu)路線為： 0-26-31-24-19-25-29-22-30-28-33-46-48-44-41-37-40-47-40-45-36-21-0所走的距離為：W=128970m，所用的時(shí)間是：T=6.12384.只余下了5個(gè)點(diǎn),所以由圖可知路線為： 0-26-31-24-19-25

17、-15-22-20-2-5-2-4-3-8-12-13-18-o總路程是：W= 171510m所用的時(shí)間是T=7.3964由上面的四個(gè)階段可以知道該問的最優(yōu)路線是：0-26-31-27-39-27-36-38-35-32-23-17-21-0-18-13-11-12-8-3-1-6-1-7-10-9-14-16-23-32-35-38-43-42-49-50-40-45-36-21-0-26-31-24-19-25-29-22-30-28-33-46-48-44-41-37-40-47-40-45-36-21-0-26-31-24-19-25-15-22-20-2-5-2-4-3-8-12-1

18、3-18-o總路程是：W= 171510m所用的時(shí)間是T=7.39645、 模型的分析 誤差分析：對(duì)于模型一是使用了精確地Dijkstra算法，故誤差可以忽略不計(jì)對(duì)于模型二假定了32到38點(diǎn)的斷開存在一定的誤差，但相對(duì)于斷開其余的幾點(diǎn)得到的數(shù)值要小，故該模型可以使用。 對(duì)于模型三，由于分區(qū)域的方法有很多，故不可避免的存在些許誤差，但由于區(qū)域越多，路程越多，故選擇分成4個(gè)區(qū)域最合適；分成的四個(gè)不同的時(shí)間的到達(dá)區(qū)域比較緊密故按照時(shí)間的不同劃分了四個(gè)區(qū)域，從而大大的消除了誤差，此模型可以使用。對(duì)于模型四的誤差比較大，由于未考慮貨物的拆分可能會(huì)有一定的影響同時(shí)由于4個(gè)階段的劃分也是有一定的不確定性故誤

19、差存在。對(duì)于該模型簡(jiǎn)化了考慮的條件，僅以M和V為判斷標(biāo)準(zhǔn)，雖對(duì)準(zhǔn)確性存在挑戰(zhàn)，但該模型相對(duì)與其他的分類有明顯的優(yōu)越性。故該模型適用于該問的求解。 靈敏度分析 對(duì)于模型一、二、三，靈敏度很好，模型的準(zhǔn)確性很高。 對(duì)于模型四由于質(zhì)量和體積的制約，使其靈敏度不會(huì)很好，但準(zhǔn)確性較高，因此模型可以使用。6、 模型評(píng)價(jià)、改進(jìn)和推廣6.1模型的評(píng)價(jià)優(yōu)點(diǎn)：l 充分利用了已知數(shù)據(jù)建立模型，使其具有很高的準(zhǔn)確性和可行性l 使用了準(zhǔn)確的算法和適當(dāng)?shù)募僭O(shè)，使模型的準(zhǔn)確性和實(shí)用性到達(dá)統(tǒng)一l 運(yùn)用功能強(qiáng)大的Matlab工具使數(shù)據(jù)處理誤差達(dá)到最小缺點(diǎn)l 由于數(shù)據(jù)較多，沒法使用工具進(jìn)行模型的驗(yàn)證，只能一步一步的精化模型6.2

20、模型的改進(jìn)對(duì)于模型一和三主要是進(jìn)行驗(yàn)證。 對(duì)于模型二斷開的那個(gè)點(diǎn)可以去取別的點(diǎn)進(jìn)行。主要是模型四的改進(jìn)，可以考慮到不同的地點(diǎn)送的貨物進(jìn)行拆分，從而渠道最優(yōu)的解6.3模型的推廣 可充分使用到圖的遍歷和最短路的一系列問題的求解中。7、 參考文獻(xiàn)1.A First Course in Mathenmatical Moderling (Third Edition) Frank R.Giordiano Maurice D.weir William P.Fox2.圖論 任韓。3.數(shù)學(xué)建模案例選集 姜啟源 謝金星4.圖論 第3版 德 迪斯特爾著5.大學(xué)生數(shù)學(xué)建模競(jìng)賽輔導(dǎo)教材 葉其效6.基于matlab 動(dòng)態(tài)

21、規(guī)劃中最短路線的實(shí)現(xiàn)程序 J電腦學(xué)習(xí) 施益昌 鄭賢斌 李自立7.物流配送問題的混沌優(yōu)化算法研究 中央民族大學(xué)學(xué)報(bào)(自然科學(xué)版) 2009年11月第18卷第4期8. Dijkstra 算法在企業(yè)物流運(yùn)輸網(wǎng)絡(luò)中的應(yīng)用 湖南農(nóng)業(yè)大學(xué)學(xué)報(bào)(自然科學(xué)版) 2005年8月第29卷4期附錄附錄1.、表格1.1各貨物號(hào)信息表貨物號(hào)送達(dá)地點(diǎn)重量(公斤)體積(立方米)不超過時(shí)間1132.500.03169：002180.500.03549：003311.180.02409：304261.560.035012：005212.150.030512：006141.720.010012：007171.380.010912

22、：008231.400.042612：009320.700.048112：0010381.330.021910：1511451.100.02879：3012430.950.022810：1513392.560.059512：0014452.280.03019：3015422.850.019010：1516431.700.078210：1517320.250.041212：0018361.790.018412：0019272.450.044512：0020242.930.04209：0021310.800.01089：3022272.250.001812：0023261.570.021012：0

23、024342.800.01039：3025401.140.01559：3026450.680.03829：3027491.350.014410：1528320.520.002012：0029232.910.048712：0030161.200.042912：003111.260.02503221.150.05013331.630.04833441.230.00063551.410.03873660.540.00673770.700.01293880.760.03463992.140.008740101.070.012441111.370.051042122.390.042843130.990.

24、004844141.660.049145150.450.020946162.040.009847171.950.032448182.120.055449193.870.026250202.010.032451211.380.041952220.390.000153231.660.050254241.240.053455252.410.001256261.260.005957270.420.022458281.720.058059291.340.037260300.060.040261310.600.027462322.190.050363331.890.049464341.810.032565

25、351.000.005566361.240.017767372.510.036168382.040.011069391.070.044070400.490.032971410.510.009472421.380.045573431.310.012174441.260.000575450.980.041376461.350.024177472.120.023078480.540.054279491.010.056680501.120.028481250.790.001182462.120.049283322.770.003484232.290.005485200.210.049086251.29

26、0.008887191.120.024988410.900.003889462.380.043490371.420.002091321.010.030092332.510.013393361.170.002094381.820.030895170.330.034596110.300.017297154.430.053698120.240.005699101.380.017510071.980.04931.2 50個(gè)位置點(diǎn)的坐標(biāo)位置點(diǎn)X坐標(biāo)(米)Y坐標(biāo)(米)1918550021445560372705704373567052620995610080143571002522808716025259

27、138452680101193530501178503545126585418513763052001413405532515212559751615365704517141657385188825807519585581652078083552112770856022220088352314765905524779093302544359525261086096352710385105002856597652925809865301565995531939510100321483510365331250109003472801106535153051137536123901141537641

28、0115103813915116103995101205040834512300414930136504213265141454314180142154430301506045109151423546233014500477735145504888514880491157515160508010153251.3相互到達(dá)信息序號(hào)位置點(diǎn)1位置點(diǎn)211321832204245386347428515952106111718127113812149141591016101817107181112191213201225211215221318231319241311251418261416271417

29、281421291522301525311623321723331831341924352022362126372136382117392230402317412431422541432519442529452731462833472922483028493041503126513134523235533223543346553328563440573538583645593627603740613836623927634034644045654144664137674146684243694249704338714448724450734550744542754648764740774844

30、78495079494280504081O1882O2183O261.4 模型二中到達(dá)時(shí)的時(shí)間點(diǎn)到的時(shí)間最大允許的時(shí)間000180.09091130.27061240.55871310.73291.5340.92971.5401.04771.5451.23171.5421.42972.25491.56182.25431.73222.25381.89132.25362.00544272.14724392.32144262.5544212.74544172.87144232.99534323.154163.4424143.6007403.9031附錄2 、MATLAB程序代碼2.1、Dijstra

31、 求解clcclear alla=11000 8250;9185 500;1445 560;7270 570;3735 670;2620 995;10080 1435;10025 2280;7160 2525;13845 2680;11935 3050;7850 3545;6585 4185;7630 5200;13405 5325;2125 5975;15365 7045;14165 7385;8825 8075;5855 8165;780 8355;12770 8560;2200 8835;14765 9055;7790 9330;4435 9525;10860 9635;10385 10

32、500;565 9765;2580 9865;1565 9955;9395 10100;14835 10365;1250 10900;7280 11065;15305 11375;12390 11415;6410 11510;13915 11610;9510 12050;8345 12300;4930 13650;13265 14145;14180 14215;3030 15060;10915 14235;2330 14500;7735 14550;885 14880;11575 15160;8010 15325;%a是各個(gè)點(diǎn)的坐標(biāo)for i=1:51 for j=1:51 t=a(i,:)-

33、a(j,:); c(i,j)=sqrt(t(1)2+t(2)2);%兩點(diǎn)之間的直線距離 endenda=1 3;1 8;2 20;2 4;3 8;3 4;4 2;5 15;5 2;6 1;7 18;7 1;8 12;9 14;9 10;10 18;10 7;11 12;12 13;12 25;12 15;13 18;13 19;13 11;14 18;14 16;14 17;14 21;15 22;15 25;16 23;17 23;18 31;19 24;20 22;21 26;21 36;21 17;22 30;23 17;24 31;25 41;25 19;25 29;27 31;28

34、33;29 22;30 28;30 41;31 26;31 34;32 35;32 23;33 46;33 28;34 40;35 38;36 45;36 27;37 40;38 36;39 27;40 34;40 45;41 44;41 37;41 46;42 43;42 49;43 38;44 48;44 50;45 50;45 42;46 48;47 40;48 44;49 50;49 42;50 40;0 18;0 21;0 26;%通路表b=zeros(51);for i=1:83 b(a(i,1)+1,a(i,2)+1)=1; b(a(i,2)+1,a(i,1)+1)=1;enda

35、=b.*c;for i=1:51 for j=1:51 if a(i,j)=0 a(i,j)=inf; end if i=j a(i,j)=0; end endend w=a;for p=1:51 n=size(w,1); w1=w(p,:); for i=1:n l(i)=w1(i); z(i)=1; end s=; s(1)=1; u=s(1); k=1; while k<n for i=1:n for j=1:k if i=s(j) if l(i)>l(u)+w(u,i) l(i)=l(u)+w(u,i); z(i)=u; end end end end ll=l; for

36、i=1:n for j=1:k if i=s(j) ll(i)=ll(i); else ll(i)=inf; end end end lv=inf; for i=1:n if ll(i)<lv lv=ll(i); v=i; end end s(k+1)=v; k=k+1; u=s(k); endif p=1 a=l; t=z;else a=a;l; t=t;z;endendfor i=1:51 a(i,i)=inf;%把相同的點(diǎn)賦值為無窮大endsave w.txt a -ascii; %保存最小距離save t.txt t -ascii; %保存最小路徑經(jīng)過的點(diǎn)2.2、問題一得求解cl

37、ear allclcformat shortw=數(shù)據(jù)太多省略;p1=7;p2=10;sum=0;w(:,1)=inf;w(:,p1)=inf;w(:,p2)=inf;w(13,16)=inf;w(16,13)=inf;x1=1,p1;x2=p2,1;for i=1:15 s1,t1=min(w(p1,:); s2,t2=min(w(p2,:); sum=sum+s1+s2; w(:,t1)=inf; w(:,t2)=inf; p1=t1; p2=t2; if t1=9|t2=9 disp('到達(dá)24時(shí)所走的距離') disp(sum) T=sum/1000/24+3*i/60;

38、 disp('到24所用的時(shí)間') disp(T) end if t1=t2 x1=x1,t1; x=x1,x2; break; end x1=x1,t1; x2=t2,x2; x=x1,x2;enddisp('順序?yàn)椋?#39;)disp(x)disp('總的路程為：')disp(sum)T=sum/1000/24+3*30/60;disp('總的時(shí)間是：')disp(T)2.3、問題二的2階段求解clear allclcformat shortw=數(shù)據(jù)太多省略;p=1;x=1;sum=0;v=w;w(:,p)=inf;for i=1:

39、10 s,t=min(w(p,:); sum=sum+s; T=sum/1000/24+3*i/60; disp(t,T) w(:,t)=inf; p=t; x=x;t;enddisp('順序?yàn)椋?#39;)disp(x)disp('總的路程為：')disp(sum)T=sum/1000/24+3*30/60;disp('總的時(shí)間是：')disp(T)2.4問題二4階段的解法clcclear allw=inf 5295.49 2182.03 4709.245295.49 inf 3113.46 5714.342182.03 3113.46 inf 388

40、3.844709.24 5714.34 3883.84 inf;disp('第一個(gè)區(qū)域')p=1;x=1;sum=0;v=w;T=0;w(:,p)=inf;for i=1:3 s,t=min(w(p,:); sum=sum+s; T=s/1000/24+T; disp(t,T) T=T+3/60; w(:,t)=inf; p=t; x=x;t;enddisp('順序?yàn)?#39;)disp(x')disp('×總路程是：')disp(sum)disp('總時(shí)間是)disp(T)disp('第二個(gè)區(qū)域')w=inf

41、1780.15 4104.9 5735.68 8234.281780.15 inf 2324.75 3955.53 6454.134104.9 2324.75 inf 1630.78 4847.795735.68 3955.53 1630.78 inf 3217.018234.28 6454.13 4847.79 3217.01 inf;p=1;x=1;v=w;w(:,p)=inf;T=0.6087;for i=1:4 s,t=min(w(p,:); sum=sum+s; T=T+3/60; T=s/1000/24+T; disp(t,T) if(i=1); T=T+3/60; end if(

42、i=4); T=T+3/60*2; end w(:,t)=inf; p=t; x=x;t;enddisp('順序?yàn)?#39;)disp(x')disp('×總路程是：')disp(sum)disp('總時(shí)間是)disp(T)disp('第三個(gè)區(qū)域')w=inf 4719.88 2351.72 3269.39 4323.14719.88 inf 3536.11 2618.44 5507.492351.72 3536.11 inf 917.67 1971.383269.39 2618.44 917.67 inf 2889.05432

43、3.1 5507.49 1971.38 2889.05 inf;x=1 3 5 4 2;T=1.3317;for i=1:4 m=i; s=w(x(i),x(i+1); sum=sum+s; if(i=4) m=m+1; end T=s/1000/24+T; disp(x(i+1),T) T=T+3/60;enddisp('順序?yàn)?#39;)disp(x')disp('×總路程是：')disp(sum)disp('總時(shí)間是)disp(T)disp('第四個(gè)區(qū)域')w=數(shù)據(jù)太多省略;p=1;x=1;v=w;w(:,p)=inf;w

44、(:,12)=inf;T=1.9413;for i=1:10 s,t=min(w(p,:); sum=sum+s; T=s/1000/24+T; disp(t,T) T=T+3/60; w(:,t)=inf; p=t; x=x;t; if i=2 T=T+3/60; end if i=4 T=T+3/60; end if i=7 T=T+3/60; end if i=8 T=T+3/60*2; end disp(p,sum)endsum=sum+v(t,12);disp('順序是：')disp(x',1)disp('總距離是：')disp(sum)T=s

45、um/1000/24+3*30/60;disp('總時(shí)間是：')disp(T)2.5、問題3的初步設(shè)定clcclear allw=;i=1;while i<50 if (w(i,1)=w(i+1,1) w(i,2)=w(i,2)+w(i+1,2); w(i,3)=w(i,3)+w(i+1,3); w(i+1,:)=; i=i-1; end i=i+1;endsave x.txt w -ascii;clcclear allload w.txta=w;for i=1:51 a(i,i)=inf;endload x.txtw=x;p=1;x=0;M=0;V=0;sum=0;v=

46、a;a(:,p)=inf;disp('第一階段')for i=1:50 s,t=min(a(p,:); M=M+w(t-1,2); V=V+w(t-1,3); sum=sum+s; p=t; if(M>50)|(V>1) break; end n=i; x=x;t-1; % disp(t-1,M,V) a(:,t)=inf;endsum=sum+v(p,1);disp('順序?yàn)椋?#39;)disp(x',0)disp('總路程是：')disp(sum)T=sum/1000/24+3*i/60;disp('所用時(shí)間是：')disp(T)disp('第二階段')p=1;x=0;M=0;V=0;a(:,p)=inf;for i=1:50 s,t=min(a(p,:); M=M+w(t-1,2); V=V+w(t-1,3); sum=sum+s; if(M>50)|(V>1) break; end n=n+1; p=t; x=x;t-1; % disp(t-1,M,V) a(:,t)=inf;enddisp(&