灾情巡视路线.pdf

《灾情巡视路线.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、灾情巡视路线摘要本题给出了某县的公路网示意图，要求出在不同条件下灾情巡视的最佳分组方案和路线。这是一类图上点的遍历问题，也就是要用若干条闭合的曲线覆盖图上的所有顶点，并使某些指标达到最优。本文建模的主要思想即为利用逐步加入法先生成一个可行路线，再利用最小生成树、启发式算法对路线进行优化调整，并且使用均衡度概念来衡量各组路线的均衡性。对于问题一，首先将图划分为三个区域，使每组巡视一个区域。在建立模型的过程中，首先使用了逐步加入法，粗略的得到三个区域的划分以及总共需要的时间。接下来使用最小生成树算法，得到权值最小的路径。根据最小生成树，最后运用深度优先搜索法，得到

2、所求的精确路线。各组所走的路程分别为（单位：km）：212.2、125.5、215.9，路程总和为553.6，均衡度为：0.49。对于问题二，与第一题相同，将巡视人员分为几组便将区域划分为几个部分。在划分区域的过程中，忽略停留时间对最小生成树与深度搜索的影响。所以套用第一问的模型。先粗略的分割得到大致所需的路程，然后根据最小生成树的深度优先算法计算，得到精确的路径，根据路径算出各组所需时间以及总时间。各组所需走的路程分别为（单位/km）：142.5、152.1、194.6、189.2，各组所需时间分别为（单位/h）：21.07、21.34、22.56、23.4

3、0，均衡度为：0.3。对于问题三，最短距离即为从原点到到最远点的距离，从而求出最短时间，在其他组的路径中，要保证时间小于最短时间。以此原则寻找其他路径，并使最后的路径包括所有的村、镇、乡。在寻找路径的过程中，使用贪心算法，在每点周围寻找路径最短的相邻点，以此保证路径最优，最后得到的所需组数为22组。对于问题四，使用理论分析对问题四进行讨论。先将巡视时间用路程、速度、ttmaxmin停留时间等变量表示。其次定义作为时间均衡度用具体实例分析在ti3不同的下，T、t、V的改变对最佳巡视路线的影响，最终得到结果。关键词：最小生成树MTSP深度优先搜索贪心算法

4、1一、问题重述今年夏天某县遭受水灾。为考察灾情、组织自救，该县领导决定带领有关部门负责人到全县各乡（镇）、村巡视。规定巡视路线为从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线。题目给出一份已将该路段的公里数标注在公路边上的该县的乡（镇）、村公路网示意图。1.给定巡查组数为三组，设计一组巡视路线使总路程最短且尽可能均衡。2.给定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时。求解应当分几组要在24小时内完成巡视，并且给出这种分组下的最佳的巡视路线。3.给定与问题二相同的T,t和V的假设，求解在巡

5、视人员足够多的情况下，完成巡视的最短时间是多少？并且给出最佳巡视路线。4.若巡视组数已定（比如三组），要求尽快完成巡视，讨论T，t和V改变对最佳巡视路线的影响。二、问题假设1.假设图上标注的公路均未受水灾影响，仍可正常通过行，不影响巡查路线。2.假设在各乡（镇）、村均能准时到达、准时离开。3.假设巡视人员的用食、休息等均在规定停留时间内，不会影响正常巡视。4.假设汽车行驶速度不受外界因素影响，始终保持35km/h匀速行驶。5.假设巡视过程中汽车、巡视人员等均无任何突发情况影响巡视进度。6.假设各巡视内成员巡视行动一致，各成员巡视进度统一2三、符号说明四、模型的

6、建立与求解4.1问题一4.1.1问题分析题目给定巡查组数为三组，要求设计一组巡视路线使总路程最短且尽可能均衡。因此考虑将图划分为三个区域，使每组巡视一个区域。划分过程中既要总路程最短，又应尽量使各组均衡，即各组通过的路程数接近，经过的乡、村数目接近。在建立模型的过程中，首先使用了逐步加入法，粗略的得到三个区域的划分以及总共需要的时间。接下来使用最小生成树算法，得到权值最小的路径。根据最小生成树，最后运用深度优先搜索法，得到所求的精确路线。4.1.2树的深度优先搜索模型的建立与求解通过对问题一进行分析，锁定问题一的关键为如何对该公路网络图进行区域划分。本文首先使

7、用逐步加入法得到一个使得总路程较短的初始化路线，再根据逐步加入法的结果使用最小生成树算法，对生成的最小生成树进行深度优先搜索法，进一步得到最终的精确路线。我们首先将题目中的图转化为一个节点间的简易图（图一），在进行模型的建立与求解。图一简化公路网络图3首先是逐步加入法：任取最外围一点，以逆时针为搜索方向，假定搜索尽量走方向变化最小的路线即先加入本区域最外围的点，然后在内部逐步加入新的点。最后得到本区域的所有店。该方法首先必须确定巡视要分为几组，并且规定各组必须经过O点，然后用上述方法确定各区域的范围。以这种方法可以进行调整得到一种总路程较短的初始化路线1如下：

8、：OCB34353230