1、灾情巡视路线的数学模型摘要：本文建立了一个关于灾情巡视路线问题的数学模型。本文首先根据给定或自定的巡视的路数利用辐射线分块算法的一般分块原则将公路网分为几块，然后用 Floyd 算法以及 Hamilton 圈改良算法求出此种分块方法下各路的最短路线，并利用辐射线分块算法与题目要求调整分块方案使其更贴近题目要求。由此可得分三组时使总的巡视路线较小且各组的巡视路线长度相差尽可能小的巡视路线，其中各组的巡视路线长度（单位：公里）为： 210.3，219.5，205.3。证明了限时 24 小时时至少分 4 组，其巡视时间(单位：小时)分别为：23.27，22.29，23.01，23.82。人员足够多时
2、共分 22 组巡视灾情。所用最短巡视时间为：6.43 小时。经模型分析讨论可知，当巡视组数一定时，要尽快完成巡视，每个块内的乡村数与路程长度基本保持平衡。T ，t ，V 的同步变化对最佳巡视路线影响不大。、一问题重述（略）二问题的提出与分析此题目是要根据已给的约束条件，求解最合适的灾情巡视路线问题，并且有时还需将不同类型的点分开讨论。此问题可以被笼统的归纳为旅行销售员（TSPTraveling Salesman Problem）问题。当分组数目一定时，分析可知，要使总路程最短且各组尽可能均衡的巡视，则各组应“分头行动” ，即每组选取不同的出发方向，从而使重复路线缩短，少做“无用功” 。可以考虑
3、用恰当的方法通过对总的公路网分块的方式将此问题转化成几个小的旅行销售员（TSP）问题，选择合适的数学方法进一步求解。 （本题中利用的是Floyd 算法以及 Hamilton 圈改良算法）当巡视时间也成为巡视路线的一个参照因素时，要寻求最佳的巡视路线，则可考虑继续选用分块的方法分别求解各组的巡视路线。最小分组数应由总的停留时间与最短形式路程共同决定。可将最佳巡视路线定义为各组从出发到返回使用的时间相同（在实际问题中，工作人员的工作时间都是长短相同）当巡视人员足够多的情况下，则分组数目已不再是限制巡视路线的约束条件之一。要求最短巡视时间，则可将公路网中各点与起点的巡视时间最短的路线分别求出。由此时
4、的所需巡视时间最长的那几条巡视路线为基础选择最终的巡视路线，将剩下的巡视路线与最长的巡视时间比较，当巡视完既定的点后剩余时间多于一个小时，则可以利用这段空闲时间巡访其他的点，由此可以减少巡访的组数。由此一步步推导，最终可得出最佳巡视路线。此时的最佳巡视路线可定义为，在最短时间内用尽可能少的组数完成巡视任务。此处，将最佳路线定义为：在最短巡视时间内尽可能减少人力车力浪费的巡视路线。 （实际中的人力充足时也需要尽量节省，尽量不造成路线重复也不造成人员浪费）当巡视组数一定的情况下尽可能快的完成巡视，此时对 T，t，V 的灵敏度分析即可得到它们对最佳巡视路线的影响。易知此问题解决的关键在于找到合适的分
5、块方法与给定待求点后的最短巡视路线求解方法。三模型假设：1计算时将各地看作一可忽略大小的点。即，不计在镇乡（或村）内部的行驶距离及时间。2每条路均可正常通行。3汽车以 35 公里/小时保持匀速行驶。4巡视人员在各乡（镇）的停留时间为 T=2 小时，并且巡视人员在各村的停留时间为 t=1 小时5分块后，各组巡视人员除公共起点外，不巡视相同的地点。四符号约定：公路网中的边ije：公路网中的结点i：边 的边权（路线长度）ij(e)ij：结点 的点权（停留时间）iiijEe(,):jVG： 连 通 图 各 边 的 集 合0123n, ： 连 通 图 结 点 的 集 合ijW(,):()E:连 通 图
6、各 边 权 值 的 集 合：加权图 中的最佳巡视路线LG： 加权图 中最佳巡视路线的长度（公里） S（或 ）：公路网中各待巡视点ij( , )：公路网中各待巡视点间的公路长（也称各边的权值）ij五模型的建立：本模型的建立基于最短路问题及行遍性问题的有关理论。设 G=（V,E,W）是以 V 为顶点集，以 E 为边集，以 W 为权值集的连通图。取 。P 是图 G 中从 出发经过mi12i3in0V,(mn), V0中所有结点，返回到 的所有闭链组成的集合（每条闭链为 P 中的元） ，0，且 ，其中 表示 上的结点， 表示 上的边集。spPms(p)spssEps分别对各问题建立目标函数：（1） i
7、j(i,j)E(P):pMn(e)（2） inE(P):p （3） oi jiE(P):p(e)/V()为了后面讨论方便，给出如下定义：定义 1 设 G=(V,E)是连通无向图（1）经过 G 的每个顶点正好一次的路径，称为 G 的一条哈密尔顿路径（2）经过 G 的每个顶点正好一次的圈，称为 G 的哈密尔顿圈或 H 圈（3）含 H 圈的图称为哈密尔顿图或 H 图定义 2 在加权图 G=(V,E)中，（1）权最小的哈密尔顿圈称为最佳 H 圈（2）经过每个顶点至少一次的权最小的闭通路称为最佳推销员回路一般说来，最佳哈密尔顿圈不一定是最佳推销员回路，同样最佳推销员回路也不一定是最佳哈密尔顿圈定义 3：
8、（） 端点相同的边称为环（） 若一对顶点之间有两条以上的边联结，则这些边称为重边（） 有边联结的两个顶点称为相邻的顶点，有一个公共端点的边称为相邻的边（） 边和它的端点称为互相关联的 （） 既没有环也没有平行边的图，称为简单图 （） 任意两顶点都相邻的简单图，称为完备图，记为 Kn，其中 n为顶点的数目我们不加证明的引用：引理 1： 在加权图 G=(V,E)中，若对任意 x,y,z V，z x,z y,都有+ ，则图 G 的最佳 H 圈也是最佳推销员回路用图xyexzzye论的术语说，就是在一个赋权完全图中，找出一个有最小权的 Hamilton 圈。称这种圈为最优圈。与最短路问题及连线问题相反
9、，目前还没有求解旅行商问题的有效算法。所以希望有一个方法以获得相当好（但不一定最优）的解。一个可行的办法是首先求一个 Hamilton 圈 ，然后适当修改 以得到CC具有较小权的另一个 Hamilton 圈。修改的方法叫做改良圈算法。设初始圈。121vCn最佳推销员回路问题可转化为最佳 H 圈问题方法是由给定的图G=(V,E)构造一个以 V 为顶点集的完备图 G=(V,E)，E的每条边 的xye权等于顶点 x 与 y 在图中最短路的权即：x,y E, =minxyeGxyLe引理 2： 加权图 G 的最佳推销员回路的权与 G的最佳 H 圈的权相同六模型的求解：寻找此种问题的解的一种可靠的方法是
10、首先列出所有候选解，然后依次检查每一个，在检查完所有或部分候选解后，即可找到所需要的解。理论上，当候选解数量有限并且通过检查所有或部分候选解能够得到所需解时，上述方法是可行的。不过，在实际应用中，很少使用这种方法，因为候选解的数量通常都非常大（比如指数级，甚至是大数阶乘） ，即便采用最快的计算机也只能解决规模很小的问题。因此，先利用辐射线分块算法的有关原则将公路网分成相应的几部分，再利用最短路径（Floyd 算法）和行遍性（二次逐边修正算法）的有关知识将每一块里的最优巡视方案求解出来。求解最短路径的方法（Floyd 算法）的编程思路：若 ，则点 p1 是点 i 到点 j 的最短路的中间点.1)
11、(rij然后用同样的方法再分头查找若：（1）向点 i 追朔得： , ,2)(1rip3)(pikiprk)(（2）向点 j 追朔得： , ,)(1qj 2)(1j jqm)(则由点 i 到 j 的最短路的路径为： 21,2, ,k mipqj D(i,j)：i 到 j 的距离R(i,j)：i 到 j 之间的插入点具体编程步骤：Step 1 输入: 带权邻接矩阵 w(i,j)Step 2 赋初值：对所有 i,j, d(i,j) w(i,j), r(i,j) j, k 1Step 3 更新 d(i,j), r(i,j). 对所有 i,j，若 d(i,k)+d(k,j)所以至少需要四个巡视组就可以完成任务。由于停驻时间的加入，此时辐射线分块算法对公路网的划分仅能起到一定的参照作用。在考虑每块内的路线基本相同长短的同时也要考虑到停驻时间对分块方案的影响。经分析与验证，最终得到的分块结果如下图：
