哈密顿灾情巡视模型

灾情巡视路线模型摘要本题所研究的分组巡视的最佳路线与多个旅行推销员的问题相似，但也有不同，因为此题还有均衡性要求。这是一类图上的点的遍历性问题，即用若干条闭链覆盖图上所有的顶点，并使某些指标达到最优。首先，将乡村公路示意图转化为赋权连通图，并通过最小生成树法将原权图划分为若干个子图，然后，利用Hamilon圈法分别求出各个子图的最佳巡视路线。最后，利用本文中自定义的均衡度公式：maxmin()100%,maxAAAA为各组巡视路程或时间组成的集合，来衡量分组的均衡性，如果均衡度越小，那么分组的均衡性就越好，据此来判断分组是否满足题意。而题中，在基于最小生成树法将原权图划分为若干个子图的划分情况下，就必然使得总巡视路程相对较短，而均衡度不够令人满意，此时根据实际需要，若要使总巡视路程优先，达到相对较短，则采用原划分的子图分组；若要使均衡度优先，达到满意要求，则我们可以对各分组部分边界点进行重划分调整。针对问题一，我们分别采用直观分析法和最小生成树法求解并得到不同的结果。若分三组巡视，最小生成树法求解各组的巡视路程分别为159.3km、242.2km、186.4km，总路程为587.9km，路程均衡度为34%。此结果下的总路程相对较短，而均衡度偏高。如果要优先考虑均衡度，在最小生成树法求解发改进的基础上得到：194.0km、205.3km、206.8km，总路程为606.1km，路程均衡度为6.2%。针对问题二，基于计算可以发现至少分4组，并求出了各组的最佳巡视路线。各组巡视的路程和时间分别为125.5km／19.6h、154.3km／22.4h、203.9km／23.8h、158.8km／21.5h，时间均衡度为18%。针对问题三，我们选取了巡视离县城最远的乡镇（点H）所需的时间6.4小时作为最短巡视时间，当巡视比较偏僻的乡村时，汽车从县镇府出发直至到达终点，中途不会停留，仅在终点站停留T（或t）小时，然后按原路返回，到达沿途各站接回巡视人员。基于最短巡视时间和制定的分组原则得到巡视人员至少需分成7组。针对问题四，实际上是一个变量讨论问题。在分析乡（镇）停留时间T，村庄停留时间t和汽车行驶速度v的改变对最佳巡视路线的影响时，我们通过控制不同变量的变化，初步的得出了当T与t变化时和v变化时对最佳巡视路线的影响。最后，我们对模型进行了评价和推广，使其更具有实用价值。【关键词】：均衡度最小生成树Hamilon圈最佳巡视路线一、问题重述下图为某县的乡（镇）、村公路网示意图，公路边的数字为该路段的公里数。今年夏天该县遭受水灾。为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视。巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线。问题一：若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。问题二：假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度v=35公里/小时。要在24小时内完成巡视，至少应分几组；给出这种分组下你认为最佳的巡视路线。问题三：在上述关于T,t和v的假定下，如果巡视人员足够多，完成巡视的最短时间是多少；给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路线。问题四：若巡视组数已定(如三组），要求尽快完成巡视，讨论T，t和v改变对最佳巡视路线的影响。二、问题分析本题给出了某县的道路交通网络图，要求的是在不同条件下，灾情巡视的最佳分组方案和路线。这是一类图上的点的遍历性问题，也就是要用若干条闭链覆盖图上所有的顶点，并使某些指标达到最优。点的遍历性问题在图论中属于哈密顿问题和旅行推销员问题类似。如果巡视人员只分一组，巡视路线是指巡视人员从县政府O出发，走遍各乡（镇）、村最后油回到县镇府。我们可以把该题抽象为图论的赋权连通问题，即有一赋权无向连通图(,)GVE，且OV。两村之间的公路长度即为无向图的边权()we。寻找最佳巡视路线，即在图(,)GVE中找到一条包含O点的回路，它至少经过所有的顶点一次且使得总路程（总时间）最短。如果将巡视人员分成若干组，每组考察部分区域且所有乡（镇）、村都考察到，实际上就是将图(,)GVE分为若干个连通的子图iG，然后在每个子图中寻找到一条含O点的最佳回路。完成巡视的时间应是各组巡视中最长的时间，要想提高巡视的效率则应尽量使各组的巡视时间接近，反映在G图分块时应尽量均衡。三、模型假设1、公路不考虑等级差别，也不受灾情或交通情况的影响；2、各条公路段上汽车行驶的速度可以认为是均匀的；3、巡视人员在各乡（镇）、村停留的时间一定，不会出现特殊情况而延误时间；4、各巡视组巡视的乡（镇）、村不受行政区划的影响，即某乡（镇）与隶属于它的村不一定要分在同一组内5、忽略不计巡视人员上、下车所用的时间；6、当巡视比较偏僻的乡村时，汽车从县镇府出发直至到达终点，中途不会停留，仅在终点站停留T（或t）小时，然后按原路返回，到达沿途各站接回巡视人员。四、符号约定k:巡视人员的分组数;(,)GVE：赋权连通图；iG：赋权连通图的第i个子图(1,2,)i，k;iL：子图iG中的最佳回路；ic：最佳回路iL的各边权之和；ih：最佳回路iL的巡视时间;ijw：第i个乡、村到第j个乡、村的距离(j1,2,53)i，，；T：巡视员在各乡（镇）的停留时间；t：巡视人员在各村停留的时间；v：汽车行驶的速度，单位公里／小时。五、模型建立及模型求解5.1问题一模型的建立及求解：5.1.1模型一的建立与求解（直观分析法）：根据题中所给的乡（镇）、村示意图对地理位置进行粗略的划组分析。很显然，由于县政府位置偏向东面，则若分成三组巡视，县城远离的一边分为两块的可能性比邻近县城的一边大得多，这样就可以得到手工给出的三组巡视路线图见表1：表1编号路线路线长度/公里路线总长度/公里ⅠO-1-B-34-35-32-30-Q-28-27-26-P-29-R-31-33-A-1-O168.4ⅡO-M-25-N-24-23-21-K-22-17-16-I-15-I-18-J-19-20-L-6-5-2-O207.2594.3ⅢO-2-3-D-7-E-11-G-13-14-H-12-F-10-F-9-E-8-4-D-3-C-O218.7为了衡量分组的合理性，于是我们定义分组的路程均衡度公式：123123123max,,min,,max,,ccccccccc；显然01，值越小，说明分组的均衡性越好。由此我们可以得到采用直观分析法时的均衡度123%。5.1.2模型二的建立与求解（基于最小生成树法）现要分三组巡视，则需要把图G分成三个子图(1,2,3)iGi，在每个子图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并使得分解结果尽量均衡。由于在最小生成树上，边权接近可以近似认为均衡即各子图包含的顶点数应接近。因此，各个子图的顶点数应尽量接近17个，且遵循以下分解原则。最小生成树分解原则：(i)分解点为O点或尽可能地接近O点；（ii）分解所得的三个子图iG的顶点数尽可能地接近17个；（iii）尽量是分解所得的子图是连通图；（iv）尽量使子图iG与点O的最短路上的点在该子图内，且尽量使各子图的点在子图内部形成环路。依据以上分解原则得到的分解结果如图2。图2然后，采用哈密顿回路法求解每个子图内的最佳巡视路线。寻找最佳巡视路线实际上就是在赋权图中寻找最优的哈密顿圈，包含图G的每个顶点的圈陈为哈密顿圈。于是问题就可以转化为：现已知三个子图内乡、村与乡、村之间的距离，从县镇府O出发，经过子图内的所有乡、村，最后又回到点O。现在讨论如何将寻找最佳巡视路线问题表述成整数规划问题。但是，对于规模较大的寻找最佳巡视路线问题，这里的表述会显得笨拙且效率低下。决策变量定义为:10ijx，选择从城市i到城市j，否则;其线性（整数）规划模型目标函数为：11minnnijijijfwx。目标函数给出了哈密顿圈的总长度，并使其最小。约束式11nijix保证只能到达每个城市一次，约束式11nijjx保证只能离开一个城市一次，约束式1ijijnxn(,ij为自定义变量)是表述问题的关键，它确保：（1）由解得到的任何圈一定包含城市1（即县镇府点O）；（2）包含全部城市的圈是可行的。于是，约束条件概括为：111j=1,2,,n1i=1,2,,n.1ij,i,j=2,3,,n01ij,i,j=1,2,,n0j=1,2,,n53nijinijjijijijjxxstnxnxn，，，或，，按照上述思想写出相应的Lingo程序（程序见附录2）求解得到三组巡视路线图见表2：表2编号路线路线长度/公里路线总长度/公里ⅠO-P-26-27-28-30-Q-29-R-A-33-31-32-35-34-B-1-O159.3ⅡO-25-20-L-19-18-J-13-14-H-15-I-16-17-22-K-21-23-24-N-M-O242.2587.9ⅢO-2-5-6-7-E-11-G-12-10-F-9-8-4-D-3-C-O186.4由此我们可以得到采用最小生成树法时的路程均衡度234%。从上述图表中不难看出，第二组走的路程过长而第一组走的路程过短，两者之间的差值较大，也就是说这样分组的均衡性较差。因此，我们需在基于最小生成树的原则之上对原来的分组进行适当的调整。为了缩小第一、二组间的路程差，首先，我们将第二组的28点和N点分到第一组；然后，再采用Hamilton圈法分别求解三个子图内的最佳回路；最后，采用Lingo编程求解得到初步改进后三组巡视路线图见表3。表3编号路线路线长度/公里路线总长度/公里ⅠO-P-26-N-24-27-28-Q-30-29-R-A-33-31-32-35-34-B-1-O194.0ⅡO-23-21-K-22-17-16-18-I-15-H-14-13-J-19-L-20-25-M-O225.1605.5ⅢO-2-5-6-7-E-11-G-12-10-F-9-8-4-D-3-C-O186.4由此，可以计算出对模型二初步改进后的分组的均衡度为：217.2%。分析表3可知，第二组与第三组走的路程间的差值还是比较大，也就是说这样分组的均衡性还有待改善。于是，我们在基于最小生成树的原则之上对初步改进后的分组进行适当的调整。为了缩小第二、三组间的路程差，首先，我们将第二组的H点分到第三组；然后采用上述中同样的方法求解得到最终改进后各组的巡视路线图见表4。表4编号路线路线长度/公里路线总长度/公里ⅠO-P-26-N-24-27-28-Q-30-29-194.0R-A-33-31-32-35-34-B-1-OⅡO-M-N-23-21-K-22-17-16-18-I-15-14-13-J-19-L-20-25-M-O205.3606.1ⅢO-C-3-D-4-8-E-9-F-10-F-12-H-12-G-11-E-7-6-5-2-O206.8注：加有底纹的表示只经过此点但不停留。由此，可以计算出对模型二最终改进后的分组的均衡度为：26.2%。综上所述，对比模型一和改进