灾情巡视问题.ppt
灾情巡视问题,093695 陆荻092376 韩向前093633 吕慧洁,问题复述,某县遭受水灾。为考察灾情和自救，县领导决定带领负责人到全县各乡（镇）、村巡视。巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线。若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的路线。若巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度v=35公里/小时。要在24小时内完成巡视，至少应分几组；给出这种分组下最佳的巡视路线。在上述关于T,t和v的假定下，若巡视人员足够多，完成巡视最短时间是多少；给出在这种最短时间完成巡视的要求下，你认为的最佳巡视路线。若巡视组数已定(比如3组)，要求尽快完成巡视，讨论T,t和v改变对最佳巡视路线的影响。,乡（镇）和村的公路网示意图,模型假设,汽车在路上的速度总是一定，不会出现抛锚等现象；巡视当中，在每个乡镇、村的停留时间一定，不会出现特殊情况而延误时间；每个小组的汽车行驶速度完全一样；分组后，各小组只能走自己区内的路，不能走其他小组的路，除公共路外；不考虑其他非正常情况。,理论准备（一）,哈密尔顿圈：经过图G的每个顶点恰好一次的圈。其中权最小的哈密尔顿圈称为最佳哈密尔顿圈。最佳推销员回路：经过每个顶点至少一次的权最小的回路。定理：完全图一定存在最佳哈密尔顿圈。定理：加权图G的最佳推销员回路的权与G'的最佳哈密尔顿圈的权相同。,理论准备（二）,方法解析： 最佳哈密尔顿圈不一定是最佳推销员回路，而最佳推销员贿赂也不一定是哈密尔顿圈。但是最佳推销员回路问题可以转化为最佳哈密尔顿圈问题。方法是由给定的图G(V,E)构造一个以V为顶点集的完备图G'(V,E') ，E'的每条边(x,y)的权等于顶点x与y在图中最短路的权。算法处理：求带权图的任意两点间的最短距离的可用算法为Floyd算法。求最优哈密尔顿图到目前为止是没有精确算法的。但是可以采用一些近似算法，如两边逐次修正法。,问题转化,节点每个乡（镇）或村边各乡（镇）、村之间的公路权各条公路的长度（或行驶时间）公路网 加权网络图原问题 最佳推销员回路问题即在给定的加权网络图中寻找：从给定点O出发，行遍所有顶点至少一次再回到O点，使得总权（路程或时间）最小的道路。,符号说明,模型求解之问题一,问题复述：分三组（路）巡视，试设计总路程最短且各组尽可能均衡的路线。问题转化：求解一个V的分组（V1,V2,V3），使得： 充分小（总路程最短） 充分小（各组路程均衡）,求解步骤（一）,运用Floyd算法，将所给图转化为满足任意两点之间的权值为原图中任意两点之间的最短路长度的完全图。将G(V,E),转化为G'(V,E')。将G'(V,E')中的顶点集V分为三组，方法如下： 选出三个点为基点，使得这三点两两之间的最短长度是所有可能组合中最大的，而且三点离O点的距离比较均衡。 对于其他任何点，离哪个基点最近，将之与该基点划为一组。 由此得到初始分组。将O点分到每组中，运用两边逐次修正算法算得每组中的最优哈密尔顿圈。 各组的圈的权是：,求解步骤（二）,调整初始分组方法：选出上次分组结果中路程最短与最长的两组。 在路程最长的组中找到与路程最短的组的基点最近的点，并将之转移到路程最短的组中，构成新的分组。 重复上述过程，直至 达到最小，即三组路程相对均匀为止。结果如下：具体的每组的路线为：,模型求解之问题二,问题复述： 假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时.要在24小时内完成巡视，至少应分几组；给出这种分组下最佳的巡视路线。问题分析： 一共有35个村，17个乡镇，停留时间总共 小时，若分为3组，每组停留时间约为23小时，那么要在24小时内完成巡视，每组在路上的时间约为1小时。而汽车行驶速度为35km/h，故分成三组是完不成任务的。最少分为4组。经验证，分成四组是可行的。问题转化： 为将V分为 ，每组用时 ，最优分组应使得 最小。,求解步骤,利用问题一的解法，将V分为四组，使得每组用时相对均匀（以时间为权重），最终结果如下：各组在24小时内完成巡视，可见此分组可行。具体巡视路线如下：,模型求解之问题三,问题复述： 在上述关于T,t和V的假定下，如果巡视人员足够多，完成巡视的最短时间是多少；给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路线。,求解步骤（一）,如果巡视人员足够多，显然52个巡视人员分别巡视不同村镇可使使用时间最短。此时用Floyd算法可得结果如下（由图可知，巡视最短时间为6.394小时）,求解步骤（二）,显然，52个巡视员是浪费，因为很多较近的村镇可以被巡视较远村镇的巡视员顺路巡视，而又不影响最终完成巡视的最短时间。根据此思路可以减少一些巡视人员。具体如下：对巡视各个点所用时间从大到小遍历，每到一个点，检查O点到该点的最短路上有没有还没有被顺路巡视但可以被它顺路巡视(增加巡视该点不影响最短时间)的点，如果有，则至少增加一个巡视点。 下图即最佳的巡视路线，共分为24组。 红颜色标记的为巡视的村或乡镇。前20组走到终点后按原路返回。 由图可以看出，除了第二组外，各组所用时间比较均衡，所得结果是比较理想的。,结果如下：,求解步骤（三）,模型求解之问题四,问题复述： 若巡视组数已定(比如三组)，要求尽快完成巡视，讨论T,t和v改变对最佳巡视路线的影响。,求解步骤,基点确认：考虑的是各个顶点之间的距离的关系，因此T,t与v的改变并不影响基点的选择。初始分组：各点距基点的距离即各点到基点的时间成了判断标准，因此T和t的改变对于初始分组过程是没有影响的。而汽车的速度是相等不变的，因此v的改变对每个点的影响是相等的。因此，v也不影响初始分组过程。调整分组：T，t与v的改变都会对巡视时间产生影响，从而对分组的调整产生影响。因 ，其中Ti表示各组所用最短巡视时间，Ni表示各组顶点中乡镇的个数，ni表示各组顶点中村的个数。当T或t变大时，乡镇或村的个数对各组的用时的影响变大。同时，当决定把一个乡镇或村的点移入另一个分组时，该点对另一个组的最短时间的影响变大。当v变大时，顶点之间的距离对各组的用时的影响变小。,第三问的结果中第二组的用时与其他组相差太大，产生这种结果的原因是顺路过程中被顺的是离最远点最近的点。为了使时间均衡且更接近6.394，我们选择被顺点时改选为加上该点后会使得总时间最接近6.394的点。最后会使结果更均匀而且能使分组进一步减少到22组。,模型优化,模型中运用了Floyd算法与二边逐次修正法得到两点之间的最短距离和最佳哈密尔顿圈及顶点的分组，从而得到相关问题的解。虽然最佳推销员回路问题属于NP问题，没有精确算法，但是我们采用了近似算法简单易行，也得到了满意的结果。,模型评价,
