最佳灾情巡视路线.ppt

1. 问题引入与分析
1) 98年全国大学生数学建模竞赛B题“最佳灾
今年(1998年)夏天某县遭受水灾. 为考察灾情、
组织自救，县领导决定，带领有关部门负责人到
全县各乡（镇）、村巡视. 巡视路线指从县政府
所在地出发，走遍各解.
算法一 求加权图的最佳旅行售货员回路近似算法:
1) 用图论软件包求出G中任意两个顶点间的最短路,
构造出完全图
2) 输入图 的一个初始H圈；
3) 用对角线完全算法（见[23]）产生一个初始圈;
4) 随机搜索出 中若干个H圈，例如2000个；
5) 对第2)，3)，4)步所得的每个H圈，用二边逐次
修正法进行优化，得到近似最优H圈；
6) 在第5)步求出的所有H圈中，找出权最小的一个,
此即要找的最优H圈的近似解.
因二边逐次修正法的结果与初始圈有关,故本算法
第2)，3)，4)步分别用三种方法产生初始圈，以保
证能得到较优的计算结果.
7
精选ppt
问题一 若分为三组巡视，设计总路程最短且各
组尽可能均衡的巡视路线.
此问题是多个售货员的最佳旅行售货员问题.
4)
8
精选ppt
此问题包含两方面：a)对顶点分组, b)在每组中
求(单个售货员)最佳旅行售货员回路.
因单个售货员的最佳旅行售货员回路问题不存
存在多项式时间内的精确算法.
故多
也不
9
精选ppt
而图中节点数较多，为53个，我们只能去寻求
一种较合理的划分准则，对图1进行粗步划分后,求
出各部分的近似最佳旅行售货员回路的权,再进一
进一步进行调整，使得各部分满足均衡性条件3).
从O点出发去其它点，要使路程较小应尽量走
O点到该点的最短路.
故用软件包求出O点到其余顶点的最短路.
这些最短路构成一棵O为树根的树.
将从O点出发的树枝称为干枝.
10
精选ppt
从O点出发到其它点共有6条干枝，它们的名称
分别为①，②，③，④，⑤，⑥.
在分组时应遵从准则：
准则1 尽量使同一干枝上及其分枝上的点分在同一组.
准则2 应将相邻的干枝上的点分在同一组；
准则3 尽量将长的干枝与短的干枝分在同一组.
由上述分组准则，我们找到两种分组形式如下：
分组1:（⑥，①），（②，③），（⑤，④）
分组2:（①，②），（③，④），（⑤，⑥）
分组1极不均衡,故考虑分组2.
11
精选ppt
分组2:(①,②),(③,④),(⑤,⑥)
对分组2中每组顶点的生成子图,用算法一求出近似最优解及相应的巡视路线.
在每个子图所构造的完全图中,取一个尽量包含上图中树上的边的H圈作为其第2)步输入的初始圈.
12
精选ppt
分组2的近似解
13
精选ppt
因为该分组的均衡度
.
所以此分法的均衡性很差.
为改善均衡性，将第Ⅱ组中的顶点C,2,3,D,4
分给第Ⅲ组（顶点2为这两组的公共点），重新分
分组后的近似最优解见表2.
14
精选ppt
15
精选ppt
因该分组的均衡度
所以这种分法的均衡性较好.
问题二 当巡视人员在各乡（镇）、村的停留
停留时间一定,汽车的行驶速度一定,要在24小时内
完成巡视,至少要分几组及最佳旅行的巡视路线.
16
精选ppt
由于T=2小时,t=1小时,V=35公里/小时,需访问
的乡镇共有17个，村共有35个. 计算出在乡(镇)及
村的总停留时间为17 2+35=69小时，要在24小时
内完成巡回，若不考虑行走时间，有: 69/i<24(i为
分的组数). 得i最小为4，故至少要分4组.
由于该网络的乡(镇)、村分布较为均匀,故有可
能找出停留时间尽量均衡的分组,当分4组时各组停
停留时间大约为69/4=，则每组分配在路
路途上的时间大约为24-=
论过,，
,不妨以
=17小时,若平
均分配给4个组,每个组约需17/4=<
小时,故分成4组是可能办到的.
17
精选ppt
：除遵从
前面准则1、2、3外，还应遵从以下准则：
准则4 尽量使各组的停留时间相等.
用上述原则在下图上将图分为4组，同时计算
各组的停留时间,然后用算法一算出各组的近似最
最佳旅行售货员巡回，得出路线长度及行走时间,
从而得出完成巡视的近似最佳时间. 用算法一计
计算时，初始圈的输入与分三组时同样处理.
这4组的近似最优解见表3.
18