1、第九屆西安電子科技大學(xué)數(shù)學(xué)建模競(jìng)賽暨全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽選拔賽題目A (B)題密封號(hào)2010年5月4日密封號(hào)2010年5月4日通信工程學(xué)院第 隊(duì)隊(duì)員1隊(duì)員2隊(duì)員3姓名鄧曉光譚正中劉春燕班級(jí)送貨路線設(shè)計(jì)問(wèn)題1、問(wèn)題重述現(xiàn)今社會(huì)網(wǎng)絡(luò)越來(lái)越普及，網(wǎng)購(gòu)已成為一種常見(jiàn)的消費(fèi)方式，隨之物流行業(yè) 也漸漸興盛，每個(gè)送貨員需要以最快的速度及時(shí)將貨物送達(dá)，而且他們往往一人 送多個(gè)地方，請(qǐng)?jiān)O(shè)計(jì)方案使其耗時(shí)最少?，F(xiàn)有一快遞公司，庫(kù)房在圖1中的。點(diǎn)，一送貨員需將貨物送至城市內(nèi)多處，請(qǐng)?jiān)O(shè)計(jì)送貨方案，使所用時(shí)間最少。該地形圖的示意圖見(jiàn)圖1,各點(diǎn)連通信息見(jiàn)表3,假定送貨員只能沿這些連通線路行走，而不能走其它任何路線。各件貨

2、物 的相關(guān)信息見(jiàn)表1, 50個(gè)位置點(diǎn)的坐標(biāo)見(jiàn)表2。假定送貨員最大載重50公斤，所帶貨物最大體積1立方米。送貨員的平均 速度為24公里/小時(shí)。假定每件貨物交接花費(fèi)3分鐘，為簡(jiǎn)化起見(jiàn)，同一地點(diǎn)有 多件貨物也簡(jiǎn)單按照每件3分鐘交接計(jì)算?，F(xiàn)在送貨員要將100件貨物送到50個(gè)地點(diǎn)。請(qǐng)完成以下問(wèn)題。.若將130號(hào)貨物送到指定地點(diǎn)并返回。設(shè)計(jì)最快完成路線與方式。給出 結(jié)果。要求標(biāo)出送貨線路。.假定該送貨員從早上8點(diǎn)上班開(kāi)始送貨，要將130號(hào)貨物的送達(dá)時(shí)間不 能超過(guò)指定時(shí)間，請(qǐng)?jiān)O(shè)計(jì)最快完成路線與方式。要求標(biāo)出送貨線路。.若不需要考慮所有貨物送達(dá)時(shí)間限制（包括前30件貨物），現(xiàn)在要將100 件貨物全部送到指定地

3、點(diǎn)并返回。設(shè)計(jì)最快完成路線與方式。要求標(biāo)出送貨線路， 給出送完所有快件的時(shí)間。由于受重量和體積限制，送貨員可中途返回取貨?？刹豢紤]中午休息時(shí)間。問(wèn)題分析送貨路線問(wèn)題可以理解為：已知起點(diǎn)和終點(diǎn)的圖的遍歷問(wèn)題的合理優(yōu)化的路線設(shè)計(jì)。圖的遍歷問(wèn)題的指標(biāo)：路程和到達(dá)的時(shí)間，貨物的質(zhì)量和體積，以及最大可以負(fù)載的質(zhì)量和體積。在路線的安排問(wèn)題中，考慮所走的路程的最短即為最合理的優(yōu)化指標(biāo)。對(duì)于問(wèn)題二要考慮到所到的點(diǎn)的時(shí)間的要求是否滿足題意即采用多次分區(qū)域的假設(shè)模型從而找出最優(yōu)的解對(duì)于問(wèn)題三則要考慮到體積和質(zhì)量的雙重影響，每次到達(dá)后找到達(dá)到最大的體積和質(zhì)量的點(diǎn)然后返回，再依次分析各個(gè)步驟中可能存在的不合理因素達(dá)到

