《數(shù)模論文災(zāi)情》word版

1、災(zāi)區(qū)巡視路線(xiàn)分析 四院一隊(duì) 向?yàn)?王瑛 伍微摘要：本問(wèn)題是一個(gè)最短回路問(wèn)題，我們根據(jù)最小生成樹(shù)和一個(gè)最短回路確定了分三組巡視的分塊方法，然后由模擬退火法得出最佳路線(xiàn)。由主要的因素停留時(shí)間確定了分四組在24小時(shí)內(nèi)巡視完畢的方案。最后由最遠(yuǎn)點(diǎn)優(yōu)先原則確定出在最短時(shí)間下的最佳巡視方案。一 問(wèn)題重述(略)二 問(wèn)題假設(shè)對(duì)于某些要經(jīng)過(guò)多次的村,鄉(xiāng),只停留一次.三 參數(shù)描述T：鄉(xiāng)鎮(zhèn)停留時(shí)間；t：村停留時(shí)間；t(i)：從O點(diǎn)出發(fā)沿最短路巡視第i點(diǎn)所需的時(shí)間；四 模型建立與問(wèn)題解決我們把這個(gè)題歸結(jié)為一個(gè)圖論問(wèn)題。1對(duì)于分三組的情況：（1） 問(wèn)題分析：分為三組時(shí)，要求總路線(xiàn)最短，且各組均衡。我們先用maple得出

2、一個(gè)最小生成樹(shù)，然后由模擬退火法算出只用一個(gè)組的最短回路（為508.6公里），然后跟據(jù)以下原則分塊：a盡量把整個(gè)回路分為大致的三份；b盡量依據(jù)最小生成樹(shù)的枝干劃分整個(gè)圖。 考慮到右部實(shí)在太小，我們將其向左側(cè)稍微擴(kuò)展了一下。（2） 分為三塊之后，問(wèn)題就轉(zhuǎn)化為一個(gè)典型的TSP程序。由模擬退火法算得三個(gè)組的走法，得出結(jié)果。（3） 跟據(jù)結(jié)果返回（1）修改，評(píng)優(yōu)標(biāo)準(zhǔn)：使三組中用的最長(zhǎng)的時(shí)間最短。（4） 最終得出較好的結(jié)果.如下: 編號(hào)巡視路線(xiàn)長(zhǎng)度1O>1>B>34>35>32>31>33>A>R>29>Q>30>Q>28

3、>27>24>23>N>26>P>O197.52O>M>25>20>21>K>22>17>16>1>15>14>13>J>18>J>19>L>6>5>2193.13O>C>3>D>7>E>11>G>12>H>12>F>10>F>9>E>8>4>D>3>2>O199.42對(duì)于24h內(nèi)完成的情況：(1) 問(wèn)題分析：

4、要求要經(jīng)過(guò)所有的鄉(xiāng)村，總共停留時(shí)間為69個(gè)小時(shí)，若是三組的話(huà)，那么就只有3×2469=3小時(shí)余下,最多還可以走3×35公里，而總路線(xiàn)最小也要508.6公里，故而是不可能的。所以考慮四組的情況，余下27個(gè)小時(shí)，可以走945公里，是可以接受的。由于停留時(shí)間占了大部分，我們就以其為主考慮，分四個(gè)區(qū)，使得每個(gè)區(qū)的停留時(shí)間差不多。(2) 然后分別求從O點(diǎn)出發(fā)經(jīng)過(guò)每一塊的最佳路線(xiàn)。(3) 算出結(jié)果如下：編號(hào)巡視路線(xiàn)長(zhǎng)度總時(shí)間1O>1>B>A>34>35>33>31>32>30>Q>29>R>29>Q&g

5、t;28>P>O158.232.522O>M>25>20>21>K>17>16>17>22>23>N>24>27>26>P>O151.420.333O>2>5>6>L>19>J>18>I>15>14>13>H>12>7>H>7>6>5>2>O202.322.784O>2>5>6>7>1>9>F>10>F>9&g

