災(zāi)區(qū)巡視最佳路線選擇問題數(shù)學(xué)建模

1、災(zāi)難最佳巡視路線摘要本文解決的是對全縣的鄉(xiāng)鎮(zhèn)和村莊進(jìn)行災(zāi)情巡視最佳線路的求解問題，多旅行售貨問題。問題一是三個(gè)旅行售貨問題，問題二是四個(gè)旅行售貨問題。我們可以運(yùn)用圖論的知識并且考慮氣均衡性，建立起約束最優(yōu)化線路模型來解決這個(gè)問題。關(guān)鍵詞：Hamilton 圈 多旅行售貨問題 最小生成樹問題今年夏天該縣遭受水災(zāi)。為考察災(zāi)情、組織自救，縣領(lǐng)導(dǎo)決定，帶領(lǐng)有關(guān)部門負(fù)責(zé)人到全縣各鄉(xiāng)（鎮(zhèn)）、村巡視。巡視路線指從縣政府所在地出發(fā)，走遍各鄉(xiāng)（鎮(zhèn)）、村，又回到縣政府所在地的路線。1.若分三組（路）巡視，試設(shè)計(jì)總路程最短且各組盡可能均衡的巡視路線。 2.假定巡視人員在各鄉(xiāng)（鎮(zhèn)）停留時(shí)間T=2小時(shí)，在各村停留時(shí)間t

2、=1小時(shí)，汽車行駛速度V=35公里/小時(shí)。要在24小時(shí)內(nèi)完成巡視，至少應(yīng)分幾組；給出這種分組下你認(rèn)為最佳的巡視路線。 1.問題重述問題1：若分三組（路）巡視，試設(shè)計(jì)總路程最短且各組盡可能均衡的巡視路線圖 問題2：假定巡視人員在各鄉(xiāng)（鎮(zhèn)）停留時(shí)間T=2小時(shí)，在各村停留時(shí)間t=1小時(shí)，汽車行駛速度V=35公里/小時(shí)。要在24小時(shí)內(nèi)完成巡視，至少應(yīng)分幾組；給出這種分組下你認(rèn)為最佳的巡視路線。 問題3：在上述關(guān)于T , t和V的假定下，如果巡視人員足夠多，完成巡視的最短時(shí)間是多少；給出在這種最短時(shí)間完成巡視的要求下，你認(rèn)為最佳的巡視路線。 問題4：若巡視組數(shù)已定(如三組），要求盡快完成巡視，討論T，t

3、和V改變對最佳巡視路線的影響。2.模型的假設(shè)及符號說明2.1模型假設(shè)假設(shè)1：假設(shè)汽車在路上以V勻速行駛，且不停留，不考慮故障，忽略外部因素影響假設(shè)2：巡視過程中除了正常停留外，沒有因其它因素造成時(shí)間延誤假設(shè)3：巡視路線可以重復(fù)假設(shè)4：對于要多次經(jīng)過的鄉(xiāng)(鎮(zhèn))或村只停留一次假設(shè)5：每個(gè)巡視人員只能走自己劃分區(qū)域內(nèi)的路線2.2符號說明G：表示加權(quán)圖Gi：表示子圖V：表示頂點(diǎn)，每一個(gè)鄉(xiāng)(鎮(zhèn))或村看成一個(gè)點(diǎn)E：表示邊，鄉(xiāng)(鎮(zhèn))或村之間的路線w(x，y)：表示權(quán)重，鄉(xiāng)(鎮(zhèn))或村之間的距離S：表示回路路程總和：表示路程均衡度Li：表示每一條子回路T：表示在每個(gè)鄉(xiāng)(鎮(zhèn))停留的時(shí)間I：表示在每個(gè)村停留的時(shí)間T

4、i：表示第i組的巡視時(shí)間V：表示汽車行駛速度Z：表示劃分的區(qū)域數(shù)N：表示鄉(xiāng)(鎮(zhèn))的數(shù)目N：表示村的數(shù)目Ni：表示第i組巡視鄉(xiāng)(鎮(zhèn))的數(shù)目Ni：表示第i組巡視村的數(shù)目M：表示所分的組數(shù)：表示時(shí)間均衡度3.問題分析本文研究的是最佳巡視路線設(shè)計(jì)問題，要求從O點(diǎn)出發(fā)巡視完所有鄉(xiāng)(鎮(zhèn))村后，在回到O點(diǎn)，此問題可以轉(zhuǎn)化為旅行商問題，再設(shè)計(jì)相應(yīng)的算法求解針對問題一：問題一要求設(shè)計(jì)3組巡視總路程最短且盡可能均衡，首先我們通過主觀篩選法將原圖劃分為3個(gè)子圖，每個(gè)子圖頂點(diǎn)數(shù)大約為17個(gè)，相鄰的點(diǎn)劃在一個(gè)子圖中，且盡量使每個(gè)子圖構(gòu)成一個(gè)回路，這樣將原問題轉(zhuǎn)化為單旅行商問題求解針對問題二：問題二在問題一的基礎(chǔ)上加了時(shí)

5、間的限制，在每一個(gè)頂點(diǎn)都有停留時(shí)間，且在24小時(shí)巡視完。通過計(jì)算可得至少分為4組，才可能實(shí)現(xiàn)。和問題一類似我們將原圖劃分為4個(gè)子圖，分別計(jì)算每組的巡視時(shí)間，設(shè)計(jì)每組的巡視路線。針對問題三：問題三T , t和V的假定下，如果巡視人員足夠多，完成巡視的最短時(shí)間，并設(shè)計(jì)最佳路線。首先，我們分析可知巡視H使用的時(shí)間是最長的。那么，設(shè)計(jì)分組時(shí)，其它組巡視的時(shí)間不能超過這一最長時(shí)間。在計(jì)算過程中我們先從距O點(diǎn)遠(yuǎn)的點(diǎn)開始考慮，因?yàn)槿粞惨晻r(shí)間與最小時(shí)間相差較遠(yuǎn)可以考慮順便訪問途徑的鄉(xiāng)、村。運(yùn)用圖論軟件可以很好解決這一問題。針對問題四：巡視組數(shù)已定，要求盡快完成巡視，討論T，t和V改變對最佳巡視路線的影響。我們

