灾情巡视路线模型论文

题目：灾情巡视路线学号：2012070231姓名：施亚男班级：12 级数学教育一 问题重述1.1背景分析： 今年夏天该县遭受水灾。为考察灾情、组织自救，县领导决定，带领有关部 门负责人到全县各乡（镇）、村巡视。巡视路线指从县政府所在地出发，走遍各 乡（镇）、村，又回到县政府所在地的路线。1.2 需要解决的问题：1）若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。2）假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=l小 时，汽车行驶速度V=35公里/小时。要在24小时内完成巡视，至少应分几组； 给出这种分组下你认为最佳的巡视路线。3）在上述关于T , t和V的假定下，如果巡视人员足够多，完成巡视的最 短时间是多少；给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路线。4）若巡视组数已定（如三组），要求尽快完成巡视，讨论T，t和V改变对最 佳巡视路线的影响。一、模型假设2.1 假设地面情况一切正常，不会影响汽车行驶速度；2.2 假设第二次经过的乡镇，不计算停留时间；2.3 对于同一乡镇，如果某一小组停留过，其他小组经过时不计算停留时间2.4 假设经过邻县村不做任何停留；2.5 假设县镇府所在地灾情不派小组人员巡视。二、符号说明ci第i个小组所走路程a衡量均衡度（a越小，均衡度越好；反之，均衡度越差）T巡视一个乡（镇）所花时间T = 2 ht巡视一个村所花时间t = 1hV汽车的行驶速度V二35km / hti第i个小组巡视所用时间Smax最短路径树中从O点出发到所有点距离中的最大距离Sj最短路径树中点j距出发点的距离（j = O, A, BN, P, R,1,235）T min完成所有巡视所用的最短时间Ts巡视完所规定的点外的剩余时间n小组巡视乡镇的个数m小组巡视村得个数三、问题分析本文研究的是考察灾情最佳巡视线路设计的问题，准确合理的路线设计对灾 情巡视救治起着重要作用。为很好的解决此问题，为此我们建立了网络图模型。对于问题一，题目要求在分三组巡视的情况下，使总路程最短且各小组所走 路程均衡。先考虑分区，我们将得出的最小生成树图形和最短路树图形，进行比 较并找出其公共部分。分组要求尽量不破坏最短生成树和最小生成树，所以我们 以公共部分为界限，将此网络图分为三组。为使每小组所走路程均衡，我们引入 了均衡度a。它表示最大路程和最小路程的差值与最大路程的比值。a越小，表 示均衡度越好。以总路程最短和均衡度最小作为目标函数建立多目标规划模型， 利用哈密顿原理得出各组的巡回路线，并对其分析修正求得各组最优巡回路线。对于问题二，要求在 24 小时内完成所有巡视。 通过第一问的结果，求得在 分三组的情况下所用的平均时间T二3（17T + 35t + 6035：8）二28.8h大于24小时， 所以我们先考虑分四组。我们的分组原则为：1、每子区域所分得的点近似相等； 2、尽量使每一个子区域连通；3、使每一个子区域中与点 O 的最短路上的点在该 区域内。根据以上分组原则将整个图大致划分为四个子图，同样利用哈密顿算法 求得在相对均衡的情况每个小组的最短路径和所需时间。如果部分时间大于 24 小时，则调整分组方式；若所有时间均大于 24 小时再考虑多加一组。直到找到 相对均衡条件下的最佳路线。对于问题三，考虑在人员足够多的情况下，求出最短的巡视时间。假设一个 小组只巡视一个点的情况下，则去巡视离O点最远的点所花时间最长。我们以巡 视小组中所耗时间最长的小组所用时间作为这次整个巡视的最短时间。要使这次 巡视时间最短，则要求去巡视离O点最远的点所花时间最小，由图一可知，离O 点最远的点为H，所以就以巡视H所花时间作为T 。当此小组只巡视H时，T min min最小。在不超过T的情况下，根据其他小组的剩余时间确定沿途是否巡视其他min点。其中巡视原则为：当一组人员巡视完规定点后时，在剩余时间允许的情况 下，优先考虑原巡视点附近而距离O较远的点，最大限度使用剩余时间，主要 考虑原则。按照此原则，逐个巡视，直至巡视完所有点。对于问题四，若巡视组数已定，则每个小组的最短路径就已确定， T 、t、V 改变只影响的是整个的巡视时间。要求尽快完成巡视，即巡视时间要尽可能小。巡视时间包括到巡视点的行驶时间和在巡视点的停留时间。行驶时间主要取决于 速度V，而停留时间由T、t决定。所以此问题讨论的是当T、t、V改变时对巡 视时间的影响，即对T、t、V的灵敏度分析。四、数据处理由题目可知，共有53个乡镇，即在网络图赋权网络图G（ V，E, W）中共 有53个点.其中V = v ,v , v （n = 53）表示图G的53个节点，E = e 表示12 nij相关联的两点i, j的边集，W二w 表示相关联两点i, j间的权值。ij定义决策变量 r ：ij1表示i,j两点相关联r = ij 0表示i.j两点不相关其中相关联表示i, j两点之间有权值，不相关表示i, j之间没有权值。将这些点和权值生成图G的矩阵，对于不相关的两点权值作为无穷大处理 （数据.txt）。用MATLAB编写程序，得出该网络图G的最小生成树。再运用迪克 斯特拉算法求出出发点O到各点的最短距离，即网络图的最短路径树。画出的两 种图形如图 1 所示。路径图（路程）五、模型建立与求解6.1 问题一6.1.1 模型建立 通过问题一的分析，建立多目标规划模型 (1)三组巡视的总路线最短：mini=12)巡视路线尽量均衡：.max(c ) - min(c )mm a = i-max(c )i我们设当a 0.15时，认为均衡度比较好。 综上得出目标函数：min Z c 0.15，我们认为均衡度不好，需要对分组进行修正。通过结果发现第二小组所行走的路程比较多，而第三小组行走路程较短，我 们考虑将分区2 中离分区1 较近但距1 较远的 11， G， 12 三个点划到第三分区 中，而分区的区域不变。在此情况下，重新利用哈密顿算法编程得到三个小组的 巡视路线如下表 1：小组路线行走路 程ci第一组O, P ,26 ,N ,23, 24 ,27 ,28 ,Q, 29, Q ,30, 32 ,31, R ,A, 33, 35 ,34 ,B, 1 ,O206.8km第二组0,M,25,21,K,22,17 ,16 ,I ,18 ,I ,15 ,H ,14 ,13 ,J ,19 ,L ,20, 25, M, O216.6km第三组O ,2 ,5 ,6, 7 ,E, 9 ,F ,10, F ,12 ,G ,11, E , & 4, D ,3 ,C,O186.4km则三组所行走的总路程：C =工 c = 609.8km i i=1此分区下的均衡度：max(c ) - min(c ) c - c= ii =3 = 0.13max(c )ci2由a &(1J 111/z*45n料豪iff. ftJ丿？J11-AV1 tl fA14严！V,/di、十96.2问题二6.2.1模型准备：根据第一问的结果得出在分三组的情况下，各小组所用时间：第一组：t 二 6T + 13t + 206.8 二 30.9h1V第二组：t 二 6T + lit +二 29.2h2V第三组：t = 5T + lit +186.4 二 26.3h3V通过以上数据观察可知，分三组时不能满足题目要求，所以我们先考虑分四组。6.2.2 模型建立根据问题二分析，建立多目标规划模型。 要求设计最佳巡视路线，即使总路程最短，并且所用时间相对均衡，得出目 标函数：厂min f cVii=1min a约束条件：每个小组巡视所用时间均不超过 24 小时，即t = mT + nt + i 0.15，我们认为此分组结果不够合理，需要重新调整分组方 式。通过观察分析，将 2分区中的村 28 划分到 1 中，同时将 3 分区中的村11划分到4 中,同样利用matlab编程求得各组的最短巡视路线和所用时间，如下表2：组号巡视点寻访 个数巡视路径总路程 长耗时长 （小时）第一组A B Q R 1 2829 30 31 3233 34 3513O,1,B,A,34,35,33,31,32,30,Q,28,Q,29,R,O142.121.06第二组K M N P 1617 21 22 2324 25 26 2713O,P,26,27,26,N,24,23,22,17,16,17,K,21,25,M,O152.121.35第三组G H I J L 1213 14 15 1819 2012O,M,6,L,19,J,13,G,12,H,14,15,I,18,J,19,20,25,M,O196.522.61第四组C D E F 2 3 45 6 7 8 9 10 1114O,2,5,6,7,E,11,G12,F,10,F,9,E,8,4,D,3,C,O186.423.33根据表中数据可知，所有时间均小于 24 小时，对时间进行均衡度分析为：i = 4 i = 0.097 10 . 1第一组 一第二组 一第三组 第四组图4*县政剧用在地o0 乡()A,8.Ro H 1.2.3S公 at1 26 6.3 问题三由最短树路径树可知，从O点到所有点距离中的最大距离S = 77.5km,从 maxO 点出发到点 H 。同时计算出其所用时间：T 二minSmax + 2 = 6.4286hv即完成此次巡视所用的最短时间。在不超过T .的情况下，其他小组巡视点j的剩余时间：min2ST = T （j +1）s min V其中,fT巡视一个乡（镇）所花时间t，二彳t巡视一个村所花时间下面对剩余时间的利用进行讨论：当T 1时，直接返回县政府；s当1 T 2时，巡视一个村；s当 2 T 3时，巡视两个村或一个乡（镇）；s当 3 T 4 时，巡视三个村或一个村和一个乡（镇）；s当 4 T 5时，巡视四个村、两个个乡（镇）或两个村和一个乡（镇）；s当5 T 6，情况不存在。s根据对T的讨论和我们的巡视原则，逐个除去已巡视的点，直到所有点巡视s完结束，最终求得需要 23组。各小组巡视情况如下表 3：小 组路线巡视点剩余 时间兼巡 视点最终路线10,2,5,6,7,E,9,F,12,HH0无0,2,5,6,7,E,9,F,12,H20,2,5,6,L,19,J,13,14141.27130,2,5,6,L,19,J,13,1430,M,25,21,K,18,I,15151.43180,M,25,21,K,18,I,1540,2,5,6,7,E,9,F,12121.5890,2,5,6,7,E,9,F,1250,2,5,6,7,E,9,F,10101.6680,2,5,6,7,E, & E9,F,1060,2,5,6,7,E,11,GG0.85无0,2,5,6,7,E,11,G70,M,25,21,K,18,II0.94无0,M,25,21,K,18,I80,M,25,21,K,17,16161.98170,M,25,21,K,17,1690,2,5,6,7,E,11112.23E0,2,5,6,7,E,11100,2,5,6,7,E,9,FF1.2870,2,5,6,7,E,9,F110,2,5,6,L,19,JJ1.33190,2,5,6,L,19,J120,P,26,N,23,22222.63K0,P,26,N,23,22,K,22130,P,26,N,24242.9023,260,P,26,N,24,23,24140,M,25,21213.17M,250,M,25,21150,2,5,6,LL2.205,60,2,5,6,L160,M,25,20203.24NO,M,25,N,25,20170,1,A,34,35353.37A,34O,1,A,34,35180,R,29,Q,30303.39Q,29O,R,29,Q,30190,2,3,D,443.433,DO,2,3,D,420O,R,31,32323.70R,33O,R,31,33,31,32210,P,26,27273.81P,28O,P,26,27,2&2722O,R,31314.171,BO,R,31,1,B23O,2,CC3.7720,C,0,26.4 问题四 完成所有巡视所用最短时间：T = min + nT + mtminV我们以问题一中的第一组为例，其中S = 206.8km,m = 13,n = 6。为方便讨论，将1T,t统一作为时间变量，设T = at (a = 2)，则上式可改写为：+ (m + an)t,_S= minmin V当停留时间t不变时，利用matlab作图得到巡视时间T与行驶速度V的关系 min如下：由图示可知，当V取值较小时，V对巡视时间T影响较大，即速度小范围 min波动时，我们也需重新考虑分组。V取值较大时，V对巡视时间T影响较小，即V小范围波动时，不需要调min整分组情况。当速度V不变时，同样利用matlab作图得到巡视时间T与停留时间t的关系如由图形可知，T与t成线性变化。即无论t取何值，t对T的影响较大,min min当停留时间t小范围波动时，也需重新考虑分组。六、模型评价、改进与推广7.1 模型评价7.1.1 优点：1）本模型运用最小生成树和最短路径树相结合的方法，将区域分为三个部 分，使求解简化；2）引入均衡度的概念，使模型检验合理方便；3）模型运用网络图的方法给出了灾情最佳巡视路线，缩短了时间，对与灾 情的防治有极大帮助；7.1.2 缺点：1）运用哈密顿圈原理求得的回路不是最优解，检验修正路线的工作量较大。2）问题四中，在对T、t、V的灵敏度分析中，只对其变化作了定性分析, 而未作定量分析。7.2 模型改进1）此模型只针对当前数据，对灾情的广泛区域没有实用性，我们可以建立 动态规划模型，这样在数据发生变动的情况下，也可使用；2）问题三中，根据我们设计的巡回路线，部分小组剩余时间较多而未充分 利用，我们可以改进设计路线原则，尽量减少人力。7.3 模型推广 该模型不仅可以运用到最佳灾情路线的确定问题，还可以推广到推销、投递 旅行商等实际问题中。