6、t;E>8>4>D>3>C>O158.821.543人員足夠多的巡視方案問(wèn)題分析：首先求最短時(shí)間的上限,離O點(diǎn)最遠(yuǎn)的點(diǎn)為H，從O到H的最短路線(xiàn)為155公里，算出時(shí)間為155/35,再加了停留2小時(shí)，共為6.43小時(shí)。則每一組巡視的路線(xiàn)不能超過(guò)6.43小時(shí)，在這一個(gè)條件下，使組數(shù)盡可能的少。我們按照一定規(guī)則得出路線(xiàn)，然后進(jìn)行微調(diào)，使組數(shù)達(dá)到較少。(具體見(jiàn)下)編程得出路線(xiàn)算法：（1） 先得出最小生成樹(shù)，然后得出從O點(diǎn)到每一個(gè)點(diǎn)的最短離t(i)；（2） 找出其中最長(zhǎng)距離，算出從O點(diǎn)沿最短路巡視所需的時(shí)間t(i),并求dt=6.43-t(i)；（3） 若dt<

7、1，則這一組只能巡視這一個(gè)點(diǎn)，若dt>1，則在余下的點(diǎn)中找到距離O點(diǎn)最遠(yuǎn)的點(diǎn)，根據(jù)條件看這一組能否巡視這一點(diǎn)；（4） 若能巡視則依次判斷次遠(yuǎn)點(diǎn)，第三遠(yuǎn)點(diǎn)，一直下去，滿(mǎn)足總巡視時(shí)間不超過(guò)t,就讓這組巡視這點(diǎn)，直到dt<1,然后再?gòu)牡诙介_(kāi)始。修改方法：(1) 停留時(shí)間：對(duì)于下一個(gè)訪(fǎng)問(wèn)點(diǎn),優(yōu)先考慮加上停留時(shí)間之后的”最遠(yuǎn)點(diǎn)”；(2) 鄰近原則：一旦訪(fǎng)問(wèn)某一個(gè)點(diǎn),再下一個(gè)點(diǎn)盡量訪(fǎng)問(wèn)離它近的點(diǎn)。得出結(jié)果如下：編號(hào)巡視路徑停留地點(diǎn)所需時(shí)間1O>M>25>20>19>J>13>14>H>14>13>J>19>20&g

8、t;25>M>OH6.432O>2>5>6>L>19>J>13>14>13>J>19>L>6>5>2>O13,146.153O>M>25>21>K>18>I>15>I>16>17>K>21>25>M>O15,166.314O>2>5>6>7>E>9>F>12>G>11>E>7>6>5>2>O12,115.

9、945O>2>5>6>7>E>8>E>9>F>10>F>9>E>7>6>5>2>O8,106.226O>2>5>6>7>E>11>G>11>E>7>6>5>2>O>G5.587O>2>5>6>7>E>9>F>9>E>7>6>5>2>O9,F6.148O>2>5>6>L>19>J&g

10、t;18>K>21>25>M>OJ,186.299O>M>25>21>K>18>I>18>K>21>25>M>OI5.4910O>M>25>21>K>17>22>23>N>26>P>O17,22,236.1211O>2>5>6>L>19>L>6>5>2>OL,195.6412O>M>25>20>21>23>24>N>26&

11、gt;P>O20,21,246.1013O>M>25>21>K>21>25>M>O25,K5.5014O>2>5>6>7>E>7>6>5>2>O6,7,K6.3815O>R>31>32>35>34>A>1>O33,32,35,346.3216O>R>29>Q>30>Q>28>P>OQ,30,286.1117O>P>26>27>26>N>26>P&

12、gt;O26,27,N6.2318O>2>3>D>4>D>3>2>O3,D,45.9919O>1>A>33>31>R>29>R>OA,33,295.9720O>2>5>M>O2,5,M5.4021O>1>B>C>O1,B,C5.9822O>P>O>R>OP,R5.324T,t,V對(duì)巡視路線(xiàn)的影響：若分組方法已經(jīng)定下了，T，t,V的改變對(duì)其沒(méi)有什么影響。所以T,t,V的改變主要影響的是分組的關(guān)狀況。由于在現(xiàn)實(shí)中要盡快完成所有的巡視，所以分組就要求使其中最長(zhǎng)的時(shí)間最短，也有一定的均衡性。當(dāng)v較大(如40)時(shí)，T,t的時(shí)間一般比走路的時(shí)間長(zhǎng)很多，所以T,t對(duì)分組的影響比較大,當(dāng)T>>t時(shí)，可以只考慮T。當(dāng)v很小時(shí),則主要考慮走路時(shí)間。五 模型檢驗(yàn)1 分三組的情況：a 三組中，最長(zhǎng)的路線(xiàn)長(zhǎng)度為199.4公里，是比較短的；b 三組之間最大相差不過(guò)6.2公里，非常均衡；c 三組路線(xiàn)總長(zhǎng)度為590.2公里，僅比單個(gè)貨郎擔(dān)回