4、模型的進(jìn)一步合理優(yōu)化得到最合理的解。模型假設(shè)與符號(hào)說(shuō)明、模型的假設(shè)、到同一地點(diǎn)的貨物要一次拿上，即不考慮再以后又經(jīng)過(guò)時(shí)再帶些貨物、要求達(dá)到不超過(guò)的時(shí)間不包括此次在該點(diǎn)交易的時(shí)間。、所用的距離數(shù)據(jù)都精確到米而時(shí)間則精確到、同一地點(diǎn)有多件貨物也簡(jiǎn)單按照每件3 分鐘交接計(jì)算。、符號(hào)說(shuō)明符號(hào)囚(ij)符號(hào)說(shuō)明送貨點(diǎn)的稀號(hào)從。開(kāi)始函”。的總的路程從口開(kāi)始醺耳。的生的B寸間從,治到j(luò)的最短路程送貨員的平均速度從白開(kāi)始到t的所用最理面間到達(dá)可以帶的最暑的貨物的質(zhì)量到達(dá)i可以帶的最大的貨物物攜一次可以摭帶的最多貨物的總高質(zhì)量一次可以攜帶的最多貨物的總高質(zhì)鬢v=W其中i , j=1、2、350 并且 M=50k

5、g模型的建立我們?yōu)榱饲蟪龈鱾€(gè)點(diǎn)的之間的最短的路徑，使用Dijstra算法求解。Dijkstra算法是圖論中非常有名的一個(gè)算法。圖采用鄰接矩陣的形式描述，w (i,j )表示結(jié)點(diǎn)i到結(jié)點(diǎn)j間的最短距離,如果沒(méi)有直接連通，則為無(wú)窮大，計(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 o另外再引入一個(gè)標(biāo)記數(shù)組dn,其中在某一步dk表示當(dāng)前從i到k

6、 的較短路徑，dk的初值為w (i , k)0整個(gè)算法過(guò)程如下：1、在t中選擇一個(gè)dk最小的結(jié)點(diǎn)k,將k并入s,并從t中去掉，如果 t為什則轉(zhuǎn)到3 ;2、用k結(jié)點(diǎn)和t中其余結(jié)點(diǎn)進(jìn)行一遍比較，如果 didk+mki,則用dk+mki取代原來(lái)的di，重復(fù)1 ;3、算法結(jié)束，此時(shí)dk中保存的就是從i到k結(jié)點(diǎn)的最短路徑。算法就以這樣非常簡(jiǎn)單的形式完成了求解，時(shí)間復(fù)雜度是O(n),確定了從i到其余各結(jié)點(diǎn)的最短路徑。模型的求解根據(jù)算法和相鄰的點(diǎn)的距離可以用dijkstra求出任意兩點(diǎn)的最短路徑。1 相鄰的點(diǎn)的距離使用循環(huán)的結(jié)構(gòu)求出1-50 各個(gè)點(diǎn)之間的最短距離。程序1 見(jiàn)附錄可以求出w和aa 為最短路徑是

7、的所過(guò)的的地點(diǎn)如從。開(kāi)始到其余 50個(gè)點(diǎn)的 a(0)= 0 7 4 8 3 15 1 18 12 14 18 13 13 1821 12 23 21 0 24 22 0 29 17 31 19 0 31 30 25 22 26 23 28 31 38 21 40 3627 34 37 43 38 41 36 41 40 46 42 40要從。點(diǎn)到16點(diǎn)則要先到23即0-23-16要從。點(diǎn)到23點(diǎn)則要先到17即 0-17-23-16要從。點(diǎn)到17點(diǎn)則要先到21即0-21-17-23-16 而?？梢灾苯拥?1 所以從 0 到 16 的最優(yōu)路徑是0-21-17-23-16 最短的距離是w( 0,16

8、) =7493m模型二 對(duì)于問(wèn)題一的求解模型的建立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)注的）目標(biāo)函數(shù)是：T=MW- V+o x 30約束條件是:必須全部遍歷回到0點(diǎn)即求出從。出發(fā)遍歷這圖的21個(gè)點(diǎn)的并回到o的最短的距離要距離最短則每一步也要最短，即從O開(kāi)始找最短的點(diǎn)到達(dá)后繼續(xù)找未遍歷的最短的點(diǎn)則可求出最短的距離本題要求出回到。點(diǎn)則可以看到兩個(gè)開(kāi)始最短遍歷的點(diǎn)在某點(diǎn)重合即可完成其中共經(jīng)過(guò)21個(gè)點(diǎn)，運(yùn)送

