灾区巡视最佳路线选择问题数学建模

《灾区巡视最佳路线选择问题数学建模》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、灾情巡视摘要木文解决的是对全县各乡镇和村庄进行灾情巡视线路的设计问题，该问题属于点的遍历性的TSP问题。因此我们结合图论的相关知识并考虑到分组的均衡性，建立起了约束最优化线路模型来解决该问题。针对问题一，我们先建立起目标函数（见5.11中式（0.1））,随后根据各点的集中区域进行划分，引入均衡度a进行分组方案的比较，最终采用方案二（见5.2中方案二）。再利用破圈法和最小牛成树法得到了最短回路。最后matlab编程求解（见附录一）得出各组的巡视路程分别为200.1公里,196.8公里,205.1公里，总路程为602公里，均衡度严0.0405。具体路线安排见表二。针对问题二，分

2、析得到要在24小时完成巡视的任务最少要四组巡视人员，将问题一中各条线路的权重由路程改为了时间，并在结点处增加了结点权重。Matlab求解（见附录二）得巡视的时间分别为21.73小时22.51小时，23.60小时，21.18小时。所以至少分四组，具体路线安排见表三。针对问题三，通过图论软件得出巡视到距离O最远的点H要的时间为6.43小时，要在这个时间上限内完成巡视，分析得到最优分配为24组。最后借助图论软件求出最终方案（见表四）。针对问题四，在不影响分组的均衡条件下，采用控制变量法对77,7分别为变量时的各自允许变化范围进行了研究。得出了这三个变量的关系式，再根据式子进行了讨

3、论，得到最终结果见表五。关键词：Hamilton圈破圈法TSP问题最小生成树1问题重述1.1问题背景今年夏天该县遭受水灾。为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视。巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又冋到县政府所在地的路线。1.2需要解决的问题若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间匸1小时，汽车行驶速度V=35公里/小时。要在24小时内完成巡视，至少应分几组；给出这种分组下你认为最佳的巡视路线。在上述关于T,t和V的假定下，如果巡视人员足够

4、多，完成巡视的最短时间是多少；给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路线。若巡视组数已定（如三组），要求尽快完成巡视，讨论T,t和V改变对最佳巡视路线的影响。2模型的假设及符号说明2.1模型假设假设1：假设汽车在路上以/匀速行驶，且不停留，不考虑故障，忽略外部因素影响假设厶巡视过程中除了正常停留外，没有因其它因素造成时间延误假设3：巡视路线可以重复假设4：对于要多次经过的乡（镇）或村只停留一次假设5：每个巡视人员只能走自己划分区域内的路线2・2符号说明符号说明G表示加权图Gi表示子图V表示顶点，每一个乡（镇）或村看成一个点E表示边，乡（镇）或村之间的路线y)表

5、示权重，乡（镇）或村之间的距离s表示回路路程总和表示路程均衡度b表示每一条子冋路T表示在每个乡（镇）停留的时间I表示在每个村停留的时间Ti表示第i组的巡视时间V表示汽车行驶速度Z表示划分的区域数N表示乡（镇）的数口n表示村的数日M表示第i组巡视乡（镇）的数目叫表示第i组巡视村的数目m表示所分的组数3表示时间均衡度3问题分析本文研究的是最佳巡视路线设计问题，要求从O点出发巡视完所有乡（镇）村后，在回到O点，此问题可以转化为旅行商问题，再设计相应的算法求解针对问题一：问题一要求设计3组巡视，巡视总路程最短且尽可能均衡，首先我们通过主观筛选法将原图划分为3个子图，每个子图顶点数大

6、约为17个，相邻的点划在一个子图中，且尽量使每个子图构成一个回路，这样将原问题转化为单旅行商问题求解针对问题二：问题二在问题一的基础上加了时间的限制，在每一个顶点都有停留时间，且在24小时巡视完。通过计算可得至少分为4组，才可能实现。和问题一类似我们将原图划分为4个子图，分别计算每组的巡视时间，设计每组的巡视路线。针对问题三：问题三T,t和V的假定下，如果巡视人员足够多，完成巡视的最短时间，并设计最佳路线。首先，我们分析可知巡视H使用的时间是最长的。那么，设计分组时，其它组巡视的时间不能超过这一最长时间。在计算过程中我们先从距O点远的点开始考虑，因为若巡视时间与最小时间相差

7、较远可以考虑顺便访问途径的乡、村。运用图论软件可以很好解决这一问题。针对问题四：巡视组数已定，要求尽快完成巡视，讨论T,t和V改变对最佳巡视路线的影响。我们分别考虑当其中两个变量不变时对最佳路线的影响。分为3种情况讨论。4.数据分析处理4.1理论知识定义一个图G是指一个二元组(T(G丿工(创，其中：其中元素称为图G的顶点。2)E(G)是顶点集々G丿中的无序或有序的元素偶对(匕•，匕)组成的集合，即称为边集，其中元素称为边.定义图G的阶是指图的顶点数V(G)f用v來表示；图的边的数目用£来表示.用G二(7(G),