哈密顿灾情巡视模型

1、数学建模课 程 论 文学生 潘在裕 成绩 灾情巡视路线模型摘要本题所研究的分组巡视的最佳路线与多个旅行推销员的问题相似，但也有不同，因为此题还有均衡性要求。这是一类图上的点的遍历性问题，即用若干条闭链覆盖图上所有的顶点，并使某些指标达到最优。首先，将乡村公路示意图转化为赋权连通图，并通过最小生成树法将原权图划分为若干个子图，然后，利用Hamilon圈法分别求出各个子图的最佳巡视路线。最后，利用本文中自定义的均衡度公式：，来衡量分组的均衡性，如果均衡度越小，那么分组的均衡性就越好，据此来判断分组是否满足题意。而题中，在基于最小生成树法将原权图划分为若干个子图的划分情况下，就必然使得总巡视路程相对

2、较短，而均衡度不够令人满意，此时根据实际需要，若要使总巡视路程优先，达到相对较短，则采用原划分的子图分组；若要使均衡度优先，达到满意要求，则我们可以对各分组部分边界点进行重划分调整。针对问题一，我们分别采用直观分析法和最小生成树法求解并得到不同的结果。若分三组巡视，最小生成树法求解各组的巡视路程分别为159.3km、242.2km、186.4km，总路程为587.9km，路程均衡度为34%。此结果下的总路程相对较短，而均衡度偏高。如果要优先考虑均衡度，在最小生成树法求解发改进的基础上得到：194.0km、205.3km、206.8km，总路程为606.1km，路程均衡度为6.2%。针对问题二，

3、基于计算可以发现至少分4组，并求出了各组的最佳巡视路线。各组巡视的路程和时间分别为125.5km19.6h、154.3km22.4h、203.9km23.8h、158.8km21.5h，时间均衡度为18%。针对问题三，我们选取了巡视离县城最远的乡镇（点H）所需的时间6.4小时作为最短巡视时间，当巡视比较偏僻的乡村时，汽车从县镇府出发直至到达终点，中途不会停留，仅在终点站停留T（或t）小时，然后按原路返回，到达沿途各站接回巡视人员。基于最短巡视时间和制定的分组原则得到巡视人员至少需分成7组。针对问题四，实际上是一个变量讨论问题。在分析乡（镇）停留时间T，村庄停留时间t和汽车行驶速度v的改变对最佳

4、巡视路线的影响时，我们通过控制不同变量的变化，初步的得出了当T与t变化时和v变化时对最佳巡视路线的影响。最后，我们对模型进行了评价和推广，使其更具有实用价值。【关键词】： 均衡度 最小生成树 Hamilon圈 最佳巡视路线一、问题重述下图为某县的乡（镇）、村公路网示意图，公路边的数字为该路段的公里数。今年夏天该县遭受水灾。为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视。巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线。问题一：若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。 问题二：假定巡视人员在各乡（镇）停留时间T=2小

