灾情巡视路线模型论文

《灾情巡视路线模型论文》由会员分享，可在线阅读，更多相关《灾情巡视路线模型论文（13页珍藏版）》请在金锄头文库上搜索。

1、题目：灾情巡视路线题目：灾情巡视路线学号：2012070231姓名：施亚男班级：12 级数学教育一问题重述问题重述1.11.1 背景分析：背景分析： 今年夏天该县遭受水灾。为考察灾情、组织自救，县领导决定，带领有关 部门负责人到全县各乡（镇）、村巡视。巡视路线指从县政府所在地出发，走 遍各乡（镇）、村，又回到县政府所在地的路线。 1.21.2 需要解决的问题：需要解决的问题： 1）若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。2）假定巡视人员在各乡（镇）停留时间 T=2 小时，在各村停留时间 t=1 小 时，汽车行驶速度 V=35 公里/小时。要在 24 小时内完成巡视，至少

2、应分几组； 给出这种分组下你认为最佳的巡视路线。 3）在上述关于 T , t 和 V 的假定下，如果巡视人员足够多，完成巡视的最 短时间是多少；给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路 线。 4）若巡视组数已定(如三组） ，要求尽快完成巡视，讨论 T，t 和 V 改变对 最佳巡视路线的影响。一、一、 模型假设模型假设2.1 假设地面情况一切正常，不会影响汽车行驶速度； 2.2 假设第二次经过的乡镇，不计算停留时间； 2.3 对于同一乡镇，如果某一小组停留过，其他小组经过时不计算停留时间； 2.4 假设经过邻县村不做任何停留； 2.5 假设县镇府所在地灾情不派小组人员巡视。二、二、

3、 符号说明符号说明ic第 个小组所走路程i衡量均衡度（越小，均衡度越好；反之，均衡度越差）T巡视一个乡（镇）所花时间hT2t巡视一个村所花时间ht1V汽车的行驶速度hkmV/35it第 个小组巡视所用时间imaxS最短路径树中从 O 点出发到所有点距离中的最大距离jS最短路径树中点距出发点的距离j)352 , 1 ,(LLRPNBAOj minT完成所有巡视所用的最短时间sT巡视完所规定的点外的剩余时间n小组巡视乡镇的个数m小组巡视村得个数三、三、 问题分析问题分析本文研究的是考察灾情最佳巡视线路设计的问题，准确合理的路线设计对 灾情巡视救治起着重要作用。为很好的解决此问题，为此我们建立了网络

4、图模 型。 对于问题一，题目要求在分三组巡视的情况下，使总路程最短且各小组所 走路程均衡。先考虑分区，我们将得出的最小生成树图形和最短路树图形，进 行比较并找出其公共部分。分组要求尽量不破坏最短生成树和最小生成树，所 以我们以公共部分为界限，将此网络图分为三组。为使每小组所走路程均衡， 我们引入了均衡度。它表示最大路程和最小路程的差值与最大路程的比值。 越小，表示均衡度越好。以总路程最短和均衡度最小作为目标函数建立多目 标规划模型，利用哈密顿原理得出各组的巡回路线，并对其分析修正求得各组 最优巡回路线。对于问题二，要求在 24 小时内完成所有巡视。 通过第一问的结果，求得在分三组的情况下所用的

5、平均时间大于 24 小时，htTT.828)358 .6093517(311所以我们先考虑分四组。我们的分组原则为：1、每子区域所分得的点近似相等； 2、尽量使每一个子区域连通；3、使每一个子区域中与点 O 的最短路上的点在 该区域内。根据以上分组原则将整个图大致划分为四个子图，同样利用哈密顿 算法求得在相对均衡的情况每个小组的最短路径和所需时间。如果部分时间大 于 24 小时，则调整分组方式；若所有时间均大于 24 小时再考虑多加一组。直 到找到相对均衡条件下的最佳路线。对于问题三，考虑在人员足够多的情况下，求出最短的巡视时间。假设一 个小组只巡视一个点的情况下，则去巡视离点最远的点所花时间

6、最长。我们O 以巡视小组中所耗时间最长的小组所用时间作为这次整个巡视的最短时间。要 使这次巡视时间最短，则要求去巡视离点最远的点所花时间最小，由图一可O知，离 O 点最远的点为 H，所以就以巡视所花时间作为。当此小组只巡视HminTH 时，最小。在不超过的情况下，根据其他小组的剩余时间确定沿途是minTminT否巡视其他点。其中巡视原则为：当一组人员巡视完规定点后时，在剩余时 间允许的情况下，优先考虑原巡视点附近而距离较远的点，最大限度使用O剩余时间，主要考虑原则。按照此原则，逐个巡视，直至巡视完所有点。对于问题四，若巡视组数已定，则每个小组的最短路径就已确定，、 、Tt 改变只影响的是整个的

7、巡视时间。要求尽快完成巡视，即巡视时间要尽可能V 小。巡视时间包括到巡视点的行驶时间和在巡视点的停留时间。行驶时间主要 取决于速度，而停留时间由、 决定。所以此问题讨论的是当、 、改VTtTtV 变时对巡视时间的影响，即对、 、的灵敏度分析。TtV四、四、 数据处理数据处理由题目可知，共有 53 个乡镇，即在网络图赋权网络图中共（WEVG有 53 个点. 其中表示图 G 的 53 个节点，表)53(,21nvvvVnLijeE 示相关联的两点的边集，表示相关联两点间的权值。ji,ijwW ji,定义决策变量：ijr两点不相关表示两点相关联表示jijirij.0,1其中相关联表示两点之间有权值，

8、不相关表示之间没有权值。ji,ji, 将这些点和权值生成图的矩阵，对于不相关的两点权值作为无穷大处理G （数据.txt） 。用 MATLAB 编写程序，得出该网络图的最小生成树。再运用迪G 克斯特拉算法求出出发点到各点的最短距离，即网络图的最短路径树。画出O 的两种图形如图 1 所示。五、五、 模型建立与求解模型建立与求解6.1 问题一问题一 6.1.1 模型建立模型建立 通过问题一的分析，建立多目标规划模型。 （1）三组巡视的总路线最短： 31miniic（2）巡视路线尽量均衡：)max()min()max(miniii ccc我们设当时，认为均衡度比较好。15. 0 综上得出目标函数： m

9、inmin31iic约束条件：每个小组所走的路线必须是条回路。6.1.2 模型求解模型求解 根据问题一的分析，根据两图的公共部分作为分组的界限，分组图如下（图 2）：将分好的三个子区域分别利用哈密顿原理进行编程求解，得到三个小组的 巡视路线为：第一组：O, P ,26 ,N ,23, 24 ,27 ,28 ,Q, 29, Q ,30, 32 ,31, R ,A, 33, 35 ,34 ,B, 1 ,O行走的总路程为kmc8 .2061第二组：O ,M ,21, K ,22 ,17, 16 ,I ,18 ,I ,15 ,14, 13, 14,H ,12 ,G ,11, J ,19, L ,20,

10、 25 M ,O行走的总路程为kmc5 .2452第三组：O, 2 ,5 ,6 ,7, E, 9 ,F, 10 ,F, 9 ,E, 8 ,4 ,D, 3, C, O行走的总路程为kmc8 .1583三组所行走的总路程：kmcCii1 .611316.1.3 均衡度分析均衡度分析根据三组所行走的路程求得均衡度：ic35. 0)max()min()max(232ccc ccciii因为，我们认为均衡度不好，需要对分组进行修正。15. 035. 0 通过结果发现第二小组所行走的路程比较多，而第三小组行走路程较短， 我们考虑将分区 2 中离分区 1 较近但距 1 较远的 11，G，12 三个点划到第三

11、分 区中，而分区的区域不变。在此情况下，重新利用哈密顿算法编程得到三个小 组的巡视路线如下表 1：小组路线行走路程ic第一组O, P ,26 ,N ,23, 24 ,27 ,28 ,Q, 29, Q ,30, 32 ,31, R ,A, 33, 35 ,34 ,B, 1 ,O206.8km第二组O,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 ,8, 4, D ,3 ,C, O186.4km则三组所

12、行走的总路程：kmcCii8 .60931此分区下的均衡度：13. 0)max()min()max(232ccc ccciii由可知，此种情况下的分区较为合理。各小组的巡视路线如下图 315. 06.2 问题二问题二 6.2.1 模型准备：模型准备： 根据第一问的结果得出在分三组的情况下，各小组所用时间：第一组：hVtTt9 .308 .2061361第二组：hVtTt2 .296 .2161162第三组：hVtTt3 .264 .1861153通过以上数据观察可知，分三组时不能满足题目要求，所以我们先考虑分四组。6.2.2 模型建立模型建立 根据问题二分析，建立多目标规划模型。 要求设计最佳

13、巡视路线，即使总路程最短，并且所用时间相对均衡，得出 目标函数： minmin41iic约束条件：每个小组巡视所用时间均不超过 24 小时，即（4 , 3 , 2 , 124iVcntmTti i6.2.3 模型求解模型求解 根据问题二分析，得出整个区域的分组情况。利用哈密顿算法编程求得各 小组最短巡视路线及所用时间如下： 第一组: 巡视区域：A,B,Q,R,1,29,30,31,32,33,34,35最短路程，所用时间kmc5 .1251ht59.191第二组： 巡视区域：K,M,N,P,16,17,21,22,23,24,25,26,27,28最短路程，所用时间 kmc3 .1542ht4

14、1.222第三组 G,H,I,J,11,12,13,14,15,18,19,20最短路程，所用时间 kmc9 .2033ht83.233第四组 C,D,E,F,2,3,4,5,6,7,8,9,10最短路程，所用时间 kmc8 .1584ht54.2046.2.46.2.4 均衡度分析均衡度分析 根据以上所求结果，发现所用时间都小于 24 小时。但第三组用时较多，几 乎接近 24 小时，而第一组用时较少。我们对各组所用时间进行均衡度分析：178. 0)max()min()max(313ttt tttiii因为，我们认为此分组结果不够合理，需要重新调整分组15. 0178. 0 方式。 通过观察分

15、析，将 2 分区中的村 28 划分到 1 中，同时将 3 分区中的村 11 划分到 4 中，同样利用 matlab 编程求得各组的最短巡视路线和所用时间，如下 表 2：组号巡视点寻访 个数巡视路径总路程 长耗时长 （小时）第一组A B Q R 1 28 29 30 31 32 33 34 3513O,1,B,A,34,35,33,31,32,30 ,Q,28,Q,29,R,O142.121.06第二组K M N P 16 17 21 22 23 24 25 26 2713O,P,26,27,26,N,24,23,22,1 7, 16,17,K,21,25,M,O152.121.35第三组G H

16、 I J L 12 13 14 15 18 19 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 4 5 6 7 8 9 10 1114O,2,5,6,7,E,11,G,12,F,10, F,9,E,8,4,D,3,C,O186.423.33根据表中数据可知，所有时间均小于 24 小时，对时间进行均衡度分析为：15. 097.00)max()min()max(414ttt tttiii我们认为此情况下的分组较为合理，同时得出各组的路线图为：6.3 问题三问题三由最短树路径树可知，从点到所有点距离中的最大距离，OkmS5 .77max从点出发到点。同时计算出其所用时间：OHhvST4286.