6、分別考慮當(dāng)其中兩個(gè)變量不變時(shí)對最佳路線的影響。分為3種情況討論。4.數(shù)據(jù)分析處理4.1理論知識定義 一個(gè)圖G是指一個(gè)二元組(V(G),E(G)，其中：其中元素稱為圖G的頂點(diǎn)。 2) E(G)是頂點(diǎn)集V(G)中的無序或有序的元素偶對組成的集合，即稱為邊集,其中元素稱為邊.定義 圖G的階是指圖的頂點(diǎn)數(shù)|V(G)|, 用來表示；圖的邊的數(shù)目|E(G)|用來表示. 用表示圖，簡記也用來表示邊 設(shè)G=<V，E，W>是加權(quán)的連通圖，對任意邊eÎ，其權(quán)C(e)0。令T=<VT,ET,WT>是G的一棵加權(quán)生成樹，其所有枝上的權(quán)的總和稱為樹T的權(quán)，記為C(T)。一般說來，對于G

7、的不同生成樹T，C(T)也是不同的。可以知道，其中必有一個(gè)最小者，而這正是人們最為感興趣的。因此，給定連通加權(quán)圖G=<V，E，W>，T0=<V，ET0，WT0>是G的加權(quán)生成樹，C(T0)為T0的權(quán)。若對G的任意加權(quán)生成樹T均有C(T0)C(T)，則稱T0是G的最小生成樹。下面給出一種求最小生成樹的方法(破圈法)：設(shè)G是有n個(gè)結(jié)點(diǎn)的連通圖，下面算法產(chǎn)生的是最小生成樹。算法的基本思想先將圖G 的邊按權(quán)的遞減順序排列后, 依次檢驗(yàn)每條邊, 在保持連通的情況下, 每次刪除最大權(quán)邊, 直到余下n- 1 條邊為止。4.2數(shù)據(jù)分析處理我們把53個(gè)鄉(xiāng)(鎮(zhèn))村看作53個(gè)頂點(diǎn)，它們之間的

