最优灾情巡视路线摘要关键字1问题重述下图为某县的乡（镇）、村公路网示意图，公路边的数字为该路段的公里数。
今年夏天该县遭受水灾。
为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视。
巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线。
问题一：若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。
问题二：假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度v=35公里/小时。
要在24小时内完成巡视，至少应分几组；给出这种分组下你认为最佳的巡视路线。
问题三：在上述关于T , t和v的假定下，如果巡视人员足够多，完成巡视的最短时间是多少；给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路线。
问题四：若巡视组数已定(如三组），要求尽快完成巡视，讨论T，t和v改变对最佳巡视路线的影响。
2问题假设与符号说明2.1问题假设假设一：假设在巡视过程中不考虑天气、故障等因素的影响假设二：假设路线上的公路没有被洪水冲断，可以供巡视工作使用。
假设三：假设在巡视工程中，经过邻县村时，不做任何时间的耽搁。
2.2符号说明3问题分析本题给出了某县的道路交通网络图，要求的是在不同条件下，灾情巡视的最佳分组方案和路线。
这是一类图上的点的遍历性问题，也就是要用若干条闭链覆盖图上所有的顶点，并使某些指标达到最优。
点的遍历性问题在图论中属于哈密顿问题和旅行推销员问题类似。
如果巡视人员只分一组，巡视路线是指巡视人员从县政府O 出发，走遍各乡（镇）、村最后又回到县政府。
我们可以把该题抽象为图论的赋权连通问题，即有一赋权无向连通图(,)G V E ，且O V ∈。
两村之间的公路长度即为无向图的边权()w e 。
寻找最佳巡视路线，即在图(,)G V E 中找到一条包含O 点的回路，它至少经过所有的顶点一次且使得总路程（总时间）最短。
针对问题一：如果将巡视人员分成三组，每组考察全县的一个区域，使所有乡（镇）、村都考察到，实际上就是将图(,)G V E 分为三个连通的子图i G ，且每个子图都与O 点相连，然后在每个子图中寻找到一条含O 点的最佳回路。
针对三组巡视成员，需对该县分为三个区域。
我们采用Prim 算法通过++C 编程求出G 图的最小树形图，然后将树形图分成三个区域，最后，采用哈密顿回路法求解每个子图内的最佳巡视路线。
针对问题二：完成巡视的时间应是各组巡视中最长的时间，要想提高巡视的效率则应尽量使各组的巡视时间接近，反映在G 图分块时应尽量均衡。
4数据的分析与处理5问题一的解答5.1模型一的准备现要分三组巡视，则需要把图G 分成三个子图(1,2,3)i G i =，在每个子图i G 中寻找最佳回路(1,2,3)i L i=。
因为最小生成树中能包含图G 中所有的顶点E ，而且最小树的边权是相邻两顶点间的距离，它描述了顶点之间的相近程度，故可以采用最小生成树进行分组。
本模型的主要思想是：首先采用Prim 算法得到G 图的最小生成树，然后基于最小生成树生成一个可行的巡视路线，求得路线的最优总路程为。
采用Prim 算法求解最小生成树步骤如下： （1）输入加权连通图G 的带权邻接矩阵((,))n n A a i j ⨯=；（2）建立初始候选边表, B T←∅；（3）在候选边表中选出最短边(,),(,)u v T T u v ←⋃；（4）调整候选边表B ；（5）重复（2），（3），直到T 含有1n -条边。
根据Kraskal 算法进行编程求解（具体程序见附录1），于是我们得到图G 的最小生成树如图1。
图1G并使得分解结果尽量均衡。
由现对已得到的最小生成树进行分解，以获得三个子图i于在最小生成树上，边权接近可以近似认为均衡即各子图包含的顶点数应接近。
因此，各个子图的顶点数应尽量接近17个，且遵循以下分解原则。
最小生成树分解原则：G的顶点数尽可能(i)分解点为O点或尽可能地接近O点；（ii）分解所得的三个子图iG与点O的最短地接近17个；（iii）尽量是分解所得的子图是连通图；（iv）尽量使子图i路上的点在该子图内，且尽量使各子图的点在子图内部形成环路。
依据以上分解原则得到的分解结果如图2。
图2然后，采用哈密顿回路法求解每个子图内的最佳巡视路线。
寻找最佳巡视路线实际上就是在赋权图中寻找最优的哈密顿圈，包含图G 的每个顶点的圈陈为哈密顿圈。
于是问题就可以转化为：现已知三个子图内乡、村与乡、村之间的距离，从县镇府O 出发，经过子图内的所有乡、村，最后又回到点O 。
5.2模型一的建立 5.2.1确定目标函数由题中所给出的问题条件，分析出这是3个售货员寻求最佳旅行回路的问题。
把县、乡、村所在地堪称借点，根据路线图可以构造一个赋权网络图[,,]G N E W =,其中}{}{}{0,1,2...52,(,),,(,),N E i j i j N W w i j i j N ==∈=∈.根据图论中的结论，最佳售货员回路问题可转化为最佳汉密尔顿()Hamilton 回路的问题。
在图G 的基础上构建三个子图i G ，于是在G 中寻求最佳回路的问题即在i G中寻找最佳()Hamilton 回路的问题，于是决策变量定义为:1 0 ij x ⎧=⎨⎩，选择从城市i 到城市j ，否则;其线性（整数）规划模型目标函数为：11minF n nij ij i j w x ===∑∑。
5.2.2确定约束条件目标函数给出了哈密顿圈的总长度，并使其最小。
约束式11niji x==∑保证只能到达每个城市一次，约束式11nijj x==∑保证只能离开一个城市一次，约束式1i j ij nx n μμ-+≤-( ,i j μμ为自定义变量)是表述问题的关键，它确保：（1）由解得到的任何圈一定包含城市1（即县镇府点O ）；（2）包含全部城市的圈是可行的。
于是，约束条件概括为：111 j=1,2,,n 1 i=1,2,,n . 1 i j, i,j=2,3,,n 0 1 i j, i,j=1,2,,n 0 j=1,2,,n 53nij i nij j ij ijij j x x s t nx n x n μμμ==⎧=⎪⎪⎪=⎪⎪⎨-+≤-≠⎪⎪=≠⎪≥⎪⎪=⎩∑∑L L L L L ，，，或， ，5.3综上所述，可得问题一的模型 目标函数：11minF n nij ij i j w x ===∑∑约束条件：111 j=1,2,,n 1 i=1,2,,n . 1 i j, i,j=2,3,,n 0 1 i j, i,j=1,2,,n 0 j=1,2,,n 53nij i nij j ij ijij j x x s t nx n x n μμμ==⎧=⎪⎪⎪=⎪⎪⎨-+≤-≠⎪⎪=≠⎪≥⎪⎪=⎩∑∑L L L L L ，，，或， ，5.4问题一的求解与结果分析按照上述思想写出相应的Lingo 程序（程序见附录2）求解得到三组巡视路线图见表2：5问题二的解答5.2模型二的准备此问添加了巡视组在各乡（镇）停留的时间2T =小时，在各村停留的时间1t =小时以及汽车的行驶速度35v=公里／小时的条件后，要求在24小时内完成巡视的最少分组数以及相应的最佳巡视路线。
此时需访问的乡（镇）共有17个，村共有35个，于是可以计算出巡视人员在乡（镇）及村停留的总时间为1723569⨯+=小时。
此外，从问题一的结果中可知，巡视的总路程至少为500公里，则汽车行驶所需的时间和将超过14小时。
由此可知，各组巡视所需的总时间之和超过83小时，要想在24小时内完成巡视则应满足： 8324i< (i 为分的组数)。
得i 最小为4，故至少要分4组。
现在尝试将顶点分成4组。
分组的原则应建立在最小生成树的分解原则之上，则分组应遵循以下原则：(i)分解点为O点或尽可能地接近O点；（ii）分解所得的4个子图的顶点G与点O 数尽可能地接近14个；（iii）尽量是分解所得的子图是连通图；（iv）尽量使子图i的最短路上的点在该子图内，且尽量使各子图的点在子图内部形成环路；（v）尽量使各组的巡视时间相接近。
依据以上分解原则得到的分解结果如图4。
采用上述原则将G图分为4个子图，并运用哈密顿回路法找出各个组的最佳巡视路线。
然后，计算出各组最佳巡视路线的总长度及汽车行驶所需时间，同时算出各组的停留时间,从而得到各组完成巡视的最佳时间。
5.3模型二的建立由题中所给出的问题条件，分析出这是4个售货员寻求最佳旅行回路的问题。
把县、乡、村所在地堪称借点，根据路线图可以构造一个赋权网络图[,,]G N E W =,其中}{}{}{0,1,2...52,(,),,(,),N E i j i j N W w i j i j N ==∈=∈.根据图论中的结论，最佳售货员回路问题可转化为最佳汉密尔顿()Hamilton 回路的问题。
在图G 的基础上构建三个子图i G ，于是在G 中寻求最佳回路的问题即在i G中寻找最佳()Hamilton 回路的问题，于是决策变量定义为:1 0 ij x ⎧=⎨⎩，选择从城市i 到城市j ，否则;其线性（整数）规划模型目标函数为：11minFn nij ij i j w x ===∑∑。
6问题三的解答 7模型的评价、改进与推广8参考文献 9附录。