灾难最佳巡视路线
摘要
本文解决的是对全县的乡镇和村庄进行灾情巡视最佳线路的求解问题，多旅行售货问题。问题一是三个旅行售货问题，问题二是四个旅行售货问题。我们可以运用图论的知识并且考虑气均衡性，建立起约束最优化线路模型来解决这个问题。
关键词：Hamilton 圈 多旅行售货问题 最小生成树
问题
今年夏天该县遭受水灾。为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视。巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线。
1.若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。 2.假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时。要在24小时内完成巡视，至少应分几组；给出这种分组下你认为最佳的巡视路线。
1.问题重述
问题1：若分三组（路）巡视，试设计总路程最短且各组尽可能均衡
的巡视路线图
问题2：假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时。要在24小时内完成巡视，至少应分几组；给出这种分组下你认为最佳的巡视路线。
问题3：在上述关于T , t和V的假定下，如果巡视人员足够多，完成巡视的最短时间是多少；给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路线。
问题4：若巡视组数已定(如三组），要求尽快完成巡视，讨论T，t和V改变
对最佳巡视路线的影响。
2.模型的假设及符号说明
2.1模型假设
假设1：假设汽车在路上以V匀速行驶，且不停留，不考虑故障，忽略外部因素影响
假设2：巡视过程中除了正常停留外，没有因其它因素造成时间延误 假设3：巡视路线可以重复
假设4：对于要多次经过的乡(镇)或村只停留一次 假设5：每个巡视人员只能走自己划分区域内的路线 2.2符号说明
G：表示加权图 Gi：表示子图
V：表示顶点，每一个乡(镇)或村看成一个点 E：表示边，乡(镇)或村之间的路线
w(x，y)：表示权重，乡(镇)或村之间的距离 S：表示回路路程总和 ?：表示路程均衡度 Li：表示每一条子回路
T：表示在每个乡(镇)停留的时间 I：表示在每个村停留的时间 Ti：表示第i组的巡视时间 V：表示汽车行驶速度 Z：表示划分的区域数 N：表示乡(镇)的数目 N：表示村的数目
Ni：表示第i组巡视乡(镇)的数目 Ni：表示第i组巡视村的数目 M：表示所分的组数
?：表示时间均衡度
3.问题分析
本文研究的是最佳巡视路线设计问题，要求从O点出发巡视完所有乡(镇)村后，在回到O点，此问题可以转化为旅行商问题，再设计相应的算法求解
针对问题一：问题一要求设计3组巡视总路程最短且尽可能均衡，首先我们通过主观筛选法将原图划分为3个子图，每个子图顶点数大约为17个，相邻的点划在一个子图中，且尽量使每个子图构成一个回路，这样将原问题转化为单旅行商问题求解
针对问题二：问题二在问题一的基础上加了时间的限制，在每一个顶点都有停留时间，且在24小时巡视完。通过计算可得至少分为4组，才可能实现。和问题一类似我们将原图划分为4个子图，分别计算每组的巡视时间，设计每组的巡视路线。
针对问题三：问题三T , t和V的假定下，如果巡视人员足够多，完成巡视的最短时间，并设计最佳路线。首先，我们分析可知巡视H使用的时间是最长的。那么，设计分组时，其它组巡视的时间不能超过这一最长时间。在计算过程
v
中我们先从距O点远的点开始考虑，因为若巡视时间与最小时间相差较远可以考虑顺便访问途径的乡、村。运用图论软件可以很好解决这一问题。
针对问题四：巡视组数已定，要求尽快完成巡视，讨论T，t和V改变对最佳巡视路线的影响。我们分别考虑当其中两个变量不变时对最佳路线的影响。分为3种情况讨论。
v4.数据分析处理
4.1理论知识
定义 一个图G是指一个二元组(V(G),E(G))，其中：其中元素称为图G的顶点。 2) E(G)是顶点集V(G)中的无序或有序的元素偶对(vi,vj) 组成的集合，即称为边集,其中元素称为边.
定义 图G的阶是指图的顶点数|V(G)|, 用v来表示； 图的边的数目|E(G)|用?来表示.
用G?(V(G),E(G))表示图，简记G?(V,E).也用vivj来表示边(vi,vj).
设G=
设G是有n个结点的连通图，下面算法产生的是最小生成树。 算法的基本思想
先将图G 的边按权的递减顺序排列后, 依次检验每条边, 在保持连通的情况下, 每次删除最大权边, 直到余下n- 1 条边为止。 4.2数据分析处理
我们把53个乡(镇)村看作53个顶点，它们之间的距离为权重，建立邻接矩阵，运用图论软件，可视化如下图所示
运用图论软件，自动选择最短路径，可以求得O点到53个顶点的最短距离及路径。
5问题一的解答
5.1模型一的建立 5.1.1确定目标函数
公路网图中，每个乡(镇)或村，看作图中的一个节点，公路看作边，节点之间的距离看作对应边上的权，公路网问题就转化为加权网络图，问题一就转化为在加权网络图中，从给定点O出发，寻遍所有顶点再回到O，所得总权最小，即为多旅行商路线问题。
分三组巡视，则需要把图G分为3个子图，在每个子图Gi(i=1,2,3)中寻找最佳回路Li(i=1,2,3)。巡视路线要尽可能均衡，因而每组巡视顶点数要尽量接近。 目标函数：
?minS?(L1?L2?L3)?(maxLi?minLi) (0.1) ?1?i?31?i?3?min??maxLi??是对均衡度的度量，?越小表示均衡度越好；S表示总的巡视路线，S越
小表示巡回路线越短。这两个目标函数不可能同时达到最小值，求解时要两者兼顾。 5.2模型的求解
因为最小生成树包含G中所有定点E，相邻两点之间的权重为这两点之间的距离，它描述了顶点之间的相近程度，故考虑最小生成树初步分块。对于巡视组
的划分，我们可以利用原图的最小生成树（所选择的都是权最小边）．从县城出发的最短路生成树，或者原图的单旅行商路线等等子图作为依据，对边界进行合理划分后向内扩展等直观方法作近似处理．
分组巡视路线的最优解，应当采用增广完全图上的单旅行商路线分段的方法求得．但是根据原题图的规模以及边的稀疏性，用这种方法处理反而将使问题变得更为复杂，而且考虑到均衡性要求需做的调整工作也将是大量的，因此，可以采用先适当进行点的分组，分别求出各组的单旅行商路线，然后在组问进行适当调整的方法求得近似解.
问题一求解步骤：
1.分析问题 2.建立数学模型
3.根据分区原则划3个分区
4.寻找最小生成树，求最短回路 5.均衡度测试 6.调整分区 7.接受模型
算法实现：
求出G中任意两个顶点见的最短路，构造出完备图G'(V,E')
?(x,y）?E',w(x,y)?mindG(x,y),
输入图G的一个初始H圈。
用对角线完全算法产生一个初始H圈。 随机搜索出G中若干个H圈。
对2,3,4步所得每个H圈，用二边逐次修正法进行优化，得到近似最佳H圈。 在第5步求出的所有H圈中，找出权重最小的一个，即为要找的最佳H圈的近似解。 根据以下4条原则将原图划分为3组： 1从O点开始分解。
2分解的三个子图顶点数尽可能接近17个。 3尽量实每一个子图为连通图。
4尽量使每一个子图中与点O的最短路上的点在该子图内，尽量使每个子图的点在子图内形成回路。
运用破圈法得到图形如下，红色线条为最小生成树 方案一 H划在第二组