9、30件貨物該30件貨物“50kg v=n*所以可以一次把貨物攜帶進(jìn)行運(yùn)送。由T與W關(guān)系可知要使所用的時(shí)間最小即所走的距離最短。即3SOO最短的遍歷。模型的求解由圖可以明顯得出距離 。最近的點(diǎn)是21點(diǎn)和26點(diǎn)。由于32點(diǎn)到38點(diǎn)的距離小于32點(diǎn)到16點(diǎn)的距離為使從21點(diǎn)出來(lái)的線遍歷右下的點(diǎn)完后再和 26點(diǎn)出 來(lái)的匯合則安排32點(diǎn)到35點(diǎn)斷開(kāi)。有程序2 （附錄）可得：013112132321314334141643615175381618639172174018238421924943202610452127114922順序和Columns 1 through 13I758134362&14132

10、1CqIluiuie 14 thr&ugh 2322192QIS15171112IQ1總的路程為：S. 3787+004總的時(shí)間是：3.7411遍歷節(jié)點(diǎn)路線是:0-2-4-40-45-49-42-43-38-36-39-27-31-26-0最優(yōu)的路線是：0-2-3-0-45-42-49-42-43-38-36-27-39-27-31-26-0總路程是：W=53787m最優(yōu)時(shí)間是：T=模型三一對(duì)于問(wèn)題二的求解模型的建立由第一個(gè)模型建立的可以求出到達(dá)24時(shí)所用的時(shí)間是：軻達(dá)2時(shí)所走的距黃U51，。十口口4到所用的時(shí)間0390可知到24點(diǎn)的時(shí)間是：t(24)二由表可知必須在9點(diǎn)之前把貨物送到24點(diǎn)即

11、t(24)1故模型一不適用于問(wèn)題二 的求解.由下圖3可知：圖3.考慮時(shí)間的點(diǎn)的位置由于右邊的點(diǎn)的地點(diǎn)需要的時(shí)間要比左邊的早，所以先分兩個(gè)階段，即先走左邊后走右邊即先走圈內(nèi)的元素由程序 3 （附錄）可得：從。出發(fā)經(jīng)過(guò) 13、18、24、26、27、31、34、39、40 到達(dá) 4552673162792942432821383110401145而到13點(diǎn)時(shí)必須在9點(diǎn)之前到達(dá)但1,到45點(diǎn)時(shí)必須在9點(diǎn)半之前到達(dá)而 故分成兩個(gè)階段不成功，所以分四個(gè)階段，求出各個(gè)階段的最短距離和到達(dá)時(shí)的時(shí)間即可。目標(biāo)函數(shù):約束條件是:tj=Wi +v+2 toT到個(gè)點(diǎn)的時(shí)間最大值模型的求解圖個(gè)階段的圈圖對(duì)四個(gè)階段分別

12、求出到達(dá)的時(shí)間，由程序 4 （附錄）可知分4個(gè)階段1.從0出發(fā)經(jīng)過(guò)13、18到24滿足t1的條件31821342423133444054534254944323826、27、32、36、39 回到。II幡序?yàn)?目的暗程為二1. 101 04-0 0 1總的口寸E足：O. CJ0S7故路線為：0-18-13-24 2.從24出發(fā)經(jīng)過(guò)31、34、40到45滿足t順回為I N 34 乒行的睹程為：1. 9S63e-*-UQ-l 忌啊日寸聞急：3317|故路線為：24-31-34-40-45 3.從45出發(fā)經(jīng)過(guò)38、42、43到49滿足t啡柿為1 13542總的跖耨沌：#703*4-0 04總附時(shí)向足

13、J9413所以路線為：45-42-49-43-38 4. 從 38 出發(fā)經(jīng)過(guò) 14、16、17、21、23、1036827113972652141762393231614滿足t4雁席為二總的餡程為：揖 7912ct0,04總的附間是；3.9130故路線為：38-36-27-39-27-3-32-16-14-21-0所以總的遍歷點(diǎn)順序是：0-4-40-45-42-49-43-38-36-27-39-26-2-14-0總時(shí)間是T=總距離是W=57912m最優(yōu)路線是：0-49-42-43-38-36-27-39-27-3-32-23-16-14-21-0到每個(gè)點(diǎn)的時(shí)間見(jiàn)附錄模型四一對(duì)于問(wèn)題三的求解.

