灾难最佳巡视路线摘要本文解决得就是对全县得乡镇与村庄进行灾情巡视最佳线路得求解问题，多旅行售货问题。问题一就是三个旅行售货问题，问题二就是四个旅行售货问题.我们可以运用图论得知识并且考虑气均衡性，建立起约束最优化线路模型来解决这个问题。关键词:Hamilton圈多旅行售货问题ﻩ最小生成树问题今年夏天该县遭受水灾。为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡(镇）、村巡视.巡视路线指从县政府所在地出发，走遍各乡(镇）、村,又回到县政府所在地得路线。1、若分三组（路)巡视,试设计总路程最短且各组尽可能均衡得巡视路线。2、假定巡视人员在各乡（镇)停留时间T=２小时，在各村停留时间t＝1小时，汽车行驶速度V=35公里/小时.要在24小时内完成巡视，至少应分几组;给出这种分组下您认为最佳得巡视路线。1、问题重述问题1：若分三组(路）巡视，试设计总路程最短且各组尽可能均衡得巡视路线图问题２：假定巡视人员在各乡(镇)停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时。要在2４小时内完成巡视，至少应分几组;给出这种分组下您认为最佳得巡视路线。问题３：在上述关于T，ｔ与Ｖ得假定下，如果巡视人员足够多，完成巡视得最短时间就是多少;给出在这种最短时间完成巡视得要求下，您认为最佳得巡视路线。问题4:若巡视组数已定（如三组）,要求尽快完成巡视,讨论T,t与Ｖ改变对最佳巡视路线得影响。2、模型得假设及符号说明2、1模型假设假设1：假设汽车在路上以V匀速行驶，且不停留,不考虑故障，忽略外部因素影响假设2：巡视过程中除了正常停留外,没有因其它因素造成时间延误假设3:巡视路线可以重复假设4：对于要多次经过得乡（镇）或村只停留一次假设５：每个巡视人员只能走自己划分区域内得路线2、2符号说明G:表示加权图Ｇi：表示子图V：表示顶点，每一个乡(镇)或村瞧成一个点Ｅ:表示边，乡（镇)或村之间得路线w（x，y):表示权重,乡(镇)或村之间得距离Ｓ：表示回路路程总与ə:表示路程均衡度Li：表示每一条子回路T：表示在每个乡(镇）停留得时间Ｉ：表示在每个村停留得时间Ti：表示第ｉ组得巡视时间V:表示汽车行驶速度Z：表示划分得区域数N:表示乡（镇）得数目N：表示村得数目Ni:表示第i组巡视乡（镇）得数目Ｎi:表示第i组巡视村得数目M：表示所分得组数:表示时间均衡度3、问题分析本文研究得就是最佳巡视路线设计问题，要求从O点出发巡视完所有乡（镇）村后，在回到O点,此问题可以转化为旅行商问题，再设计相应得算法求解针对问题一：问题一要求设计３组巡视总路程最短且尽可能均衡，首先我们通过主观筛选法将原图划分为3个子图，每个子图顶点数大约为１７个，相邻得点划在一个子图中，且尽量使每个子图构成一个回路，这样将原问题转化为单旅行商问题求解针对问题二：问题二在问题一得基础上加了时间得限制，在每一个顶点都有停留时间，且在2４小时巡视完。通过计算可得至少分为４组，才可能实现.与问题一类似我们将原图划分为4个子图，分别计算每组得巡视时间,设计每组得巡视路线。针对问题三:问题三Ｔ,t与V得假定下,如果巡视人员足够多,完成巡视得最短时间,并设计最佳路线.首先，我们分析可知巡视H使用得时间就是最长得。那么,设计分组时，其它组巡视得时间不能超过这一最长时间。在计算过程中我们先从距O点远得点开始考虑,因为若巡视时间与最小时间相差较远可以考虑顺便访问途径得乡、村。运用图论软件可以很好解决这一问题。针对问题四:巡视组数已定,要求尽快完成巡视，讨论Ｔ,t与Ｖ改变对最佳巡视路线得影响。我们分别考虑当其中两个变量不变时对最佳路线得影响。分为３种情况讨论。４、数据分析处理4、1理论知识定义一个图G就是指一个二元组（V（G）,E（Ｇ））,其中：其中元素称为图G得顶点。2)E(G）就是顶点集Ｖ(G)中得无序或有序得元素偶对组成得集合,即称为边集，其中元素称为边、定义图Ｇ得阶就是指图得顶点数|Ｖ（Ｇ）|，用来表示；图得边得数目|E（G）|用来表示、用表示图,简记也用来表示边设G＝<V，Ｅ，W＞就是加权得连通图,对任意边ｅÎ,其权Ｃ（ｅ）≥0。令Ｔ=＜ＶＴ,EＴ，ＷＴ>就是Ｇ得一棵加权生成树,其所有枝上得权得总与称为树T得权，记为C（T)。一般说来，对于G得不同生成树Ｔ，C（Ｔ）也就是不同得.可以知道,其中必有一个最小者，而这正就是人们最为感兴趣得.因此,给定连通加权图Ｇ＝<Ｖ,E，W>，T０=〈Ｖ,ET0，WT０〉就是G得加权生成树，C(T0）为Ｔ0得权.若对G得任意加权生成树Ｔ均有C（T0）≤C（T),则称Ｔ0就是G得最小生成树。下面给出一种求最小生成树得方法(破圈法）:设Ｇ