灾情巡视路线选择

1、灾情巡视路线选择摘要 本文就灾情巡视问题进行分析，并建立相应的数学模型，根据路程长短以及村镇的停留时间合理地规划路线，并根据要求调整优化。问题一中要求设计总路程最短且各组尽可能均衡。先找出最短生成树，然后设计路线，并人工优化路线。问题二要求分组最少的前提下设计最佳的巡视路线。将总路程、乡（镇）、村的数目大致均分，能最大程度的节约时间，同时合理优化。问题三的人员足够多，先计算到达该县最远的乡（镇）或村所需的时间，此时间为完成巡视的最短时间。其余村镇可以运用统筹的方式遍历并最后优化。问题四要求尽快完成巡视，先用函数式表示这个最小的时间，然后分别讨论T、t、V的改变对最小时间以及最佳路线的影响。同时

2、根据实际分组等具体因素的影响确定均衡度的合理范围，再根据均衡度对各小组的路线进行优化。关键字：普林算法 最小生成树 均衡度 统筹 一、 问题的描述与分析1.1问题的描述 大水无情人有情，为考察灾情，县领导决定派人及早将各乡（镇），村巡视一遍，巡视路线为从县政府所在地出发，走遍各乡（镇），村，又回到县政府所在地的路线。1. 若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。 2. 假定巡视人员在各乡（镇）停留时间T=2 小时，在各村停留时间 t=1 小时，汽车行驶速度V=35公里/ 小时。要在 24小时内完成巡视，至少应分几组；给出这种分组下你认为最佳的巡视路线。3. 在上述关于T

3、 , t 和V 的假定下，如果巡视人员足够多，完成巡视的最短时间是多少；给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路线。 4. 若巡视组数已定（比如三组），要求尽快完成巡视，讨论 T，t 和V 改变对最佳巡视路线的影响。（图见附录）1.2问题的分析对于问题一，我们应该要抓住设计总路程最短且各组尽可能均衡这一要点，即总路程不一定是最短的，不一定是最均衡的，但是二者要统筹兼顾。所以路程的设计很重要。由题意可以看出，在设计路线时，三组人的路线尽量不重复，尽量无交叉。对于问题二，我们不再要求路线均衡，但是值得注意的是分组应尽可能的少，在完成任务，分组最少的前提下设计最佳的巡视路线。可以从给出

4、的题图看出该县的各乡（镇），村分布较为均与，要想用尽可能少的组在24小时内完成任务，其实各组的路程还是大致均分的，才有可能最大程度的节约时间，从而完成最佳路线的设计。由此看出问题一得到的总路程对于分组的最小值很有参考价值。对于问题三，因为要尽快的完成巡视，并且巡视的人员足够多。所以我们可以考虑到达该县最远的乡（镇）或村所需的时间，此时间为完成巡视的最短时间。其余村镇可以运用统筹的方式遍历，而且时间差均不大，基本保证人尽其用。对于问题四，题目要求要尽快完成巡视，并讨论T、t、V的改变对最佳巡视路线的影响，这些的前提都是巡视组数一定。由于都不是定值，我们可以用函数表达式来进行讨论。首先确定最短的巡

