灾情巡视路线的数学模型12组.doc

最优灾情巡视路线摘要本文解决的是灾情巡视路线的最佳安排问题，我们将其转化为多个推销员回路问题，并针对灾情巡视的不同要求，用哈密顿法求出了各情况下的近似最优解。针对问题一：本文采用法求出最小生成树图，然后以最小生成树为依据将该县分为三个区域，分别对应三组巡视人员。然后利用哈密顿法求解出各组最短的巡视路程，分别为第一组197.6km、第二组196.8km、第三组206.8km，总路程为601.2km。最后用本文中自定义的路程均衡度来衡量分组的均衡性，路程均衡度为5.0%，各组的均衡性很好。针对问题二：本文在解决问题一的基础上，将该县分为四个区域。然后利用哈密顿法求解出四个区域的最短巡视路程，进而求出巡视时间和停留时间，得到各组的巡视总时间，分别为第一组21.1小时、第二组22.5小时、第三组23.0小时、第四组21.5小时。其中时间均衡度为8.6%，满足题目要求。 针对问题三：本文分析得出，巡视的最短时间为6.43小时，然后我们根据最短时间并依据最小生成树图将巡视人员分为七组，在新的巡视规则下很好的完成了巡视任务。各组的巡视路线和停留点时间如下表:组号巡视路线时间/小时16.4325.8736.1546.3856.3765.3875.48 针对问题四：本文在不破坏原来分组均衡性的条件下，讨论了对分组的影响，并得出的最大变化范围。最后根据得出的结论对分三组的实例进行定量分析，验证了结论的可行性。关键字 1问题重述 下图为某县的乡（镇）、村公路网示意图，公路边的数字为该路段的公里数。今年夏天该县遭受水灾。为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视。巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线。 问题一：若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。 问题二：假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度v=35公里/小时。要在24小时内完成巡视，至少应分几组；给出这种分组下你认为最佳的巡视路线。 问题三：在上述关于T , t和v的假定下，如果巡视人员足够多，完成巡视的最短时间是多少；给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路线。 问题四：若巡视组数已定(如三组），要求尽快完成巡视，讨论T，t和v改变对最佳巡视路线的影响。 2问题假设与符号说明2.1问题假设假设一：假设在巡视过程中不考虑天气、故障等因素的影响假设二：假设路线上的公路没有被洪水冲断，可以供巡视工作使用。假设三：假设在巡视工程中，经过邻县村时，不做任何时间的耽搁。假设四：巡视人员上下车的时间忽略不记。假设五：当巡视比较偏僻的乡村时，汽车从县镇府出发直至到达终点，中途不会停留，仅在终点站停留T（或t）小时，然后按原路返回，到达沿途各站接回巡视人员。2.2符号说明赋权连通图；赋权连通图的第个子图子图中的最佳回路；最佳回路的各边权值之和第个乡、村到第个乡、村的距离某组从城市到城市时为1，无巡视组视为0表示各乡（镇）停留时间表示各村停留时间 3问题分析本题给出了某县的道路交通网络图，要求的是在不同条件下，灾情巡视的最佳分组方案和路线。这是一类图上的点的遍历性问题，也就是要用若干条闭链覆盖图上所有的顶点，并使某些指标达到最优。点的遍历性问题在图论中属于哈密顿问题，和旅行推销员问题类似。我们可以把该题抽象为图论的赋权连通问题，即有一赋权无向连通图，且。两村之间的公路长度即为无向图的边权。寻找最佳巡视路线，即在图中找到一条包含O点的回路，它至少经过所有的顶点一次，且使得总路程或总时间最短。对于问题一：如果将巡视人员分成三组，每组考察全县的一个区域，使所有乡（镇）、村都考察到，实际上就是将图分为三个连通的子图，且每个子图都与O点相连，然后在每个子图中寻找到一条含O点的最佳回路。针对三组巡视成员，需对该县分为三个区域。我们采用算法通过编程求出图的最小树形图，然后将树形图分成三个区域，最后，采用哈密顿回路法求解每个子图内的最佳巡视路线。对于问题二：在问题一的基础上，问题二增加了巡视人员在各乡（镇）、村停留时间以及汽车途中行驶时间，并要求在24小时内完成巡视，求最佳分组和最佳巡视路线使各组的时间均衡性较好。通过分析可得要使巡视人员在24小时内完成巡视，则巡视人员至少分四组，然后根据最小树形图，将整个区域分成四个区域，利用最佳哈密顿回路法，求解每个子图的最佳巡视路线和最短巡视时间。最后利用定义的均衡度公式求出时间均衡度，根据求出的均衡度判断各组是否均衡，若均衡度较大，说明分组不够均衡，需要继续改进直至时间均衡度在允许的范围内。对于问题三：此问题就是要求如果有足够多的巡视人员，怎样确定最佳路线使完成巡视的时间最短。实际上，完成巡视的时间受到巡视最远乡（镇）、村路途时间和在乡（镇）、村停留时间的制约。通过分析可以求出巡视镇花费的时间最长，为6.43小时。由此可知，即使巡视人员再多，分组再细，完成巡视至少需要6.43小时。于是我们制订了两种分组巡视原则：对图中偏西且距县政府较远的乡（镇）、村，巡视车开往最远巡视乡（镇）、村，并在途经乡村放下巡视员，到达最远乡镇后等待，然后按原路返回并且依次接回巡视员；对图中偏东且距县政府较近的乡（镇）、村，制定安全巡视原则，巡视车从县政府出发，巡视一圈并在途经乡村放下巡视员，车不停留继续巡视第二圈并在途中接回巡视员。然后根据分组原则，计算得出各组巡视时间。 对于问题四：要尽快完成巡视，就得要求各组完成巡视的时间尽可能相等，因为总的完成巡视的时间按最长巡视时间计算。显然在分组不变的情况下，无论怎么改变，对每组的最佳巡视路线是没有影响的，但可能会影响各组间的均衡，因此此问题实际上是讨论对分组的影响，即不破坏原来分组均衡性的条件下，的最大变化范围。讨论不影响分组均衡时，定量的得出其他变量所允许的最大变化范围。最后根据得出的结论对分三组的实例进行讨论并分析结果。 4数据的分析与处理因为最小生成树中能包含图中所有的顶点，而且最小树的边权是相邻两顶点间的距离，它描述了顶点之间的相近程度，故可以采用最小生成树进行分组。本模型的主要思想是：首先采用算法得到图的最小生成树，然后基于最小生成树生成一个可行的巡视路线，求得路线的最优总路程为。利用下述（1956年）算法可以在赋权图求出最优树。（1）选取边，使得最小；（2）设已经选取，则在中选取边使得：（）不含圈；（）尽可能小；（3）当第2步无法实施时停止。 根据算法进行编程求解（具体程序见附录1），于是我们得到图的最小生成树如图1。图1 5问题一的解答5.1模型一的准备现要分三组巡视，则需要把图分成三个子图，在每个子图中寻找最佳回路。现对已得到的最小生成树进行分解，以获得三个子图并使得分解结果尽量均衡。由于在最小生成树上，边权接近可以近似认为均衡即各子图包含的顶点数应接近。因此，各个子图的顶点数应尽量接近17个，且遵循以下分解原则。最小生成树分解原则：(i)分解点为O点或尽可能地接近O点；（ii）分解所得到的三个子图的顶点数尽可能地接近17个；（iii）尽量是分解所得到的子图是连通图；（iv）尽量使子图与点O的最短路上的点在该子图内，且尽量使各子图的点在子图内部形成环路。依据以上分解原则得到的分解结果如图2。 图2然后，采用哈密顿回路法求解每个子图内的最佳巡视路线。寻找最佳巡视路线实际上就是在赋权图中寻找最优的哈密顿圈，包含图的每个顶点的圈陈为哈密顿圈。于是问题就可以转化为：现已知三个子图内乡、村与乡、村之间的距离，从县政府O出发，经过子图内的所有乡、村，最后又回到点O。5.2模型一的建立5.2.1确定目标函数 由题中所给出的问题条件，分析出这是3个售货员寻求最佳旅行回路的问题。把县、乡、村所在地堪称借点，根据路线图可以构造一个赋权网络图,其中. 根据图论中的结论，最佳售货员回路问题可转化为最佳汉密尔顿回路的问题。在图的基础上构建三个子图，于是在中寻求最佳回路的问题即在中寻找最佳回路的问题，于是决策变量定义为:其线性（整数）规划模型目标函数为：。5.2.2确定约束条件目标函数给出了哈密顿圈的总长度，并使其最小。约束式保证只能到达每个城市一次，约束式保证只能离开一个城市一次，约束式( 为自定义变量)是表述问题的关键，它确保：（1）由解得到的任何圈一定包含城市1（即县镇府点O）；（2）包含全部城市的圈是可行的。于是，约束条件概括为：5.3综上所述，可得问题一的模型目标函数：约束条件：5.4问题一的求解与结果分析按照上述思想写出相应的Lingo程序（程序见附录2）求解得到三组巡视路线图见表2： 5问题二的解答5.1模型二的准备此问添加了巡视组在各乡（镇）停留的时间小时，在各村停留的时间小时以及汽车的行驶速度公里小时的条件后，要求在24小时内完成巡视的最少分组数以及相应的最佳巡视路线。此时需访问的乡（镇）共有17个，村共有35个，于是可以计算出巡视人员在乡（镇）及村停留的总时间为小时。此外，从问题一的结果中可知，巡视的总路程至少为500公里，则汽车行驶所需的时间和将超过14小时。由此可知，各组巡视所需的总时间之和超过83小时，要想在24小时内完成巡视则应满足： (i为分的组数)。得i最小为4，故至少要分4组。 现在尝试将顶点分成4组。分组的原则应建立在最小生成树的分解原则之上，则分组应遵循以下原则：(i)分解点为O点或尽可能地接近O点；（ii）分解所得的4个子图的顶点数尽可能地接近14个；（iii）尽量是分解所得的子图是连通图；（iv）尽量使子图与点O的最短路上的点在该子图内，且尽量使各子图的点在子图内部形成环路；（v）尽量使各组的巡视时间相接近。依据以上分解原则得到的分解结果如图4。采用上述原则将图分为4个子图，并运用哈密顿回路法找出各个组的最佳巡视路线。然后，计算出各组最佳巡视路线的总长度及汽车行驶所需时间，同时算出各组的停留时间,从而得到各组完成巡视的最佳时间。5.2模型二的建立5.2.1确定目标函数 由题中所给出的问题条件，分析出这是4个售货员寻求最佳旅行回路的问题。把县、乡、村所在地看作节点，根据路线图可以构造一个赋权网络图,其中 根据图论中的结论，最佳售货员回路问题可转化为最佳汉密尔顿回路的问题。在图的基础上构建4个子图，于是在中寻求最佳回路的问题即在中寻找最佳回路的问题，于是决策变量定义为:;其线性（整数）规划模型目标函数为：5.2.2确定约束条件目标函数给出了哈密顿圈的总时间长度，并使其最小。约束式保证只能到达每个城市一次，约束式保证只能离开一个城市一次，约束式( 为自定义变量)是表述问题的关键，它确保：（1）由解得到的任何圈一定包含城市1（即县镇府点O）；（2）包含全部城市的圈是可行的。于是，约束条件概括为：5.3综上所述，得问题二的模型目标函数：约束条件：5.4问题二的求解与结果分析 6问题三的解答6.1模型三的建立此问题就是要求如果有足够多的巡视人员，怎样确定最佳路线使完成巡视的时间最短。实际上，完成巡视的时间受到巡视最远乡（镇）、村路途时间和在乡（镇）、村停留时间的制约，由算法可得到各点到o点最短距离的完全生成图.由图上可求得距离O点最远的（乡镇）、村节点，分别为H点和14节点。考虑在乡村停留时间，TimeH=77.5*2/35+2=6.43（h）Time15=69.6*2/35+1=4.98(h)所以在所有节点中，巡视H镇所花费时间最大，由此可知，即使巡视人员再多，分组再细，完成巡视至少需要6.43小时。基于此，此问就可以转化为求在6.43小时内完成巡视的最少分组数和最佳巡视路线，为达到以上目标，我们制定了以下分组巡视原则：1、对图中偏西且距县政府较远的乡（镇）、村：（1）在6.4小时内，每组巡视人员尽可能走足够多的乡（镇）、村。 （2）在巡视时，尽量按出发点到该次巡视终点最短路径的路线巡视，但在不超过6.4小时的原则下，为了能够途经更多的点，我们可以不走最短路线。（3）巡视车从县政府出发，途中每到达一个乡（镇）、村，部分巡视人员下车巡视，车不停留（忽略不计巡视人员上、下车的时间）继续开往下个站点，直到到达最远点，车停下等待；然后按原路返回，依次到达每点接回巡视人员，直至出发点。2、由于第一种分组原则下，在最远点必须要花1或者2个小时的停留时间，针对这一浪费时间的缺点，对图中偏东且距县政府较近的乡、村，我们改进一种按圈巡视的方法，原则如下：（1）每组巡视人员巡视路线构成一个圈，且巡视两圈。（2）第一圈巡视时，途中每到达一个乡（镇）、村，部分巡视人员下车巡视，车不停留（忽略不计巡视人员上、下车的时间）继续开往下个站点，直至出发点，仍不停留继续第二圈巡视，到达每点依次接回巡视人员，直至回到出发点，结束。（3）在遵循不超过6.4小时原则下，按圈巡视时，圈总路线不能过长，不超过112公里；总路线也不能过短，避免车停留等待而浪费时间。6.2模型三的求解依据以上分组原则，我们在6.4小时内完成巡视，总共分成了7组，前5组遵循的第一种分组原则，后2组依据的第二种按圈分组原则。于是得到各组的巡视路线和停留点时间如下表:组号巡视路线时间16.4325.8736.1546.3856.3765.3875.48由上表可以看出各个组的巡视时间均小于6.43小时，符合题意，此外，计算得到该分组的时间均衡度公式为： 此时，计算得到均衡度：。在此基础上，我们可以得到有时间约束的最佳巡视路线如图4。 7问题四的解答7.1模型四的建立 巡视组数已定，要求尽快完成巡视，讨论T,t,和V的改变对最佳巡视路线的影响。要求尽快完成巡视，就的要求每组完成巡视时间尽量均衡，因为总的完成巡视时间按最长的完成巡视时间计算。现在讨论在均衡度允许的范围内已分成n组后，改变T,t,和V对最佳巡视路线的影响。显然在分许不变的情况下，无论T,t,和V如何改变，对每组内的最佳巡视路线是没有影响的，但可能会影响个组间的均衡性。因此该问题实际上讨论T,t,和V对于分组的影响，即在不破坏原来分组均衡的条件下，T,t,和V允许的最大变化范围。在分组为n的情况下，设：表示第i组的最佳推销员贿赂路线总长度；：表示第i组所要停留的乡镇数目；：表示第i组所要停留的村的数目；其中：。显然，当时，即每组的乡镇树、村数、最佳选会的长度均相等，因而分组绝对均衡时，T,t,和V的最大允许变化范围的讨论：对于任意一个组i，其完成巡视的时间设均衡分组的最大允许时间均衡度为，即则有：记，则表示均衡返租所允许的最大时间误差，则 （1）由（1）式我们得到 （2）由式（2）可得1.当时，要保持云均衡分组不变,T必须满足的条件为： （3）2当时，要保持原均衡分组不变，t必须满足的条件为： （4）3当时，由（2）式得（1） 当时，有 （5）（2） 当时，有 （6）由（3）-(6)式，当T,t,和V三个变量中任意两个变量无论如何如何变化，都可计算出为保持均衡性分组不变，三个变量所允许的最大变化范围。（2） 分三组的实例讨论先对分三组的情况进行分步讨论，对问题一中所得的三个分组，若考虑停留时间和行驶时间且取小时，小时，公里/小时，结果如表5：（3） 对实例结果的分析上述实例的均衡分组有一个特点，各组的停留时间相等，即取，小时，公里/小时，在表5的分组中 （7）定义4各组的停留时间相等的均衡分组成为停留时间相等的均衡分组，由（7）式得 （8）先讨论对停留时间相等的均衡分组，T,t,V的变化规律，对停留时间相等的均衡分组，分组的实际时间误差： （9）其中，i为使最大组的标号；j为最小的足的标号。 当不变时，即时，因，由（6）式知道，要保持平衡分组，的下界应为：(i,j的含义不同)(1)取时，由（9）式得（1） 取时，由（9）式得