14、模型的建立本題中要遍歷所有的50個(gè)點(diǎn)但由于M總= 147kg, v總=巾3而M50kg,V13故應(yīng)該以M50k酢口 丫仔判斷的標(biāo)準(zhǔn)到達(dá)的最遠(yuǎn)的點(diǎn)后返回目標(biāo)函數(shù)：約束條件：M50kg,V13 模型的求解由。開(kāi)始逐漸依次找出最近的點(diǎn)后再找出離該點(diǎn)最近的點(diǎn)直到不滿足約束條件。見(jiàn)程序5 （附錄）J50C圖5.改進(jìn)后的遍歷圖1第一階段順序用J031373936 3S 3532231721息的路程為：7122+004總的用詞息：L. 73C1.第二階段N順序?yàn)楹?C o L muri1 t! Kr c ugH 1. 31JSSO40j G 710o01S1312C o L Lutaiu 1 1 Hul 0

15、-ig.lv 21 16434249忌日勺晤代為u3. 4.85Oe-i-Q04 短白勺白寸間早： 1. 5351.第三階段順序力E1 t Hr ouigh 1302 419Z 后29230 N 日 33 4E 當(dāng)日 4441o l-umn s ithiraiiEh. I. 9374T45N。15口后的;蹈程為J：1,5 9366+0 057* 53994.第四階段順亨為I C 4250%的造偃力： ,1, 總的時(shí)間是： 2112模型的優(yōu)化由于總的L =148kg卜:v=/所以最少要分四個(gè)階段，但由于每次不可能剛好帶滿 50kg而如果只要3次則 最多只能帶150kg只比原貨物多2kg所以不可能

16、是三次就把貨物帶完，最少要四 次。故只需要把上述的模型進(jìn)行數(shù)據(jù)處理就好了。過(guò)程如下：1.由于到21點(diǎn)時(shí)M=49 V若走過(guò)14則M大于了 50故直接從21點(diǎn)返回。第一次存貨物 順序?yàn)镾0263127393638 3B 322317210總韻路程為： 2. 7122e+OOd 總的時(shí)間是士1, ?301最優(yōu)路線為：0-26-3-38-35-32-23-17-21-0走的距離 W=27122m花費(fèi)的時(shí)間T=2.若按程序給出的從13到8的路線是而當(dāng)為13-11-12-8時(shí)更短故修改之；同時(shí) 到達(dá)40后如果選擇34則45的周圍全被遍歷過(guò)。到45后M=,V壞滿足要求，故從40到34后沿21-26返回。第2

17、次用培物順耳為士Co Iwiltle 1 ttircuEh 13Q181312118316710 S 14Colunuvs 13 Through_ 21IC434249SO4034Q總總J 程為：8. 4850eT004總射時(shí)河是，4.C3E54最優(yōu)路線為：0-3-5-38-43-42-49-50-40-45-36-21-0走得距離是：W=83220所用的時(shí)間是T=3.當(dāng)?shù)竭_(dá)45點(diǎn)時(shí)若要去20點(diǎn)放貨物的話則需要遍歷許多已經(jīng)遍歷過(guò)的地點(diǎn),故從45點(diǎn)沿36-21-0返回第3次帶貨物順序?yàn)椋篊clwnns I through 130241925292230283346 到 4441Columns 1

18、4 through 1937474520150息的路程為：1. 5936 e+005總的時(shí)訶是E1 539gl最優(yōu)路線為: 0-26-3-22-30-28-33-46-48-44-4-45-36-21-0所走的距離為：W=128970m所用的時(shí)間是：T=4.只余下了 5個(gè)點(diǎn)，所以由圖可知第&次帚貨物咂序?yàn)椋?4250總的路程為：L9347t+005總的時(shí)間是：8.2112路線為:0-26-3-22-20-2-5-2-4-3-8-12-13-18-O總路程是：W= 171510nW用的時(shí)間是T=由上面的四個(gè)階段可以知道該問(wèn)的 最優(yōu)路線是： 0-26-3-38-35-32-23-6-23-32-3

19、5-38-43-42-49-50-40-45-36-20-28-33-46-4 8-44-4-45-36-20-2-5-2-4-3-8-12-13-18-0總路程是：W= 171510m所用的時(shí)間是T=5、模型的分析誤差分析:對(duì)于模型一是使用了精確地 Dijkstra 算法，故誤差可以忽略不計(jì)對(duì)于模型二假定了 32到38點(diǎn)的斷開(kāi)存在一定的誤差，但相對(duì)于斷開(kāi)其余 的幾點(diǎn)得到的數(shù)值要小，故該模型可以使用。對(duì)于模型三，由于分區(qū)域的方法有很多，故不可避免的存在些許誤差，但由于區(qū)域越多，路程越多，故選擇分成 4個(gè)區(qū)域最合適；分成的四個(gè)不同 的時(shí)間的到達(dá)區(qū)域比較緊密故按照時(shí)間的不同劃分了四個(gè)區(qū)域，從而大大

