《数模论文灾情》word版

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

2、一个最小生成树，然后由模拟退火法算出只用一个组的最短回路（为508.6公里），然后跟据以下原则分块：a尽量把整个回路分为大致的三份；b尽量依据最小生成树的枝干划分整个图。 考虑到右部实在太小，我们将其向左侧稍微扩展了一下。（2） 分为三块之后，问题就转化为一个典型的TSP程序。由模拟退火法算得三个组的走法，得出结果。（3） 跟据结果返回（1）修改，评优标准：使三组中用的最长的时间最短。（4） 最终得出较好的结果.如下: 编号巡视路线长度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对于24h内完成的情况：(1) 问题分析：

4、要求要经过所有的乡村，总共停留时间为69个小时，若是三组的话，那么就只有3×2469=3小时余下,最多还可以走3×35公里，而总路线最小也要508.6公里，故而是不可能的。所以考虑四组的情况，余下27个小时，可以走945公里，是可以接受的。由于停留时间占了大部分，我们就以其为主考虑，分四个区，使得每个区的停留时间差不多。(2) 然后分别求从O点出发经过每一块的最佳路线。(3) 算出结果如下：编号巡视路线长度总时间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人员足够多的巡视方案问题分析：首先求最短时间的上限,离O点最远的点为H，从O到H的最短路线为155公里，算出时间为155/35,再加了停留2小时，共为6.43小时。则每一组巡视的路线不能超过6.43小时，在这一个条件下，使组数尽可能的少。我们按照一定规则得出路线，然后进行微调，使组数达到较少。(具体见下)编程得出路线算法：（1） 先得出最小生成树，然后得出从O点到每一个点的最短离t(i)；（2） 找出其中最长距离，算出从O点沿最短路巡视所需的时间t(i),并求dt=6.43-t(i)；（3） 若dt<

7、1，则这一组只能巡视这一个点，若dt>1，则在余下的点中找到距离O点最远的点，根据条件看这一组能否巡视这一点；（4） 若能巡视则依次判断次远点，第三远点，一直下去，满足总巡视时间不超过t,就让这组巡视这点，直到dt<1,然后再从第二步开始。修改方法：(1) 停留时间：对于下一个访问点,优先考虑加上停留时间之后的”最远点”；(2) 邻近原则：一旦访问某一个点,再下一个点尽量访问离它近的点。得出结果如下：编号巡视路径停留地点所需时间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对巡视路线的影响：若分组方法已经定下了，T，t,V的改变对其没有什么影响。所以T,t,V的改变主要影响的是分组的关状况。由于在现实中要尽快完成所有的巡视，所以分组就要求使其中最长的时间最短，也有一定的均衡性。当v较大(如40)时，T,t的时间一般比走路的时间长很多，所以T,t对分组的影响比较大,当T>>t时，可以只考虑T。当v很小时,则主要考虑走路时间。五 模型检验1 分三组的情况：a 三组中，最长的路线长度为199.4公里，是比较短的；b 三组之间最大相差不过6.2公里，非常均衡；c 三组路线总长度为590.2公里，仅比单个货郎担回