8、距離為權(quán)重，建立鄰接矩陣，運(yùn)用圖論軟件，可視化如下圖所示運(yùn)用圖論軟件，自動(dòng)選擇最短路徑，可以求得O點(diǎn)到53個(gè)頂點(diǎn)的最短距離及路徑。5問題一的解答5.1模型一的建立確定目標(biāo)函數(shù)公路網(wǎng)圖中，每個(gè)鄉(xiāng)(鎮(zhèn))或村，看作圖中的一個(gè)節(jié)點(diǎn)，公路看作邊，節(jié)點(diǎn)之間的距離看作對應(yīng)邊上的權(quán)，公路網(wǎng)問題就轉(zhuǎn)化為加權(quán)網(wǎng)絡(luò)圖，問題一就轉(zhuǎn)化為在加權(quán)網(wǎng)絡(luò)圖中，從給定點(diǎn)O出發(fā)，尋遍所有頂點(diǎn)再回到O，所得總權(quán)最小，即為多旅行商路線問題。分三組巡視，則需要把圖G分為3個(gè)子圖，在每個(gè)子圖Gi(i=1,2,3)中尋找最佳回路Li(i=1,2,3)。巡視路線要盡可能均衡，因而每組巡視頂點(diǎn)數(shù)要盡量接近。目標(biāo)函數(shù)：是對均衡度的度量，越小表示均

9、衡度越好；S表示總的巡視路線，S越小表示巡回路線越短。這兩個(gè)目標(biāo)函數(shù)不可能同時(shí)達(dá)到最小值，求解時(shí)要兩者兼顧。5.2模型的求解因?yàn)樽钚∩蓸浒珿中所有定點(diǎn)E，相鄰兩點(diǎn)之間的權(quán)重為這兩點(diǎn)之間的距離，它描述了頂點(diǎn)之間的相近程度，故考慮最小生成樹初步分塊。對于巡視組的劃分，我們可以利用原圖的最小生成樹（所選擇的都是權(quán)最小邊）從縣城出發(fā)的最短路生成樹，或者原圖的單旅行商路線等等子圖作為依據(jù)，對邊界進(jìn)行合理劃分后向內(nèi)擴(kuò)展等直觀方法作近似處理分組巡視路線的最優(yōu)解，應(yīng)當(dāng)采用增廣完全圖上的單旅行商路線分段的方法求得但是根據(jù)原題圖的規(guī)模以及邊的稀疏性，用這種方法處理反而將使問題變得更為復(fù)雜，而且考慮到均衡性要求

10、需做的調(diào)整工作也將是大量的，因此，可以采用先適當(dāng)進(jìn)行點(diǎn)的分組，分別求出各組的單旅行商路線，然后在組問進(jìn)行適當(dāng)調(diào)整的方法求得近似解.問題一求解流程圖1.分析問題2.建立數(shù)學(xué)模型3.根據(jù)分區(qū)原則劃3個(gè)分區(qū)4.尋找最小生成樹，求最短回路5.均衡度測試6.調(diào)整分區(qū)7.接受模型算法實(shí)現(xiàn)：求出G中任意兩個(gè)頂點(diǎn)見的最短路，構(gòu)造出完備圖輸入圖G的一個(gè)初始H圈。用對角線完全算法產(chǎn)生一個(gè)初始H圈。隨機(jī)搜索出G中若干個(gè)H圈。對2,3,4步所得每個(gè)H圈，用二邊逐次修正法進(jìn)行優(yōu)化，得到近似最佳H圈。在第5步求出的所有H圈中，找出權(quán)重最小的一個(gè)，即為要找的最佳H圈的近似解。根據(jù)以下4條原則將原圖劃分為3組：1從O點(diǎn)開始分

11、解。2分解的三個(gè)子圖頂點(diǎn)數(shù)盡可能接近17個(gè)。3盡量實(shí)每一個(gè)子圖為連通圖。4盡量使每一個(gè)子圖中與點(diǎn)O的最短路上的點(diǎn)在該子圖內(nèi)，盡量使每個(gè)子圖的點(diǎn)在子圖內(nèi)形成回路。運(yùn)用破圈法得到圖形如下，紅色線條為最小生成樹方案一 H劃在第二組圖二方案二 H劃在第3組圖三I方案一的求解結(jié)果（具體程序見附錄一）表一分組路線每組路程均衡度總路程組O-1-B-34-35-3230-Q-28-27-2423-N-26-P-29-R-3133-A-1-O200.100.147601.4組O-M-25-20-L19-J-18J13-14-H1415I-16-17-22-K-2125-M-O216.6組O-2-5-67-E-1

