《数模论文灾情》word版.doc

灾区巡视路线分析 四院一队 向为 王瑛 伍微摘要：本问题是一个最短回路问题，我们根据最小生成树和一个最短回路确定了分三组巡视的分块方法，然后由模拟退火法得出最佳路线。由主要的因素停留时间确定了分四组在24小时内巡视完毕的方案。最后由最远点优先原则确定出在最短时间下的最佳巡视方案。一 问题重述(略)二 问题假设对于某些要经过多次的村,乡,只停留一次.三 参数描述T：乡镇停留时间；t：村停留时间；t(i)：从O点出发沿最短路巡视第i点所需的时间；四 模型建立与问题解决我们把这个题归结为一个图论问题。1对于分三组的情况：（1） 问题分析：分为三组时，要求总路线最短，且各组均衡。我们先用maple得出一个最小生成树，然后由模拟退火法算出只用一个组的最短回路（为508.6公里），然后跟据以下原则分块：a尽量把整个回路分为大致的三份；b尽量依据最小生成树的枝干划分整个图。 考虑到右部实在太小，我们将其向左侧稍微扩展了一下。（2） 分为三块之后，问题就转化为一个典型的TSP程序。由模拟退火法算得三个组的走法，得出结果。（3） 跟据结果返回（1）修改，评优标准：使三组中用的最长的时间最短。（4） 最终得出较好的结果.如下: 编号巡视路线长度1O1B3435323133AR29Q30Q28272423N26PO197.52OM252021K2217161151413J18J19L652193.13OC3D7E11G12H12F10F9E84D32O199.42对于24h内完成的情况：(1) 问题分析：要求要经过所有的乡村，总共停留时间为69个小时，若是三组的话，那么就只有32469=3小时余下,最多还可以走335公里，而总路线最小也要508.6公里，故而是不可能的。所以考虑四组的情况，余下27个小时，可以走945公里，是可以接受的。由于停留时间占了大部分，我们就以其为主考虑，分四个区，使得每个区的停留时间差不多。(2) 然后分别求从O点出发经过每一块的最佳路线。(3) 算出结果如下：编号巡视路线长度总时间1O1BA343533313230Q29R29Q28PO158.232.522OM252021K1716172223N242726PO151.420.333O256L19J18I151413H127H7652O202.322.784O256719F10F9E84D3CO158.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） 若dt1，则在余下的点中找到距离O点最远的点，根据条件看这一组能否巡视这一点；（4） 若能巡视则依次判断次远点，第三远点，一直下去，满足总巡视时间不超过t,就让这组巡视这点，直到dtM252019J1314H1413J192025MOH6.432O256L19J131413J19L652O13,146.153OM2521K18I15I1617K2125MO15,166.314O2567E9F12G11E7652O12,115.945O2567E8E9F10F9E7652O8,106.226O2567E11G11E7652OG5.587O2567E9F9E7652O9,F6.148O256L19J18K2125MOJ,186.299OM2521K18I18K2125MOI5.4910OM2521K172223N26PO17,22,236.1211O256L19L652OL,195.6412OM2520212324N26PO20,21,246.1013OM2521K2125MO25,K5.5014O2567E7652O6,7,K6.3815OR31323534A1O33,32,35,346.3216OR29Q30Q28POQ,30,286.1117OP262726N26PO26,27,N6.2318O23D4D32O3,D,45.9919O1A3331R29ROA,33,295.9720O25MO2,5,M5.4021O1BCO1,B,C5.9822OPOROP,R5.324T,t,V对巡视路线的影响：若分组方法已经定下了，T，t,V的改变对其没有什么影响。所以T,t,V的改变主要影响的是分组的关状况。由于在现实中要尽快完成所有的巡视，所以分组就要求使其中最长的时间最短，也有一定的均衡性。当v较大(如40)时，T,t的时间一般比走路的时间长很多，所以T,t对分组的影响比较大,当Tt时，可以只考虑T。当v很小时,则主要考虑走路时间。五 模型检验1 分三组的情况：a 三组中，最长的路线长度为199.4公里，是比较短的；b 三组之间最大相差不过6.2公里，非常均衡；c 三组路线总长度为590.2公里，仅比单个货郎担回路多80公里。2 24小时内巡视的情况：a 每组巡视时间都未超过24小时；b 四组之间最大相差不过1.98小时，非常均衡。3 人员足够多的巡视方案：a 各组巡视时