灾情巡视路线模型

1西安邮电大学暑期大学生数学建模培训作业三小组人员：左虎博夏朝阳康敏2013年08月07日2摘要针对问题一，我们先采用直观分析法进行试探，再结合最小生成树法分析求解并得到更优解。若分三组巡视，最小生成树法求解各组的巡视路程分别为214.7km、198.9km、227.6km，总路程为641.2km，路程均衡度为12%。然后结合最小生成树原理和哈密顿回路法，重新设计分组路线，并结合地理位置和最优单旅行商路线对第二种方法进行略微的修改，得倒的各组的巡视路程分别为200.7km、196.5km、206km，总路程为603.2km，路程均衡度为4.61%。此结果下的总路程相对较短，而均衡度偏高。基于对问题一结果的分析，发现分三组的情况下，不能满足题目要求。因此我们我们通过理论证明得到最少得分四组进行巡视。通过将G图分为4个子图，并运用哈密顿回路法找出各个组的最佳巡视路线。然后，计算出各组最佳巡视路线的总长度及汽车行驶所需时间，同时算出各组的停留时间,从而得到各组完成巡视的最佳时间。同样以巡视路程最短和时间均衡度最小为目标函数，各巡视时间小于24小时作为约束条件建立多目标规划模型。采用Lingo软件进行编程求解（程序见附录3）得到4个组的最优巡视路线，并计算出各组巡视的总时间。对于问题三，在巡视人员足够多的情况下，巡视距离O点最远的点所用的时间为最短时间，最短时间约为6.43小时。根据最短路径树，从远到近，依次巡视各村镇，在所用时间不大于最短时间的前提下，各组尽可能多的巡视几个村镇，进行分组确立巡视点，并对已巡视过的点进行逐个剔除。结合Matlab编程得到的最短距离矩阵和人工记录分析，得出分组情况及巡视路线（见附表），对于问题四，在组数固定时，则各组的最短路径就已确定，在最佳路径不变的情况下，t、T、V改变影响的只是整个巡视时间。我们利用matlab编程画图得到问题二中个别分组的路径的T、t、V与巡视时间的关系曲线。通过观察曲线发现：①停留时间t与巡视时间呈线性关系，无论t取何值，对巡视时间影响都较大；②当速度V较小时，V的变化对巡视时间的影响较大；当速度V足够大时，V的变化对巡视时间的几乎无影响。在t变化和V较大幅度减小时，都需适当调整分组，甚至重新分组。关键词：哈密顿改良圈，最小生成树，MATLAB,prim算法3目录1.问题重述………………………………..12.模型假设与符号说明…………………...23.问题分析……………………………..34.模型建立与求解………………………...45.模型评价………………………………186.参考文献………………………………197.附录…………………………………….201一、问题重述1.1问题背景2008年夏天某县遭受水灾.为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视.巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线。1.2问题内容1.若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的路线。2.假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时.要在24小时内完成巡视，至少应分几组；给出这种分组下你认为最佳的巡视路线。3.在上述关于T、t和V的假定下，如果巡视人员足够多，完成巡视的最短时间是多少：给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路线。4.若巡视组数已定（如三组），要求尽快完成巡视，讨论T,t和V改变对最佳巡视路线的影响。2二、模型假设与符号说明2.1模型假设1.公路不考虑等级差别，也不受灾情或交通情况的影响；2.各条公路段上汽车行驶的速度可以认为是均匀的；3.巡视人员在各乡（镇）、村停留的时间一定，不会出现特殊情况而延误时间；4.各巡视组巡视的乡（镇）、村不受行政区划的影响，即某乡（镇）与隶属于它的村不一定要分在同一组内；5.忽略不计巡视人员上、下车所用的时间；6.当巡视比较偏僻的乡村时，汽车从县镇府出发直至到达终点，中途不会停留，仅在终点站停留T（或t）小时，然后按原路返回，到达沿途各站接回巡视人员。2.2符号说明k:巡视人员的分组数;(,)GVE：赋权连通图；iG：赋权连通图的第i个子图(1,2,)i，k;iL：子图iG中的最佳回路；ic：最佳回路iL的各边权之和；ih：最佳回路iL的巡视时间;ijw：第i个乡、村到第j个乡、村的距离(j1,2,53)i，，；T：巡视员在各乡（镇）的停留时间；t：巡视人员在各村停留的时间；V：汽车行驶的速度，单位公里／小时。3三、问题分析首先，本题所求的是分组巡视的最佳路线,应与多旅行商问题类似。1）最佳旅行商问题可转化为最佳哈密尔顿回路的问题。在一般图中，最佳旅行线路未必为最佳哈密尔顿回路，首先哈密尔顿回路未必存在，其次就算哈密尔顿回路存在，也未必是最佳旅行线路。所以需要转化。转化方法是,在图G的基础上构造一个完全图G′,点集仍为N,每条边(i,j)的权w(i,j)为点i与j在G中最短路的长。于是,在G中寻求最佳旅行商回路的问题即为在G′中寻求最佳H-回路的问题。2）多旅行商问题可转化为单旅行商问题。3）在均衡性的要求下，上面的转化方法可能会得到比较差的结果。因此，这个问题应该先分组，再用单旅行商问题的方法求解。1.问题一的分析1）分组方法和依据地理位置、最小生成树、最短路生成树、最优单旅行商路线2）均衡性的度量a=（max(Ci)-min(Ci)）/max(Ci)3）调整策略及依据各路线的长度、相邻点的数量、两组点间的距离2.问题二的分析1)确定最少组数停留时间：17*2+35*1=692）停留时间与路程的转化3）解法类似第一问，顶点数、转移点3.问题三的分析1）首先应确定最短时间2）分组依照最小距离树和由远及近原则4.问题四的分析对于问题四，也可以结合问题二（在分四组去巡视的前提下），要求尽快完成巡视，分析村、乡镇停留时间及汽车行驶速度对巡视路线的影响。鉴于均衡度系数较低与寻访点个数相差不大，我们可以利用matlab编程画图得到问题二中个别分组的路径的T、t、V与巡视时间的关系曲线。通过曲线走势直观分析，得出结论。4四、模型建立与求解4.1问题一模型的建立及求解：4.1.1模型一的建立与求解（直观分析法）：根据题中所给的乡（镇）、村示意图对地理位置进行粗略的划组分析。很显然，由于县政府位置偏向东面，则若分成三组巡视，县城远离的一边分为两块的可能性比邻近县城的一边大得多，这样就可以得到手工给出的三组巡视路线图见表1：表1：三组巡视路线的详细情况对比图为了衡量分组的合理性，于是我们定义分组的路程均衡度公式：123123123max,,min,,max,,ccccccccc；显然01，值越小，说明分组的均衡性越好。由此我们可以得到采用直观分析法时的均衡度%67.121。4.1.2模型二的建立与求解（基于最小生成树法）现要分三组巡视，则需要把图G分成三个子图(1,2,3)iGi，在每个小组名称路线总路线长度路线的总长度IO—1—B—34—35—33—A—R—31—32—30—Q—28—27—24—N—26—P—29—R—O214.7641.2IIO—P—26—N—23—22—17—16—I—15—14—13—J—18—K—21—25—20—L—6—M—O198.9IIIO—C—3—D—4—8—E—F—10—F—12—H—12—G—11—J—19—L—7—6—5—2—O227.65子图iG中寻找最佳回路(1,2,3)iLi。因为最小生成树中能包含图G中所有的顶点E，而且最小树的边权是相邻两顶点间的距离，它描述了顶点之间的相近程度，故可以采用最小生成树进行分组。本模型的主要思想是：首先采用Prim算法得到G图的最小生成树，然后基于最小生成树生成一个可行的巡视路线，求得路线的最优总路程为。采用Prim算法求解最小生成树步骤如下：（1）输入加权连通图G的带权邻接矩阵((,))nnAaij；（2）建立初始候选边表,BT；（3）在候选边表中选出最短边(,),(,)uvTTuv；（4）调整候选边表B；（5）重复（2），（3），直到T含有1n条边。根据Prim算法进行编程求解（具体程序见附录1），于是我们得到G图的最小生成树如图1。图1现对已得到的最小生成树进行分解，以获得三个子图iG并使得分解结果尽6量均衡。由于在最小生成树上，边权接近可以近似认为均衡即各子图包含的顶点数应接近。因此，各个子图的顶点数应尽量接近17个，且遵循以下分解原则。最小生成树分解原则：(1)分解点为O点或尽可能地接近O点；（2）分解所得的三个子图Gi的顶点数尽可能地接近17个；（3）尽量是分解所得的子图是连通图；（4）尽量使子图Gi与点O的最短路上的点在该子图内，且尽量使各子图的点在子图内部形成环路。依据以上分解原则得到的分解结果如图2。图2然后，采用哈密顿回路法求解每个子图内的最佳巡视路线。寻找最佳巡视路线实际上就是在赋权图中寻找最优的哈密顿圈，包含图G的每个顶点的圈称为哈密顿圈。于是问题就可以转化为：现已知三个子图内乡、村与乡、村之间的距离，从县镇府O出发，经过子图内的所有乡、村，最后又回到点O。将划分好后的点通过MATLAB进行哈密尔顿改良圈处理，我们可以得到三个分组的哈密尔顿改良圈的连接方式。再进过我们的初步拟合和处理，我们得到了表2。7表2：哈密尔顿回路法得到的三组路线由此，可以计算出对模型二初步改进后的分组的均衡度为：%82.72从上述图表中不难看出，第二组走的路程稍长，而第一组与第三组走的路程过短，其间差值较大，故为了使分组的均衡性更好，我们需在基于最小生成树的原则之上对原来的分组进行适当的调整。为了缩小第二组与其他两组间的路程差，首先，我们将第二组的K点附近的路线进行修改，使之延K，22，17，16，I，15，14，再在J点处过一趟18处；然后将H点划到第三组，并将E点到4相连，过4后走D，3，C回到O点，如此可以有效地减少了第二组的路程，稍微地减少了第一组和第三组的路程；最后，采用Hamilton圈法分别求解三个子图内的最佳回路（表3）。表3：最终改进路线图的分组情况注：加有底纹的表示只经过此点但不停留。由此，可以计算出对模型二最终改进后的分组的均衡度为：%61.43。名称路线总路线长度路线的总长度IO—1—B—A—34—35—32—31—R—29—Q—30—Q—28—27—26—N—23—24—27—26—P—O205635.8IIO—M—25—20—L—19—J—13—14—H—14—15—I—18—K—17—16—17—22—K—21—25—M—O222.4IIIO—2—5—6—7—E—11—G—12—F—10—F—9—E—8—E—7—D—4—D—3—C—O208.4小组名称路线总路线长度路线的总长度IO—1—B—A—34—35—32—31—33—A—R—29—Q—30—Q—28—27—24—23—N—26—P—O200.7603.2IIO—M—25—21—K—22—17—16—I—15—14—13—J—18—J—19—L—20—25—M—O196.5IIIO—C—3—D—4—8—E—9—F—10—F—12—H—12—G—11—E—7—6—5—2—O2068综上所述，对比模型一和改进后模型二的结果可知，若分成三组巡视，虽然改进后模型二的巡视总路程比模型一的短，而且，改进后模型二分组的均衡性比模型一要好很多。此外，模型二的结果是经过严谨科学的计算得到的，具有较高的可信度，相比之下，模型一的结果是人根据地理位置粗略划分得到地，具有随机性，可信度较低。经上述分析可知，若分成三组巡视，则应该采用改进后模型二的巡视路线,见图3。图394.2问题二的模型建立及求解：此问添加了巡视组在各乡（镇）停留的时间2T小时，在各村停留的时间1t小时以及汽车的行驶速度35v公里／小时的条件后，要求在24小时内完成巡视的最少分组数以及相应的最佳巡视路线。此时需访问的乡（镇）共有17个，村共有