20、的消除了誤差，此模型可以使用。對(duì)于模型四的誤差比較大，由于未考慮貨物的拆分可能會(huì)有一定的影響同 時(shí)由于4個(gè)階段的劃分也是有一定的不確定性故誤差存在。對(duì)于該模型簡(jiǎn)化 了考慮的條件，僅以M和V為判斷標(biāo)準(zhǔn)，雖對(duì)準(zhǔn)確性存在挑戰(zhàn)，但該模型相 對(duì)與其他的分類有明顯的優(yōu)越性。故該模型適用于該問(wèn)的求解。靈敏度分析對(duì)于模型一、二、三，靈敏度很好，模型的準(zhǔn)確性很高。對(duì)于模型四由于質(zhì)量和體積的制約，使其靈敏度不會(huì)很好，但準(zhǔn)確性較高，因此模型可以使用。6、模型評(píng)價(jià)、改進(jìn)和推廣模型的評(píng)價(jià)優(yōu)點(diǎn)：充分利用了已知數(shù)據(jù)建立模型，使其具有很高的準(zhǔn)確性和可行性 使用了準(zhǔn)確的算法和適當(dāng)?shù)募僭O(shè)，使模型的準(zhǔn)確性和實(shí)用性到達(dá)統(tǒng)一運(yùn)用功能強(qiáng)

21、大的Matlab工具使數(shù)據(jù)處理誤差達(dá)到最小缺點(diǎn)由于數(shù)據(jù)較多，沒(méi)法使用工具進(jìn)行模型的驗(yàn)證，只能一步一步的精化模型模型的改進(jìn)對(duì)于模型一和三主要是進(jìn)行驗(yàn)證。對(duì)于模型二斷開(kāi)的那個(gè)點(diǎn)可以去取別的點(diǎn)進(jìn)行。主要是模型四的改進(jìn)，可以考慮到不同的地點(diǎn)送的貨物進(jìn)行拆分，從而渠道最優(yōu)的解模型的推廣可充分使用到圖的遍歷和最短路的一系列問(wèn)題的求解中。參考文獻(xiàn)First Course in Mathenmatical Moderling （Third Edition）Frank Maurice William圖論任韓。數(shù)學(xué)建模案例選集姜啟源 謝金星 TOC o 1-5 h z 圖論 第 3 版 德 迪斯特爾著大學(xué)生數(shù)學(xué)建

22、模競(jìng)賽輔導(dǎo)教材葉其效基于 matlab 動(dòng)態(tài)規(guī)劃中最短路線的實(shí)現(xiàn)程序J 電腦學(xué)習(xí)施益昌 鄭賢斌 李自立物流配送問(wèn)題的混沌優(yōu)化算法研究中央民族大學(xué)學(xué)報(bào)（ 自然科學(xué)版）2009年 11月第18卷第4期Dijkstra 算法在企業(yè)物流運(yùn)輸網(wǎng)絡(luò)中的應(yīng)用湖南農(nóng)業(yè)大學(xué)學(xué)報(bào)（ 自然科學(xué)版） 2005 年 8月第29卷 4期附錄附錄 1. 、表格各貨物號(hào)信息表貨物號(hào)送達(dá)地點(diǎn)重里（公斤）體積（立方米）不超過(guò)時(shí)間1139: 002189: 003319: 3042612: 0052112: 0061412: 0071712: 0082312: 0093212: 00103810: 1511459: 3012431

23、0: 15133912: 0014459: 30154210: 15164310: 15173212: 00183612: 00192712: 0020249: 0021319: 30222712: 00232612: 0024349: 3025409: 3026459: 30274910: 15283212: 00292312: 00301612: 003113223333443553663773883994010411142124313441445154616471748184919502051215222532354245525562657275828592960306131623263

24、33643465356636673768386939704071417242734374447545764677477848794980508125824683328423852086258719884189469037913292339336943895179611971598129910100750個(gè)位置點(diǎn)的坐標(biāo)位置點(diǎn)X坐標(biāo)（米）丫坐標(biāo)（米）191855002144556037270570437356705262099561008014357100252280871602525913845268010119353050117850354512658541851376305200141340