5、时，在各村停留时间t=1小时，汽车行驶速度v=35公里/小时。要在24小时内完成巡视，至少应分几组；给出这种分组下你认为最佳的巡视路线。 问题三：在上述关于T , t和v的假定下，如果巡视人员足够多，完成巡视的最短时间是多少；给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路线。 问题四：若巡视组数已定(如三组），要求尽快完成巡视，讨论T，t和v改变对最佳巡视路线的影响。二、问题分析本题给出了某县的道路交通网络图，要求的是在不同条件下，灾情巡视的最佳分组方案和路线。这是一类图上的点的遍历性问题，也就是要用若干条闭链覆盖图上所有的顶点，并使某些指标达到最优。点的遍历性问题在图论中属于哈密顿问

6、题和旅行推销员问题类似。如果巡视人员只分一组，巡视路线是指巡视人员从县政府O出发，走遍各乡（镇）、村最后油回到县镇府。我们可以把该题抽象为图论的赋权连通问题，即有一赋权无向连通图，且。两村之间的公路长度即为无向图的边权。寻找最佳巡视路线，即在图中找到一条包含O点的回路，它至少经过所有的顶点一次且使得总路程（总时间）最短。如果将巡视人员分成若干组，每组考察部分区域且所有乡（镇）、村都考察到，实际上就是将图分为若干个连通的子图，然后在每个子图中寻找到一条含O点的最佳回路。完成巡视的时间应是各组巡视中最长的时间，要想提高巡视的效率则应尽量使各组的巡视时间接近，反映在图分块时应尽量均衡。三、模型假设1

7、、公路不考虑等级差别，也不受灾情或交通情况的影响；2、各条公路段上汽车行驶的速度可以认为是均匀的；3、巡视人员在各乡（镇）、村停留的时间一定，不会出现特殊情况而延误时间；4、各巡视组巡视的乡（镇）、村不受行政区划的影响，即某乡（镇）与隶属于它的村不一定要分在同一组内5、忽略不计巡视人员上、下车所用的时间；6、当巡视比较偏僻的乡村时，汽车从县镇府出发直至到达终点，中途不会停留，仅在终点站停留T（或t）小时，然后按原路返回，到达沿途各站接回巡视人员。四、符号约定: 巡视人员的分组数;：赋权连通图；：赋权连通图的第个子图;：子图中的最佳回路；：最佳回路的各边权之和；：最佳回路的巡视时间;：第个乡、村

8、到第个乡、村的距离；：巡视员在各乡（镇）的停留时间；：巡视人员在各村停留的时间；：汽车行驶的速度，单位公里小时。五、模型建立及模型求解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.4O-M-25-N-24-23-2

9、1-K-22-17-16-I-15-I-18-J-19-20-L-6-5-2-O207.2 594.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为了衡量分组的合理性，于是我们定义分组的路程均衡度公式 ：；显然，值越小，说明分组的均衡性越好。由此我们可以得到采用直观分析法时的均衡度。5.1.2模型二的建立与求解（基于最小生成树法）现要分三组巡视，则需要把图分成三个子图，在每个子图中寻找最佳回路。因为最小生成树中能包含图中所有的顶点，而且最小树的边权是相邻两顶点间的距离，它描述了顶点之间的相近程度，故可以采用最小生成树进行分组。

10、本模型的主要思想是：首先采用Prim算法得到图的最小生成树，然后基于最小生成树生成一个可行的巡视路线，求得路线的最优总路程为。采用Prim算法求解最小生成树步骤如下：（1）输入加权连通图的带权邻接矩阵；（2）建立初始候选边表；（3）在候选边表中选出最短边；（4）调整候选边表；（5）重复（2），（3），直到含有条边。根据Prim算法进行编程求解（具体程序见附录1），于是我们得到图的最小生成树如图1。图1现对已得到的最小生成树进行分解，以获得三个子图并使得分解结果尽量均衡。由于在最小生成树上，边权接近可以近似认为均衡即各子图包含的顶点数应接近。因此，各个子图的顶点数应尽量接近17个，且遵循以下分解

11、原则。最小生成树分解原则：(i)分解点为O点或尽可能地接近O点；（ii）分解所得的三个子图的顶点数尽可能地接近17个；（iii）尽量是分解所得的子图是连通图；（iv）尽量使子图与点O的最短路上的点在该子图内，且尽量使各子图的点在子图内部形成环路。依据以上分解原则得到的分解结果如图2。 图2然后，采用哈密顿回路法求解每个子图内的最佳巡视路线。寻找最佳巡视路线实际上就是在赋权图中寻找最优的哈密顿圈，包含图的每个顶点的圈陈为哈密顿圈。于是问题就可以转化为：现已知三个子图内乡、村与乡、村之间的距离，从县镇府O出发，经过子图内的所有乡、村，最后又回到点O。现在讨论如何将寻找最佳巡视路线问题表述成整数规划

12、问题。但是，对于规模较大的寻找最佳巡视路线问题，这里的表述会显得笨拙且效率低下。决策变量定义为:;其线性（整数）规划模型目标函数为：。目标函数给出了哈密顿圈的总长度，并使其最小。约束式保证只能到达每个城市一次，约束式保证只能离开一个城市一次，约束式( 为自定义变量)是表述问题的关键，它确保：（1）由解得到的任何圈一定包含城市1（即县镇府点O）；（2）包含全部城市的圈是可行的。于是，约束条件概括为：按照上述思想写出相应的Lingo程序（程序见附录2）求解得到三组巡视路线图见表2：表2编号路线路线长度/公里路线总长度/公里O-P-26-27-28-30-Q-29-R-A-33-31-32-35-3

13、4-B-1-O159.3O-25-20-L-19-18-J-13-14-H-15-I-16-17-22-K-21-23-24-N-M-O242.2 587.9 O-2-5-6-7-E-11-G-12-10-F-9-8-4-D-3-C-O186.4由此我们可以得到采用最小生成树法时的路程均衡度。从上述图表中不难看出，第二组走的路程过长而第一组走的路程过短，两者之间的差值较大，也就是说这样分组的均衡性较差。因此，我们需在基于最小生成树的原则之上对原来的分组进行适当的调整。为了缩小第一、二组间的路程差，首先，我们将第二组的28点和N点分到第一组；然后，再采用Hamilton圈法分别求解三个子图内的最

14、佳回路；最后，采用Lingo编程求解得到初步改进后三组巡视路线图见表3。表3编号路线路线长度/公里路线总长度/公里O-P -26-N -24-27-28-Q-30-29-R-A-33-31-32-35-34-B-1-O194.0O-23-21-K-22-17-16-18-I-15-H-14-13-J-19-L- 20-25-M-O225.1 605.5 O-2-5-6-7-E-11-G-12-10-F-9-8-4-D-3-C-O186.4由此，可以计算出对模型二初步改进后的分组的均衡度为：。分析表3可知，第二组与第三组走的路程间的差值还是比较大，也就是说这样分组的均衡性还有待改善。于是，我们在

15、基于最小生成树的原则之上对初步改进后的分组进行适当的调整。为了缩小第二、三组间的路程差，首先，我们将第二组的H点分到第三组；然后采用上述中同样的方法求解得到最终改进后各组的巡视路线图见表4。表4编号路线路线长度/公里路线总长度/公里O-P -26-N -24-27-28-Q-30-29-R-A-33-31-32-35-34-B-1-O194.0O-M-N-23-21-K-22-17-16-18-I-15-14-13-J-19-L- 20-25-M-O205.3 606.1 O-C-3-D-4-8-E-9-F-10-F-12-H-12-G-11-E-7-6-5-2-O206.8注：加有底纹的表示

16、只经过此点但不停留。由此，可以计算出对模型二最终改进后的分组的均衡度为：。综上所述，对比模型一和改进后模型二的结果可知，若分成三组巡视，虽然改进后模型二的巡视总路程比模型一的长，但是，改进后模型二分组的均衡性比模型一要好很多。此外，模型二的结果是经过严谨科学的计算得到的，具有较高的可信度，相比之下，模型一的结果是人根据地理位置粗略划分得到地，具有随机性，可信度较低。经上述分析可知，若分成三组巡视，则应该采用改进后模型二的巡视路线,见图3。图35.2问题二的模型建立及求解：此问添加了巡视组在各乡（镇）停留的时间小时，在各村停留的时间小时以及汽车的行驶速度公里小时的条件后，要求在24小时内完成巡视

17、的最少分组数以及相应的最佳巡视路线。此时需访问的乡（镇）共有17个，村共有35个，于是可以计算出巡视人员在乡（镇）及村停留的总时间为小时。此外，从问题一的结果中可知，巡视的总路程至少为500公里，则汽车行驶所需的时间和将超过14小时。由此可知，各组巡视所需的总时间之和超过83小时，要想在24小时内完成巡视则应满足： (i为分的组数)。得i最小为4，故至少要分4组。 现在尝试将顶点分成4组。分组的原则应建立在最小生成树的分解原则之上，则分组应遵循以下原则：(i)分解点为O点或尽可能地接近O点；（ii）分解所得的4个子图的顶点数尽可能地接近14个；（iii）尽量是分解所得的子图是连通图；（iv）尽

18、量使子图与点O的最短路上的点在该子图内，且尽量使各子图的点在子图内部形成环路；（v）尽量使各组的巡视时间相接近。采用上述原则将图分为4个子图，并运用哈密顿回路法找出各个组的最佳巡视路线。然后，计算出各组最佳巡视路线的总长度及汽车行驶所需时间，同时算出各组的停留时间,从而得到各组完成巡视的最佳时间。基于此，可以采用Lingo软件进行编程求解（程序见附录3）得到4个组的巡视路线，并计算出各组巡视的总时间，具体数据见表3。表3（路程单位：公里；时间单位：小时）编号路线路线长度停留时间行驶时间总时间O-1-B-A-34-35-33-31-32-30-Q-29-R-O125.5163.619.6O-P-

19、28-27-26-N-24-23-22-17-16-17-K-21-25-M-O154.3184.422.4O-M-20-18-I-15-14-H-12-G-11-G-13-J-19-L-20-M-O203.9185.823.8O-2-5-6-7-E-9-F-10-F-9-E-8-4-D-3-C-O158.8174.521.5注：加有底纹的表示只经过此点但不停留。从上述图表中可以看出所分的四个组的巡视时间均小于24小时，符合题意。此外，计算得到该分组的时间均衡度公式为： ；此时，计算得到均衡度：。在此基础上，我们可以得到有时间约束的最佳巡视路线如图4。图45.3问题三的模型建立及求解：此问题就

20、是要求如果有足够多的巡视人员，怎样确定最佳路线是完成巡视的时间最短。实际上，完成巡视的最短时间受到单独巡视离县城最远的乡（镇）、村所需时间的制约，同时我们可以求出离县城最远的点是H点，距离为77.5公里。因此，单独巡视返回该乡所需的时间为小时。由此可知，即使巡视人员再多，分组再细，完成巡视至少需要6.4小时。基于此，此题就可以转化为求在6.4小时内完成巡视的最少分组数和最佳巡视路线。为达到以上目标，我们制定了以下分组巡视原则：1、对图中偏西且距县政府较远的乡（镇）、村：（1）在6.4小时内，每组巡视人员尽可能走足够多的乡（镇）、村。 （2）在巡视时，尽量按出发点到该次巡视终点最短路径的路线巡视

21、，但在不超过6.4小时的原则下，为了能够途经更多的点，我们可以不走最短路线。（3）巡视车从县政府出发，途中每到达一个乡（镇）、村，部分巡视人员下车巡视，车不停留（忽略不计巡视人员上、下车的时间）继续开往下个站点，直到到达最远点，车停下等待；然后按原路返回，依次到达每点接回巡视人员，直至出发点。2、由于第一种分组原则下，在最远点必须要花1或者2个小时的停留时间，针对这一浪费时间的缺点，对图中偏东且距县政府较近的乡、村，我们改进一种按圈巡视的方法，原则如下：（1）每组巡视人员巡视路线构成一个圈，且巡视两圈。（2）第一圈巡视时，途中每到达一个乡（镇）、村，部分巡视人员下车巡视，车不停留（忽略不计巡视

22、人员上、下车的时间）继续开往下个站点，直至出发点，仍不停留继续第二圈巡视，到达每点依次接回巡视人员，直至回到出发点，结束。（3）在遵循不超过6.4小时原则下，按圈巡视时，总路线不能过长，不超过112公里；总路线也不能过短，避免车停留等待而浪费时间。依据以上原则，我们在6.4小时内完成巡视，总共分成了7组，前5组遵循的第一种分组原则，后2组依据的第二种按圈分组原则。具体的分组巡视路线和所需时间见表4。表4（时间单位：小时）编号路线总时间O-2-5-6-7-E-9-F-12-H-14-H-12-F-9-E-7-6-5-2-O6.43O-M-25-20-21-K-18-I-15-I-18-K-21-

23、20-25-M-O5.87O-2-5-6-L-19-J-13-G-11-G-13-J-19-L-6-5-2-O6.15O-2-3-D-4-8-E-9-F-10-F-9-E-8-4-D-3-2-O6.38O-P-28-27-26-N-24-23-22-17-16-17-22-23-24-N-26-27-28-P-O6.37O-R-31-33-A-1-C-O-R-31-33-A-1-C-O4O-R-29-Q-30-32-35-34-B-1-O-O-R-29-Q-30-32-35-34-B-1-O5.64注：加有底纹的表示经过此点但无巡视人员上、下车。由此可以计算出此种分组下的时间均衡度为：。基于此

24、，我们可以得到巡视人员足够多的情况下分成7组的最佳巡视路线如图5。图55.4问题四的模型建立及求解：第四问要求在巡视组数已定的情况下尽快完成巡视，讨论参数T，t和v的改变对最佳巡视路线的影响。前面我们已经提到，要尽快完成巡视，即要求各组巡视时间的最大值也要最小。用数学式子表达为：；其中：是给定的分组数；：分别是第组停留的乡(镇)数和村数；：第组巡视路线的总长度。在上述表达式中，由于T和t的作用完全相仿，所以为简化讨论起见，对于任意给定的T和t，不妨记。即这里可简记为：；它是t和的的线性函数，将随着t和增大(即v的减小)而增大.于是我们容易得到以下结论：（1）若t（T）增大而V不变，为了使最大值

25、尽可能小，就要求的最大值尽可能小.但是当T和t的关系确定后，实际上就是定值，其中m是全县的乡(镇)数17，n是全县的村数35。上述要求就成为各组停留在询问乡村的总时间尽可能均匀.用数学式子表示即为:；这里表示数的下整数和上整数.当然，在调整各组停留的乡村数使之达到均衡时，自然会给各组的路线及其长度带来影响.这时应当考虑进行适当调整。（2）若t（T）不变而v增大.这种情况下，今起主导作用。那么，和（1）中的结论类似，我们更应使即各组的巡视路线尽可能均衡。诚然，因为不是常数，而且的均衡性会带来的增大，这对于尽快完成巡视会带来负面影响。所以对具体情况应作具体分析，比如可以考虑的前半部份对均衡性的修正

26、，对路程较长的组尽量考虑停留较少乡村。六、模型的推广在现实生活和生产中，有许多管理、组织与计划中的优化问题，如企业管理中，如何制订管理计划或设备购置计划，使收益最大或费用最小；在生产管理中，如何使各工序衔接好，才能使生产任务完成的既快又好；在交通管理中，如何利用现有的交通网络，使调用的物资数量多且费用最小等。这类问题都可以借助图论知识得以解决。网络模型就是一种应用图论的理论与方法解决具有网络性质的管理决策问题的数学模型。由于它具有图形直观、方法简便、容易掌握等特点，因此，近年来得到迅速发展，且广泛地应用在各个领域，尤其是经济活动中许多管理决策的优化问题。基本的网络优化问题有：最短路径问题、最小

27、支撑树问题、最大流问题和最小费用问题。在图论这个数学分支中已经有有效的算法来解决这些问题，当然这当中有很多问题都可以建立线性规划的模型，但有时若变量特别多、约束也特别多，用线性规划的方法求解效率不高甚至不能在忍受的时间内解决。根据这些问题的特点，采用网络分析的方法去求解可能会非常有效。七、模型的评价优点：本文多处使用图表，增强了文章的可读性，使建模思想更加清晰易懂。在问题三的求解中，我们假定当巡视比较偏僻的乡村时，汽车从县镇府出发直至到达终点，中途不会停留，仅在终点站停留T（或t）小时，然后按原路返回，到达沿途各站接回巡视人员，这样考虑可以避免车停留等待而浪费时间，提高巡视效率。缺点：采用最小

28、生成树求解最小回路，并采用Hmilton圈法求解各子图内的最佳回路，虽然分组的均衡度比较理想，但求的不是全局最优解。当顶点数目比较多（大于等于20）时，采用Lingo软件针对Hailton圈法编程时，程序执行的速度较慢，效率不高。(3) 本文仅仅是针对具体问题具体分析，有一定的局限性；虽然也是采用图论法解决，但与图论中的经典旅行推销员模型有所区别，在实际应用中，应对各种情况作进一步分析不断对模型加以优化，才会使其更具适用性。八、参考文献及附录【1】数学建模原理与方法，蔡锁章，海洋出版社，2000.6【2】运筹学与实验，薛毅，耿美英，电子工业出版社，2008.9【3】数学的实践与认识（第29卷第

29、1期），田家国等，1999.1附录1：D=xlsread('shuju.xls')n=53;T=;l=0;%l记录T的列数q(1)=-1;for i=2:n p(i)=1;q(i)=D(i,1);endk=1;while 1 if k>=n disp(T); break; else min=inf; for i=2:n if q(i)>0&q(i)<min min=q(i); h=i; end end end l=l+1; T(1,l)=h;T(2,l)=p(h); q(h)=-1; for j=2:n if D(h,j)<q(j) q(j)=D

30、(h,j); p(j)=h; end end k=k+1;end附录2：sets:c/1.17/:u;link(c,c):w,x;endsetsdata:w=ole('第一组数据.xls','dier');enddatan=size(c);min=sum(link:w*x);for(c(k):sum(c(i)|i#ne#k:x(i,k)=1;sum(c(j)|j#ne#k:x(k,j)=1;);for(link(i,j)|i#gt#1 #and# j#gt#1 #and# i#ne#j:u(i)-u(j)+n*x(i,j)<=n-1);for(link:b

31、in(x);endsets:c/1.17/:u;link(c,c):w,x;endsetsdata:w=ole('第二组数据.xls','dier');enddatan=size(c);min=sum(link:w*x);for(c(k):sum(c(i)|i#ne#k:x(i,k)=1;sum(c(j)|j#ne#k:x(k,j)=1;);for(link(i,j)|i#gt#1 #and# j#gt#1 #and# i#ne#j:u(i)-u(j)+n*x(i,j)<=n-1);for(link:bin(x);endsets:c/1.17/:u;link(c,c):w,x;endsetsdata:w=ole('第三组数据.xls','dier');enddatan=size(c);min=sum(link:w*x);for(c(k):sum(c(i)|i#ne#k:x(i,k)=1;sum(c(j)|j#ne#k:x(k,j)=1;);for(link(i,j)|i#gt#1 #and# j#gt#1 #and# i#ne#j:u(i)-u(j)+n*x(i,j)<=n-1);for(link:bin(x);end附录3：sets:c/1.13/:u;link(c,c):w,x;en