12、1-G-12F10-F9E-8-4-D-3C-O184.70均衡度均衡度不夠好，于是我們對路線進(jìn)行了一些調(diào)整，把H劃在第III組，這種方法更加合理。II方案二的求解結(jié)果表二分組路線每組路程均衡度總路程組O-1-B-34-35-32-30-Q-28-27-24-23N-26-P-29-R-31-33-A-1-O200.100.04056020組O-M-25-20-L19-J-18-J131415-I-16-17-22-K2125M-O196.8組O-2-5-6-7-E-11-G-12-H-12-F-10-F9-E-8-4-D-3-C-O205.10均衡度均衡度很好，路程S增加不大，故調(diào)整后的方案

13、更優(yōu)。5.3結(jié)果分析問題一中，我們建立雙目標(biāo)最優(yōu)化模型，但是二者不能同時(shí)達(dá)到最小值，對于兩者我們都要兼顧，方案二在路程增加不大情況下，均衡度較好，因而我們選擇方案二。6.問題二的解答6.1模型的建立確定目標(biāo)函數(shù)在各鄉(xiāng)（鎮(zhèn)）停留時(shí)間T=2小時(shí)，在各村停留時(shí)間t=1小時(shí)（不考慮O點(diǎn)），在不考慮在路上時(shí)間情況下滿足（Z為組數(shù)）Z的最小取值為3，若分為3組，每組在路上的時(shí)間為小時(shí)每組只能行走35公里，顯然不可能實(shí)現(xiàn)?？紤]Z值取4，分為4組每組，在路上時(shí)間為小時(shí)，4組總共能行走的路程為公里大于問題一中求解的總路程，故Z=4是可能實(shí)現(xiàn)的。據(jù)此，我們將原圖分為4個(gè)子圖。目標(biāo)函數(shù)：約束條件：6.2模型的求解分

14、組時(shí)要考慮到在鄉(xiāng)和村中停留的時(shí)間和在路程上消耗的時(shí)間，使在近處尋訪的組多訪問幾個(gè)村和鄉(xiāng)，遠(yuǎn)處的組則盡量少訪問些村莊和鄉(xiāng)，從而使各組的總的消耗時(shí)間比較均衡。劃分原則：從O點(diǎn)開始分解分解的三個(gè)子圖頂點(diǎn)數(shù)盡可能接近13個(gè)盡量實(shí)每一個(gè)子圖為連通圖盡量使每一個(gè)子圖中與點(diǎn)O的最短路上的點(diǎn)在該子圖內(nèi)，盡量使每個(gè)子圖的點(diǎn)在子圖內(nèi)形成回路。據(jù)此，劃分如下圖所示運(yùn)用問題一中同樣的算法，可以得到結(jié)果如下(具體程序見附錄二)表三組數(shù)每組路線每組路程每組時(shí)間巡視村鎮(zhèn)數(shù)O-C-B-343532-30-Q29R3133A1-O130.50021.735個(gè)鄉(xiāng)鎮(zhèn)，8 個(gè)村O-P-28-27-26-N23242322171617

15、-K2125M-O157.90022.514 個(gè)鄉(xiāng)鎮(zhèn)10 個(gè)村O-25-6-L20L-19J-18-I1514-H1413-J19-L-6-5-2-0196.00023.604個(gè)鄉(xiāng)鎮(zhèn)，9個(gè)村O-2-3-D-7-E-11-G-12-F10F-9-E-8-4-D-3-2-0181.20021.184個(gè)鄉(xiāng)鎮(zhèn)，8 個(gè)村6.3結(jié)果分析問題二在問題一基礎(chǔ)上加了停留時(shí)間及巡視時(shí)間限制，但算法一樣。至少分為4組，才能在24小內(nèi)完成巡視7.問題三的解答7.1模型的建立確定目標(biāo)函數(shù)問題3中假設(shè)巡視人員足夠多，即分組數(shù)不限，甚至每個(gè)村鎮(zhèn)都能安排一個(gè)巡視人員。那么，最短時(shí)間取決于最遠(yuǎn)那個(gè)村或鎮(zhèn)。分析發(fā)現(xiàn)H是所有點(diǎn)中距

