灾情巡视线路最优规划模型
摘要
本文是把最佳巡视路线问题转化为图论【1】中求旅行商问题（TSP）,用近似的算法来寻求近似的最优解。我们采用了分区求解的方法, 利用Kruskal算法得到基于整个网络的最小生成树，并提出了基于最小生成树的分区原则、边界调整原则和均衡度函数,保证了模型的合理性和解的有效性，从而得出特定情况下的最优巡视路线。
对于问题一，分三组巡视灾区，要求总路程最短且尽可能均衡。我们先定出几个分区原则，然后再最小生成树的基础上求解出最短回路，再根据均衡度函数进行微调。得出总路程较短且各组尽可能均衡的路线，各组的巡视路线路程分别为
关键字：最小生成树多旅行商问题（TSP） Kruskal算法哈密尔顿回路
一、问题的重述
下图(见附录1)为某县的乡(镇)、村公路网示意图,公路边的数字为该路段的公里数。
今年夏天该县遭受水灾,为考察灾情,组织自救,县领导决定,带领有关部门负责人到全县各乡(镇)、村巡视,巡视路线指从县政府所在地出发,走遍各乡(镇)、村,又回到县政府所在地的路线。
1、若分三组巡视,试设计总路程最短且尽可能均衡的巡视路线。
2、假定巡视人员在各乡(镇)停留时间T=2小时,在各村停留时间t=1小时,
汽车行驶速度为V=35公里/小时。要在24小时内完成巡视,至少应分
几组；给出这种分组下你认为最佳的巡视路线。
3、在上述关于T、t、V的假定下,如果巡视人员足够多,完成巡视的最短
时间是多少；给出在这种最短时间完成巡视的要求下,你认为最佳的巡
视路线。
4、若巡视组数已给定(比如三组),要求尽快完成巡逻,讨论T、t和V改变
对最佳巡视路线的影响。
二、模型的假设及符号说明
假设：
1、公路不考虑等级差别,即将所有路面状况视为基本相同,车辆在所
有公路上速度保持恒定不变。
2、交通情况不受灾情影响,即车辆在所有公路上都可以顺利通过。
3、各巡视小组统一行动,不再另外分成小组进行巡视。
4、对于某些至少需要经过两次的乡(镇)、村,认为仅在第一次经过这
些地点时停留,此后再经过就不再停留。
5、对于某两个区域的公共乡(镇)、村,只要任一个巡视组停留过,其它
组经过时就不再作停留。
符号说明：
三、模型的建立与求解
3.1模型的分析
本题是一类图上的点的行遍性问题,也就是要用若干条闭链覆盖图上所有的顶点,使某些指标达到最优。本题所要求的分组巡视的最佳路线,与多旅行商问题和货郎担问题类似,也就是求m 条经过同一点并覆盖所有其它顶点又使边权之和达到最小的闭链。
对于问题一，我们为了在求得最佳路线的同时，保证三组路线尽量均衡，引入了距离均衡度B （表达式见注2），并认为当B ≤0.1时,结果是均衡的。 3.2模型的建立与求解 3.3.1问题一
第一问要求设计分三组巡视总路程最短且尽可能均衡的巡视路线。设三组的巡视路线长度从小到大为1p 、2p 、3p ,则我们要达到的目标为
321min p p p P ++= (1)
13'min p p P -= (2)
但是这两个目标函数是互相矛盾的,即它们不可能同时达到最小。因此在求解时,要折中考虑。
具体求解步骤如下:
step1 采用一定的分区原则[注1]将地图分成三个区。
step2 按区寻找最小生成树,并在其基础上求解最短回路。
step3 求出每条回路的长度,代入距离均衡度函数[注2],如果满足条件则终止；否则,按调整原则[注3]将区域进行调整,返回step2。 [注1] 分组原则。
首先,以O 点为起点,采用Kruskal 算法,得到一个基于整个公路网的最小生成树,将其分解,以得到三个子图,使得分解结果尽量均衡。由于在最小生成树上,边权(相邻两顶点之间距离)接近,可略认为均衡是指各子图包含的顶点数接近。本题中共有53个乡(镇)、村，看作53个点，即在本题中应尽量保证所分三个区的节点数接近17个。综上有以下分区原则
1) 分解点为O 点,或尽可能接近O 点。
2) 分解所得的三个子图所包含的顶点数尽可能接近17个。 3) 尽量使每一个子图为连通图。
4)
尽量使每一个子图中与点O 的最短路上的点在该子图内。尽量使各子图的点在子图内部形成环路。
图1 整个图的最小生成树
[注2]距离均衡度函数:
n p p p B n
i i i
i ÷??
? ??-=
∑=1min max ( i=1,2,3…n) 当B ≤0.1时,认为结果是均衡的。
[注3]调整原则：
在本题中我们采用边界调整法,其主要目标是在边界对各区域进行调整,以提高各组的均衡程度。具体调整步骤为:
第一步为增强相邻区域的可调整性,规定首先对相邻边界点较多的两区域进行调整。
第二步优先对P最小的区域Ⅰ和P最大的区域Ⅲ之间进行调整,若这两个区域之间的相邻点相对较少,则通过第三个区域Ⅱ进行Ⅰ、Ⅱ和Ⅱ、Ⅲ之间的调整。
由上述分区原则和求解步骤得到的分区图和路径如下:
图2 分区方案一
表
分区
方案一路线及其长度表
方案一 距离均衡度：
18.035.5828
.1741.210min max 1≈÷-=÷??
?
??-=
∑=n p p p B n
i i i i
结果分析：采用上述方案得到的路线总长度较小,但是均衡度为B=0.18不满足要求,应进行调整。
在调整过程中,我们发现边界上的点存在三个敏感区域,它们是N 点23点24点、13点14点和C 点。这三个敏感区域的归属不同,造成了分区的不同和结果的不同。原因是这三个区域离O 点较远,对路程总长度的影响大,同时它们的划分对子区域的边界处能否形成回路(见分区原则iv)有很大影响。 将Ⅲ区的13点14点调到Ⅱ区去,得到新的分区和路径如下：
图3 分区方案二
方案二 距离均衡度：
03.039.5996
.1977.203min max 1≈÷-=÷??
?
??-=
∑=n p p p B n
i i i i 结果分析：均衡度B=0.03满足题目要求，且总长度比较优。 则分三组巡视时，最优路线如表2，总路程为599.9公里。 3.3.2问题二
由于T=2小时,t=1小时,V=35公里/小时,需要访问的乡镇18个,村35个,则在乡(镇)、村总的停留时间为18×2+35×1=71小时,需在24小时内完成巡视,若仍分三组的话,平均每组只有1小时的行路时间,只能走35公里,无法在规定时间内走完所有的乡(镇)、村。因此,考虑行路时间,至少要分四组。
与问题一类似,设这四组的巡视时间从小到大为1t 、2t 、 3t 、4t ,我们要实现的是下面两个目标函数
4321min t t t t T +++= (3) 14'min t t T -= (4)
244≤t （5）
在具体求解时,仍采用第一问中的分区域--求区域内的最小生成树--根据最小生成树找出回路--计算均衡度--调整的方法。下面只对分区原则和均衡度函数作以下补充：
(1)将原地图分成四个区。
(2)分区时要尽量使各组的停留时间相等。可先将相对集中的乡(镇)
划为一个区,兼顾乡(镇)个数的均匀,再通过调整村的划分来实现
时间上的均衡。
(3) 均衡性的衡量采用时间均衡度函数：
n t t
t b
n
i
i
i i
÷
-
=
∑=)
(min
max
1
b≤0.1时认为是均衡的
按照以上步骤,采用计算机搜索的方法,得到一组较优解,括号中的点表示只经过不停留。
图4 四个巡视组的区域划分
表2 四个巡视组分区路线及时间表
时间均衡度函数：
052.04
37.8708
.2121.22)(min max 1=÷-=
÷-=
∑=n
t t t b n
i i i
i
结果分析：时间均衡度函数b=0.052符合要求。
则满足问题二条件的至少需要分4组，各组路线见表2. 3.3.3问题三
若有足够多的巡视人员，要求出完成巡视的最短时间，并给出在最短时间下的最佳巡视路线。这是求点集的最小覆盖问题,子集覆盖问题属于NP--完全类,无法在短时间内找到最优解。
可以求出巡视距o 点最远的乡(镇)所需的最短时间min T ，这样，其他各组的巡视时间都不应超过min T 。引入点权的概念，若为乡镇，点权为2；若为村，点权为1，即为在该点的停留时间。
ij d i 点到j 点的最短通路长
i w i 点的权
i e 从o 点到j 点巡视的最短时间
在最短时间的限制下，完成巡视的最优路线应满足如下条件：
（1） 每个组的巡视时间不能超过最短时间min T （2） 所有的点都应巡视到，不能漏点 （3） 所需巡视组数要尽量少
寻找最优路线的具体方法如下：
step1 利用Floyd 算法求得图中任意两点的最短通路长。可以得到o 点到各点巡视最短时间v d w e ij i i ÷*+=2，找到其中最大的时间即为min T 。
Step2 将未巡视过的点按oi d （o 点到i 点的最短通路长）的大小排序，选择距离o 点最远的i 点作为巡视点，给i 点加巡视过标记。在余下点中寻找j 点，看这一组能否巡视该点。j 点的寻找原则为:ij oj d d -最大。若
0m i n >----oj ij i oi d d w d T ，可以巡视j 点；否则不能巡视j 点。再按照同样的原则，看该组能否巡视其它点。若无可巡视点，计算该组的巡视时间，开始新一组的巡视路线搜索
Step3 第二步只是找到了每组巡视的停留点，再利用Dijsktra 算法，找到从O 点出发，经过这些停留点的最短路线。 通过以上算法我们找到的最优解是22组，如下表:
结果分析： 3.3.3问题四：
若巡视组数已定,则每组所用的时间为V s t c T x t i i i i ÷+*+*= xi 第i 组停留的乡(镇)
i c 第i 组停留的村 i s 第i 组的巡视路线长度
当T 、t 不变而V 增加时,i t 主要受V 影响,因此要求路线的均衡性比较好。这时需对xi 、i c 作调整,对路程较长的组尽量考虑停留较少的村。
当V 不变而T 、t 增大时, i t 主要受xi 、i c 影响,此时乡(镇)、村分布的均衡性就显得十分重要。特别是乡(镇),T 越大,对乡(镇)的均衡性要求就越高。各组的巡视路线的均衡度可以差一些,因为在T 、t 大到一定程度时, i s ÷V 可忽略。
四、结果分析与检验
五、模型评价与推广 六、参考文献
附录
附录1
某县的乡(镇)、村公路网示意图