《数模论文灾情》word版

《《数模论文灾情》word版》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、灾区巡视路线分析四院一队向为王瑛伍微摘要：本问题是一个最短回路问题，我们根据最小生成树和一个最短回路确定了分三组巡视的分块方法，然后由模拟退火法得出最佳路线。由主要的因素——停留时间确定了分四组在24小时内巡视完毕的方案。最后由最远点优先原则确定出在最短时间下的最佳巡视方案。一．问题重述(略)二．问题假设对于某些要经过多次的村,乡,只停留一次.三．参数描述T：乡镇停留时间；t：村停留时间；t(i)：从O点出发沿最短路巡视第i点所需的时间；四．模型建立与问题解决我们把这个题归结为一个图论问题。1．对于分三组的情况：（1）问题分析：分为三组时

2、，要求总路线最短，且各组均衡。我们先用maple得出一个最小生成树，然后由模拟退火法算出只用一个组的最短回路（为508.6公里），然后跟据以下原则分块：a．尽量把整个回路分为大致的三份；b．尽量依据最小生成树的枝干划分整个图。考虑到右部实在太小，我们将其向左侧稍微扩展了一下。（2）分为三块之后，问题就转化为一个典型的TSP程序。由模拟退火法算得三个组的走法，得出结果。（3）跟据结果返回（1）修改，评优标准：使三组中用的最长的时间最短。（4）最终得出较好的结果.如下:编号巡视路线长度1O>1>B>34>35>32>31>33>A>R>29>

3、Q>30>Q>28>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．对于24h内完成的情况：(1)问题分析：要求要经过所有的乡村，总共停留时间为69个小时，若是三组的话，那么就只有3×24－69=3小时余下,最多还可以走3×35公里，而总路线最小也要508.6公里，故而是不可能的。所以考虑四组的情况，余下27个小时，可以

4、走945公里，是可以接受的。由于停留时间占了大部分，我们就以其为主考虑，分四个区，使得每个区的停留时间差不多。(2)然后分别求从O点出发经过每一块的最佳路线。(3)算出结果如下：编号巡视路线长度总时间1O>1>B>A>34>35>33>31>32>30>Q>29>R>29>Q>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、>5>6>7>1>9>F>10>F>9>E>8>4>D>3>C>O158.821.543．人员足够多的巡视方案问题分析：首先求最短时间的上限,离O点最远的点为H，从O到H的最短路线为155公里，算出时间为155/35,再加了停留2小时，共为6.43小时。则每一组巡视的路线不能超过6.43小时，在这一个条件下，使组数尽可能的少。我们按照一定规则得出路线，然后进行微调，使组数达到较少。(具体见下)编程得出路线算法：（1）先得出最小生成树，然后得出从O点到每一个点的最短离t(i)；（2）找出其中最长距离，算出从O点沿最短路巡视所需的时间t(i)

6、,并求dt=6.43-t(i)；（3）若dt<1，则这一组只能巡视这一个点，若dt>1，则在余下的点中找到距离O点最远的点，根据条件看这一组能否巡视这一点；（4）若能巡视则依次判断次远点，第三远点，一直下去，满足总巡视时间不超过t,就让这组巡视这点，直到dt<1,然后再从第二步开始。修改方法：(1)停留时间：对于下一个访问点,优先考虑加上停留时间之后的”最远点”；(2)邻近原则：一旦访问某一个点,再下一个点尽量访问离它近的点。得出结果如下：编号巡视路径停留地点所需时间1O>M>25>20>19>J>13>14>H>14>13>J>19>2

7、0>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.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,

8、F6.148O>2>5>6>L>19>J>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