16、離O最遠(yuǎn)的點(diǎn)，則有：即在T=2，t=1,v=35的情況下，完成巡視最短時(shí)間為6.43小時(shí)設(shè)應(yīng)分i組巡視，第i組巡視的鄉(xiāng)(鎮(zhèn))數(shù)目，巡視村的數(shù)目，巡視路程目標(biāo)函數(shù)：確定約束條件每一組的巡視時(shí)間不能大于每一個(gè)頂點(diǎn)都要訪問到，不能遺漏分組數(shù)要盡可能少均衡度不能大于我們規(guī)定上限7.2模型的求解尋找最優(yōu)路徑算法實(shí)現(xiàn)。利用圖論軟件求出每一點(diǎn)到O點(diǎn)最短路徑，進(jìn)而得到任意點(diǎn)返回O點(diǎn)的所需的最短時(shí)間，將此時(shí)間作為各點(diǎn)的權(quán)值；由于每一點(diǎn)都要訪問到，所以每一點(diǎn)都要走到。任取一點(diǎn)，該點(diǎn)權(quán)值的兩倍加上沿途訪問的地點(diǎn)停留時(shí)間之和記為T'，在tH-T'的時(shí)間內(nèi)，看與該點(diǎn)相連的各點(diǎn)中有沒有可以訪問的點(diǎn)，若有，

17、則繼續(xù)；沒有，則返回?；谝陨纤惴?，借助圖論軟件編程得出結(jié)果如下表表四組號訪問路線訪問地點(diǎn)所耗時(shí)間 (小時(shí))1O-1-B-C-01 B C5.9820-1-A-34-35-OA 34 356.033O-R-31-33-A-1-OR 31 335.524O-31-32-30-Q-29-O32 30 Q6.175O-R-29-Q-28-27-26-P-O29 28 275.076O-P-26-N-24-N-26-P-OP 245.547O-P-26-N-23-N-26-P-O26 N 236.228O-P-26-N-23-22-17-K-21-25-M-O22 17 216.129O-M-25-2

18、0-25-M-OM 25 206.1810O-2-5-6-7-6-5-2-O2 5 6 75.9611O-2-3-D-4-D-3-2-O3 D 4612O-2-5-6-7-E-8-E-7-6-5-2-OE 85.8413O-2-5-6-7-E-9-F-10-F-9-E-7-6-5-2-OF 105.7614O-2-5-6-L-19-L-6-5-2-OL 195.6415O-M-25-21-K-18-K-21-25-M-OK 186.0216O-2-5-6-7-E-9-F-12-F-9-E-7-6-5-2-O9 125.8417O-2-5-6-7-E-11-G-13-G-11-E-7-6-5-2

19、-O11 136.0818O-2-5-6-7-E-11-G-13-14-13-G-11-E-7-6-5-2-O145.5619O-2-5-6-7-E-9-F-12-H-12-F-9-E-7-6-5-2-OH6.4220O-2-5-6-L-19-J-19-L-6-5-2-OJ6.121O-M-25-21-K-18-I-18-K-21-25-M-OI5.522O-2-5-6-7-E-11-G-11-E-7-6-5-2-OG5.5823O-M-25-21-K-18-I-15-I-18-K-21-25-M-O15524O-M-25-21-K-17-16-17-K-21-25-M-O164.448問題四