25、553251521255975161536570451714165738518882580751958558165207808355211277085602222008835231476590552477909330254435952526108609635271038510500285659765292580986530156599553193951010032148351036533125010900347280110653515305113753612390114153764101151038139151161039951012050408345123004149301365042132

26、6514145431418014215443030150604510915142354623301450047773514550488851488049115751516050801015325相互到達(dá)信息序號(hào)位直點(diǎn)1位置點(diǎn)21132183220424538634742851595210611171812711381214914159101610181710718111219121320122521121522131823131924131125141826141627141728142129152230152531162332172333183134192435202236212637213

27、638211739223040231741243142254143251944252945273146283347292248302849304150312651313452323553322354334655332856344057353858364559362760374061383662392763403464404565414466413767414668424369424970433871444872445073455074454275464876474077484478495079494280504081O1882O2183O26模型二中到達(dá)時(shí)的時(shí)間點(diǎn)到的時(shí)間最大允許的時(shí)間0001

28、8113124131344045424943383642743942642141742343241641440附錄2、MATLABS序代碼、Dijstra 求解clcclear alla=11000 8250;9185500;1445 560;7270570;3735 670;2620 995;10080 1435;10025 2280;71602525;13845 2680;11935 3050;7850 3545;6585 4185;7630 5200;13405 5325;2125 5975;153657045;14165 7385;8825 8075;5855 8165;780 835

29、5;12770 8560;2200 8835;14765 9055;77909330;4435 9525;10860 9635;10385 10500;565 9765;2580 9865;1565 9955;9395 10100;1483510365;1250 10900;7280 11065;15305 11375;12390 11415;6410 11510;13915 11610;951012050;8345 12300;4930 13650;13265 14145;14180 14215;3030 15060;10915 14235;233014500;7735 14550;885

30、14880;11575 15160;8010 15325;%a是各個(gè)點(diǎn)的坐標(biāo)for i=1:51for j=1:51t=a(i,:)-a(j,:);c(i,j尸sqrt(t(1)A2+t(22);%兩點(diǎn)之間的直線距離endend TOC o 1-5 h z a=13;1 8;2 20;2 4;3 8;3 4;42;5 15;5 2;6 1;718;7 1;8 12;9 14;910;10 18;107;1112;1213;1225;12 15;13 18;13 19;1311;14 18;14 16;1417;14 21;15 22;1525;16 23;1723;1831;1924;2022

31、;21 26;21 36;21 17;2230;23 17;24 31;2541;25 19;25 29;2731;28 33;2922;3028;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

32、i=1:83b(a(i,1)+1,a(i,2)+1)=1;b(a(i,2)+1,a(i,1)+1)=1;enda=b.*c;for i=1:51for j=1:51if a(i,j)=0a(i,j)=inf;endif i=ja(i,j)=0;endendendw=a;for p=1:51n=size(w,1);w1=w(p,:);for i=1:nl(i)=w1(i);z(i)=1;ends=;s(1)=1;u=s(1);k=1;while kl(u)+w(u,i)l(i)=l(u)+w(u,i);z(i)=u;endendendendll=l;for i=1:nfor j=1:kif i=

33、s(j)ll(i)=ll(i);elsell(i)=inf;endendendlv=inf;for i=1:nif ll(i)lvlv=ll(i);v=i;endends(k+1)=v;k=k+1;u=s(k);endif p=1a=l;t=z;elsea=a;l;t=t;z;endendfor i=1:51a(i,i)=inf;% 把相同的點(diǎn)賦值為無(wú)窮大endsavea -ascii ; % 保存最小距離savet -ascii ; % 保存最小路徑經(jīng)過(guò)的點(diǎn)、問(wèn)題一得求解clear allclcformat shortw=數(shù)據(jù)太多省略；p1=7;p2=10;sum=0;w(:,1)=inf;

34、w(:,p1)=inf;w(:,p2)=inf;w(13,16)=inf;w(16,13)=inf;x1=1,p1;x2=p2,1;for i=1:15s1,t1=min(w(p1,:);disp( 總的時(shí)間是： )s2,t2=min(w(p2,:);sum=sum+s1+s2;w(:,t1)=inf;w(:,t2)=inf;p1=t1;p2=t2;if t1=9|t2=9disp( 到達(dá)24時(shí)所走的距離 )disp(sum)T=sum/1000/24+3*i/60;disp( 到 24所用的時(shí)間 )disp(T)endif t1=t2x1=x1,t1;x=x1,x2;break ;endx1

35、=x1,t1;x2=t2,x2;x=x1,x2;enddisp( 順序?yàn)椋?)disp(x)disp( 總的路程為： )disp(sum)T=sum/1000/24+3*30/60;disp(T)、問(wèn)題二的2階段求解clear allclcformat shortw=數(shù)據(jù)太多省略；p=1;x=1;sum=0;v=w;w(:,p)=inf;for i=1:10s,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;end TOC o 1-5 h z disp( 順序?yàn)椋?)disp(x)disp( 總

36、的路程為： )disp(sum)T=sum/1000/24+3*30/60;disp( 總的時(shí)間是： )disp(T)4階段的解法disp(sum)clc clear allw=infinfinfinf;disp( 第一個(gè)區(qū)域 )p=1;x=1;sum=0;v=w;T=0;w(:,p)=inf;for i=1:3s,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)?)disp(x)disp( x總路程是：disp( 總時(shí)間是)disp(T)disp( 第二個(gè)區(qū)域 )w

37、=infinfinfinfinf;p=1;x=1;v=w;w(:,p)=inf;T=;for i=1:4s,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;endif (i=4);T=T+3/60*2;endw(:,t)=inf;p=t;endx=x;t;enddisp( 順序?yàn)?)disp(x)disp( x總路程是：)disp(sum)disp( 總時(shí)間是)disp(T)disp( 第三個(gè)區(qū)域 )w=infinfinfinfinf;x=1 3 5 4 2;T=;for i=1:4m=i;s=w