5、视时间，然后根据T、t、V的变化讨论对最佳路线的影响。然后再根据具体的分组及在合理的不确定度的范围内，再对各个小组的路线进行优化，以求最佳的巡视路线。1.3问题的假设(1) 巡视过程中无意外情况发生； (2)非本县村不限制通过；(3）非本县村不作停留；(4）汽车一旦行驶，始终保持匀速V；(5) 各乡（镇），村只考察一次，多次经过时只计算一次停留的时间；二、 模型的假设1.均衡度设为，=最大值-最小值最大值，其中最大值和最小值均为一组内的数据；2.n表示分的小组数； 3.Ci表示各小组的巡视时间；4. xi表示第i个小组所要巡视巡视的乡镇数；5.yi表示第i个小组所要巡视的村庄数；6.Si表示第

6、i个小组巡视路线的长度。三、 模型的建立问题一3.1.1问题分析 对于问题一，因为路程尽量短，所以我们可以通过普林算法画出最小生成树，依据最小生成树的树干进行划分，粗略的划分为三组。这三组很有可能并不是最均衡合理的，但是距离一定是较短的，所以还要计算均衡度并进行优化。在最小生成树中从O点出发的树枝称为干枝，总共有6个干枝，我们考虑把6个干枝两两组合分为3组，构成3个回路。并计算其均衡度，根据其均衡度进行相应的人工优化，最终得出均衡度合适且总距离最短的3个巡视路线。3.1.2 问题解答 根据普林算法，我们可以得到最小生成树如下：根据上述的问题分析，先把6个干枝编号-，把分为一组，分为一组，分为一

7、组。分组如下：计算其总距离与均衡度，计算结果如下： 均衡度=241.9-125.5241.9=48.12% 由上面的计算结果可以看出，其总距离较短但是均衡度较大，所以这种划分不合理要进行优化。所以要将现有的路线进行手工改进，稍稍改变其路线，调整均衡度，改进后的结果如下：均衡度=216.4-191.1216.4=11.69%12%由计算可以看出该方案的巡视总路程相比较原来的巡视总路程并未增加太多，但是均衡度明显下降到11.69%，我们认为均衡度在12%内的均为合理的均衡度。所以我们现在认为改进后的路线不仅总路程较小，而且均衡，即为最佳的巡视路线。问题二3.2.1问题分析对于问题二，我们首先可以用

8、问题一得到的巡视总路程作为问题二的巡视总路程进行估算，然后得到最小的分组数为4。还有，我们从图上可以看出，该县的乡（镇），村分布较为均匀，我们可以将乡（镇），村较为合理的分为4组，并进行时间及路程的计算，确保在24小时内完成巡视。3.2.2 问题解答 我们将599.8近似的看为600参与计算。我们从图上得到共有17个乡（镇），35个村，要遍历这些地方至少要停留172+35=69(小时)设分为n组600v+69n24解得n3.59通过计算，我们可以得到我们至少要将组数定为4。根据我们得到的最小生成树图和该县地图我们，将4条巡视路线定为如下：图上每种颜色代表一条巡视路线。由上面的路线图，可以计算这

9、四条巡视路线各自所需的时间。小组编号路线路线长度（km）所用时间（h）O-2-5-6-7-E-11-G-12-H-F-10-F-9-E-8-E-7-6-5-2-O195.822.59O-M-25-21-K-18-I-15-14-13-J-19-L-20-25-M-O162.422.64O-P-26-N-23-22-17-16-17-22-23-24-27-28-Q-29-R-O156.921.48O-C-3-D-4-D-3-C-B-A-34-35-32-30-32-31-33-A-1-O186.622.33我们可以看出4条路线的巡视都在24小时内完成，而且都控制在23小时内，路线划分合理。问题

10、三3.3.1问题分析对于问题三，我们可以从题目得到，巡视的人员足够多，但是务必要求在最短的时间内完成巡视。要求最短的时间，就应该求出离县委政府O最远的乡（镇）或村所需的时间，且在途经的乡（镇）或村不作停留，这样才能求出最短的巡视时间。我们要得到最佳的巡视路线，尽管人员足够多，我们还是应当避免不必要的人力物力的浪费，每组完成巡视的时间应当尽量差不多。根据最小生成树及该县地图还有求出的最短的巡视时间，我们将整个巡视路线进行统筹规划，合理分组。3.3.2 问题解答我们通过计算可得离县委政府O最远的乡（镇）为H，到H所需的时间至少是6.43小时。并通过最小生成树及该县的地图进行合理的分组。显然，其余组

11、的时间要小于第一组O-H-O的时间6.43小时，根据统筹学，我们进行了合理的划分和计算。详细如下表：小组名称路线所用时间（h）停留地点时间差（h）第一组O-H-O6.43H0第二组O-3-D-4-D-3-2-O5.993、4、D0.44第三组O-2-5-6-M-O6.342、3、5、M0.09第四组O-2-5-6-7-E-9-F-12-F-9-E-7-6-5-2-O5.859、120.58第五组O-2-5-6-7-E-9-F-10-F-9-E-7-6-5-2-O5.767、100.67第六组O-2-5-6-E-11-G-11-E-6-5-2-O5.58G0.85第七组O-2-5-6-7-E-9

12、-F-9-E-7-6-5-3-O6.15F、E0.28第八组O-2-5-6-7-E-11-E-8-E-8-E-11-E-7-6-5-2-O5.658、110.78第九组O-2-5-6-L-20-L-6-5-2-O5.54L、200.89第十组O-2-5-6-L-19-J-13-14-13-J-19-L-6-5-2-O6.1513、140.28第十一组O-2-5-6-L-19-J-19-L-6-5-2-O6.1019、J0.33第十二组O-M-25-21-K-17-16-17-K-21-25-M-O5.4516、170.98第十三组O-M-25-21-K-18-I-15-I-18-K-21-25

13、-M-O5.9915、180.44第十四组O-M-25-21-K-18-I-18-K-21-25-M-O5.49I0.94第十五组O-M-25-21-K-21-25-M-O5.4921、K0.94第十六组O-P-26-N-23-22-23-N-26-27-26-P-O6.2522、23、270.18第十七组O-M-25-N-26-P-O6.0525、26、N0.38第十八组O-P-26-N-24-27-28-Q-29-R-O6.0624、28、290.37第十九组O-P-28-Q-29-R-O5.67P、Q0.76第二十组O-R-29-Q-30-32-31-R-O6.17R、30、320.26

14、第二十一组O-R-31-33-A-34-35-34-A-1-O5.6431、33、350.79第二十二组O-1-A-B-1-O6.261、A、B0.17第二十三组O-1-A-34-A-1-O-C-O5.2534、C1.18问题四3.4.1问题分析巡视组数一定，要求尽快完成巡视，讨论T、t、V的改变对最佳巡视路线的影响。本问要求尽快完成巡视，也就是要求各组巡视时间的最大值尽可能小。用数学表达式表示出这个最小的时间，然后分别讨论T、t、V的改变对最小时间以及最佳路线的影响。同时根据实际的人员及环境等具体因素的影响确定均衡度的合理范围，再根据确定的均衡度对各小组的路线进行优化。3.4.2 问题解答巡

15、视的最小时间的数学表达式为minmaxCi=minmax1inT*xi+t*yi+SiV这里，Ci表示各小组的巡视时间，n表示分的小组数，xi表示第i个小组所要巡视巡视的乡镇数，yi表示第i个小组所要巡视的村庄数，Si表示第i个小组巡视路线的长度。 Ci= T*xi+t*yi+SiV 在上述表达式中，T和t的作用完全相仿，所以在讨论时，T和t一起进行讨论。1. 若T或t增加而V保持不变。为了使Ci尽可能小，则必须使T*xi+t*yi的最大值尽可能小。然而，当T和t确定之后，i(T*xi+t*yi)的值是确定的，因为总共有17个乡（镇）和35个村。这时，在乡、村停留的时间对总的巡视时间的影响变大

16、。这就要求，每组停留的乡村数要基本一致。当然，还要计算均衡度并根据设定的均衡度以及实际情况对各组进行相应的调整优化。2. 若V增大而T和t保持不变。为了使Ci尽可能小，则必须使SiV的最大值尽可能小。此时，巡视路线对总的巡视时间的影响变大。由于巡视路程的不固定性，我们在使巡视路线相对均衡的前提下，还要考虑T*xi+t*yi的影响，并根据设定的均衡度以及实际情况对巡视路线进行调整优化。四、模型的评价 1.该问题属于行遍性问题中的流动推销员问题，也就是TSP问题。是已经被论证的NPC问题，至今仍没有简单有效的算法，在图中寻求最佳回路问题可转化为在一个完备加权图中寻求最佳哈密尔顿圈的问题，运算量很大，而且还不能保证得到