20、的解答8.1模型的建立問題四巡視組數(shù)已定(如三組），要求盡快完成巡視，討論T，t和V改變對最佳巡視路線的影響。在問題三的基礎(chǔ)上，即所分組數(shù)m為定值，要盡快完成巡視，即Ti盡可能小要求m組中最大巡視時(shí)間最小目標(biāo)函數(shù)時(shí)間均衡度8.2模型的求解規(guī)定當(dāng)時(shí)間均衡度時(shí)最佳路線不變最大巡視時(shí)間第e組Tg，最小巡視時(shí)間第f組Tf，I.當(dāng)T，t為定值時(shí)，巡視路線不變V滿足.當(dāng)T，V定值時(shí)，巡視路線不變t滿足.當(dāng)t，V定值時(shí)，巡視路線不變T滿足取m=4,考慮問題二中分四組情況，取結(jié)果為：表五不變量T和t不變T和V不變t和V不變變量范圍當(dāng)T和t為定值時(shí)，若，則最佳巡視路線不變；當(dāng)T和V偉定值時(shí)，若，則最佳路線巡視路

21、線不變；當(dāng)t和V不變時(shí)，若，則最佳巡視路線不變。參考文獻(xiàn)1E.米捏卡美，網(wǎng)絡(luò)和圖的最優(yōu)化算法中國鐵道出版社，北京，19842盧開澄 圖論及應(yīng)用，清華大學(xué)出版社，北京，19813 韓中庚 數(shù)學(xué)建模方法及其應(yīng)用 高等教育出版社 20054謝兆鴻數(shù)學(xué)建模技術(shù)中國水利水電出版社2003.95張紅梅 楊鐵軍 matlab基礎(chǔ)及其應(yīng)用教程附錄一附錄一問題一的求解程序%分區(qū)I的求解程序N=20; %輸入地點(diǎn)個(gè)數(shù)Result0=0.0;%用于記錄最小的權(quán)值和C=eye(N);for i=1:N for j=1:NC(i,j)=inf;endendfor i=1:NC(i,i)=0;end%輸入相關(guān)信息C(1,

22、2)=10.1; C(1,3)=6.0;C(1,4)=9.9;C(1,7)=12.9;C(2,6)=10.5; C(2,11)=12.1;C(2,12)=15.2;C(3,4)=5.9;C(3,8)=10.3;C(4,8)=12.2;C(4,15)=17.6;C(5,6)=10.5;C(5,9)=7.9;C(5,16)=13.2;C(6,10)=7.8;C(7,8)=8.6;C(7,12)=1.9;C(7,13)=9.2;C(8,14)=7.4;C(8,15)=11.5;C(9,16)=8.9; C(10,11)=7.9;C(10,16)=18.2;C(11,17)=8.3;C(12,17)=

23、7.2;C(13,14)=7.3;C(13,19)=8.1;C(14,19)=19;C(14,20)=20.3;C(15,20)=8.2;C(17,18)=7.7;C(18,19)=10.3;C(19,20)=14.9;for i=1:N-1for j=i+1:NC(j,i)=C(i,j);endendfor i=1:NC(i,i)=0;endR=1 4 15 20 19 18 17 11 10 16 9 5 6 2 12 7 13 14 8 3;%隨便輸入一個(gè)環(huán)路%下面求哈密頓圈for i=1:N-1for j=i+2:Nif C(R(i),R(j)=0 && C(R(i),

24、R(j)<inf for m=i+1:jfor n=m+2:N if C(R(m),R(n)=0 && C(R(m),R(n)<inf && C(R(i),(m)<inf && C(R(j),(n)<inf && C(R(i),(n)<inf && C(R(j),(m)<inf &&(C(R(i),R(j)+C(R(m),R(n)<C(R(i),(m)+C(R(j),(n)|(C(R(i),R(j)+C(R(m),R(n)<C(R(i),R(n)+C(

25、R(j),R(m) k=R(m); R(m)=R(j); R(j)=k; %交換得到總權(quán)值更小的哈密頓圈 end end end else continue; end endendR=1 4 15 20 19 18 17 11 10 16 9 5 6 2 12 7 13 14 8 3;for i=1:N-1 j=i+1;Result0=Result0+C(R(i),R(j);endResult0=Result0+C(R(j),R(1)+C(1,3)+C(3,4)-9.9;fprintf('路徑為：');for i=1:N if i=2 fprintf('3 4 '

26、;);elsefprintf('%d ',R(i);endendfprintf('n最小的路徑和為:%3.2fn',Result0);路徑為：1 3 4 15 20 19 18 17 11 10 16 9 5 6 2 12 7 13 14 8 3 最小的路徑和為:200.10對應(yīng)路徑為：O-1-B-34-35-32-30-Q-28-27-24-23-N-26-P-29-R-31-33-A-1-O%分區(qū)II的求解程序N=15; %輸入地點(diǎn)個(gè)數(shù)Result0=0.0;%用于記錄最小的權(quán)值和C=eye(N);for i=1:N for j=1:N C(i,j)=inf

27、; endendfor i=1:N C(i,i)=0;end%輸入相關(guān)信息C(1,2)=7.8; C(1,3)=6.5;C(2,3)=7.9; C(2,6)=4.1;C(3,4)=5.5;C(3,7)=8.3;C(4,7)=7.2;C(5,6)=10.1;C(5,8)=6.7;C(6,8)=9.8;C(6,9)=9.2;C(7,10)=8.1;C(8,11)=6.8;C(9,10)=8.2;C(9,12)=8.2; C(10,12)=15.8;C(10,13)=9.8;C(11,12)=11.8;C(12,13)=16.4;C(12,14)=8.8;C(13,15)=8.6;C(14,15)=

28、15;for i=1:N-1 for j=i+1:N C(j,i)=C(i,j); endendfor i=1:N C(i,i)=0;endR=1 2 6 5 8 11 12 14 15 13 10 9 7 4 3;%隨便輸入一個(gè)環(huán)路%下面求哈密頓圈for i=1:N-1 for j=i+2:N if C(R(i),R(j)=0 && C(R(i),R(j)<inf for m=i+1:j for n=m+2:N if C(R(m),R(n)=0 && C(R(m),R(n)<inf && (C(R(i),R(j)+C(R(m),R(

29、n)<C(R(i),(m)+C(R(j),(n)|(C(R(i),R(j)+C(R(m),R(n)<C(R(i),R(n)+C(R(j),R(m) % && m=j k=R(m); R(m)=R(j); R(j)=k; %交換得到總權(quán)值更小的哈密頓圈 end end end else continue; end endendR=1 3 4 7 10 13 15 14 12 11 8 5 6 2;for i=1:N-2 j=i+1; Result0=Result0+C(R(i),R(j);endResult0=Result0+C(R(j),R(1)+8.2*2;fpr

30、intf('路徑為：');for i=1:N-1 if i=5 fprintf('10 9 10 '); else fprintf('%d ',R(i); endendfprintf('n最小的路徑和為:%3.2fn',Result0);對應(yīng)路徑為：25-20-L-19-J-18-J-13-14-15-I-16-17-22-K-21-25上面的程序是對圖中一個(gè)哈密頓圈求得的局部最短路徑之和（采用局部優(yōu)化思想）第二部分的最短路徑及其和如下：（再加上O-M-25及14-H 這兩段路的兩倍即可）從而，最終的路徑為：O-M-25-20-L

31、-19-J-18-J-13-14-H-14-15-I-16-17-22-K-21-25-M-O全局最短路徑之和為：133.20+（9.9+19.8+12.0）*2=216.6%分區(qū)III的求解程序N=11;Result0=0.0;%用于記錄最小的權(quán)值和C=eye(N);for i=1:N for j=1:N C(i,j)=inf; endendfor i=1:N C(i,i)=0;endC(1,2)=8.2; C(1,3)=11.5;C(2,4)=8.3; C(2,5)=4.8;C(3,5)=7.8;C(4,6)=9.7; C(4,7)=11.3;C(5,7)=8.2;C(6,8)=7.3;C

32、(7,8)=15.1; C(7,9)=12.7;C(8,10)=7.2;C(9,11)=20.4; C(10,11)=8.0;for i=1:N-1 for j=i+1:N C(j,i)=C(i,j); endendfor i=1:N C(i,i)=0;endR=1 2 4 6 8 10 8 11 9 7 5 3;%隨便輸入一個(gè)環(huán)路%下面求哈密頓圈for i=1:N-1 for j=i+2:N if C(R(i),R(j)=0 && C(R(i),R(j)<inf for m=i+1:j for n=m+2:N if C(R(m),R(n)=0 && C(

33、R(m),R(n)<inf && (C(R(i),R(j)+C(R(m),R(n)<C(R(i),R(m)+C(R(j),R(n)|(C(R(i),R(j)+C(R(m),(R(n)<C(R(i),R(n)+C(R(j),R(m) k=R(m); R(m)=R(j); R(j)=k; %交換得到總權(quán)值更小的哈密頓圈 end end end else continue; end endendR=1 2 4 6 8 10 11 9 7 5 3;for i=1:N-1 j=i+1; Result0=Result0+C(R(i),R(j);endResult0=Res

34、ult0+C(R(j),R(1);fprintf('路徑為：');for i=1:N fprintf('%d ',R(i);endfprintf('n最小的路徑和為:%3.2fn',Result0);對應(yīng)路徑為：O-2-5-6-7-E-8-4-D-3-C-O 上面的程序是對圖中一個(gè)哈密頓圈求得的局部最短路徑之和（采用局部優(yōu)化思想）這個(gè)第三部分的最短路徑及其和如下：（再加上一段固定的路徑（從E經(jīng)11、G、12、F、10、F、9,再到E）之和即可）從而，最終的路徑為：O-2-5-6-7-E-11-G-12-F-10-F-9-E-8-4-D-3-C-O

35、全局最短路徑之和為：109.30+（14.2+6.8+7.8+12.2+10.5*2+5.6+7.8）=184.70附錄二問題二的求解程序說明：由于問題二中劃分四個(gè)區(qū)域 算法一樣，只是鄰接矩陣不同，未了避免重復(fù) ，只附錄第I組的程序，每組求解結(jié)果 將會詳細(xì)呈現(xiàn)。分區(qū)I的求解程序N=14; %輸入地點(diǎn)個(gè)數(shù)Result0=0.0;%用于記錄最小的權(quán)值和V=35; %巡視汽車行駛速度T=2; %鄉(xiāng)鎮(zhèn)逗留時(shí)間t=1; %村逗留時(shí)間C=eye(N);for i=1:N for j=1:N C(i,j)=inf; endendfor i=1:N C(i,i)=0;end%輸入相關(guān)信息C(1,2)=6.0;

36、C(1,3)=11.5;C(1,6)=12.9;C(2,3)=11.2;C(2,4)=5.9;C(2,5)=10.3; C(3,4)=11.0;C(4,5)=12.2; C(4,8)=17.6; C(5,6)=8.6;C(5,7)=7.4;C(5,8)=11.5;C(6,9)=1.9;C(6,10)=9.2;C(7,10)=7.3;C(7,11)=20.3;C(7,14)=19;C(8,11)=8.2; C(9,12)=7.2;C(10,14)=8.1;C(11,14)=14.9;C(12,13)=7.7;C(13,14)=10.3;for i=1:N-1 for j=i+1:N C(j,i)

37、=C(i,j); endendfor i=1:N C(i,i)=0;endR=1 3 4 8 11 14 13 12 9 6 10 7 5 2 1;%為最佳的路徑for i=1:size(R,2)-1 j=i+1; Result0=Result0+C(R(i),R(j);endtime=Result0/V+T*5+t*8; %巡視所用的總時(shí)間fprintf('路徑為：');for i=1:size(R,2) fprintf('%d ',R(i);endfprintf('n巡視過程訪問了 5 個(gè)鄉(xiāng)鎮(zhèn)，8 個(gè)村莊 ！n');fprintf('

38、巡視總路程為%2.3fn',Result0);fprintf('巡視所用的總時(shí)間為:%3.2fn',time);I分區(qū)II分區(qū)求解程序N=15; %輸入地點(diǎn)個(gè)數(shù)Result0=0.0;%用于記錄最小的權(quán)值和V=35; %巡視汽車行駛速度T=2; %鄉(xiāng)鎮(zhèn)逗留時(shí)間t=1; %村逗留時(shí)間C=eye(N);for i=1:N for j=1:N C(i,j)=inf; endendfor i=1:N C(i,i)=0;end%輸入相關(guān)信息C(1,2)=10.1;C(1,3)=19.8;C(2,4)=12.1;C(2,6)=10.5; C(3,7)=14.2;C(3,8)=12.

39、0;C(4,5)=7.9; C(5,6)=7.8;C(5,12)=18.2;C(6,7)=10.5;C(7,8)=8.8;C(7,9)=7.9;C(7,12)=13.2;C(8,10)=7.8; C(9,10)=9.1;C(9,12)=8.9;C(9,13)=10.0;C(10,11)=4.1;C(11,13)=10.1;C(11,14)=9.8;C(13,14)=6.7;C(14,15)=6.8;for i=1:N-1 for j=i+1:N C(j,i)=C(i,j); endendfor i=1:N C(i,i)=0;endR=1 2 4 5 6 7 9 12 9 13 14 15 14

40、 11 10 8 3 1;%為最佳的路徑for i=1:size(R,2)-1 j=i+1; Result0=Result0+C(R(i),R(j);endtime=Result0/V+T*4+t*10; %巡視所用的總時(shí)間fprintf('路徑為：');for i=1:size(R,2) fprintf('%d ',R(i);endfprintf('n巡視過程訪問了 4 個(gè)鄉(xiāng)鎮(zhèn)，10 個(gè)村莊 ！n');fprintf('巡視所用的總時(shí)間為:%3.2fn',time);II分區(qū)III分區(qū)求解程序N=14; %輸入地點(diǎn)個(gè)數(shù)Result0=0.0;%用于記錄最小的權(quán)值和V=35; %巡視汽車行駛速度T=2; %鄉(xiāng)鎮(zhèn)逗留時(shí)間t=1; %村逗留時(shí)間C=eye(N);for i=1:N for j=1:N C(i,j)=inf; endendfor i=1:N C(i,i)=0;end%輸入相關(guān)信息C(1,2)=8.2;C(2,3)=8.3; C(3,4)=9.7;C(4,5)=11.8; C(5,6)=5.5;C(5,7)=7.2;C(6,7)=8.3;C(7,8)=8.1;C(8,9)