38、(x(i),x(i+1);sum=sum+s;if (i=4)m=m+1;endT=s/1000/24+T;disp(x(i+1),T)T=T+3/60;enddisp( 順序?yàn)?)T=T+3/60;disp(x)disp( x總路程是：)disp(sum)disp( 總時(shí)間是)disp(T)disp( 第四個(gè)區(qū)域 )w=數(shù)據(jù)太多省略；p=1;x=1;v=w;w(:,p)=inf;w(:,12)=inf;T=;for i=1:10s,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=

39、2T=T+3/60;endif i=4if i=7T=T+3/60;endif i=8T=T+3/60*2;enddisp(p,sum)endsum=sum+v(t,12); TOC o 1-5 h z disp( 順序是： )disp(x,1)disp( 總距離是： )disp(sum)T=sum/1000/24+3*30/60;disp( 總時(shí)間是： )disp(T)、問(wèn)題 3 的初步設(shè)定clcclear allw=；i=1;while i50)|(V1)i=i+1;endsave w -ascii ;clcclear allloada=w;for i=1:51a(i,i)=inf;end

40、loadw=x;p=1;x=0;M=0;V=0;sum=0;v=a;a(:,p)=inf;disp( 第一階段 )for i=1:50s,t=min(a(p,:);M=M+w(t-1,2);V=V+w(t-1,3);sum=sum+s;p=t;break ;endn=i;x=x;t-1;% disp(t-1,M,V) a(:,t)=inf;endsum=sum+v(p,1); TOC o 1-5 h z disp( 順序?yàn)椋?)disp(x,0)disp( 總路程是： )disp(sum)T=sum/1000/24+3*i/60;disp( 所用時(shí)間是： )disp(T)disp( 第二階段

41、)p=1;x=0;M=0;V=0;a(:,p)=inf;for i=1:50s,t=min(a(p,:);M=M+w(t-1,2);V=V+w(t-1,3);sum=sum+s;if (M50)|(V1)break ;break ;endendbreak ;endn=n+1;p=t;x=x;t-1;% disp(t-1,M,V)a(:,t)=inf;end TOC o 1-5 h z disp( 順序?yàn)椋?)disp(x,0)disp( 總路程是： )disp(sum)T=sum/1000/24+3*i/60;disp( 所用時(shí)間是： )disp(T)disp( 第三階段 )p=1;x=0;M

42、=0;V=0;a(:,p)=inf;for i=1:50-ns,t=min(a(p,:);M=M+w(t-1,2);V=V+w(t-1,3);sum=sum+s;if (M50)|(V1)p=t;x=x;t-1;% disp(t-1,M,V)a(:,t)=inf;n=n+1;endsum=sum+v(p,1); TOC o 1-5 h z disp( 順序?yàn)椋?)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-ns,t=min(a(p,:);M