建模案例:最佳灾情巡视路线

建模案例：最佳灾情巡视路线

这里介绍1998年全国大学生数学模型竞赛B 题中的两个问题.

一、问 题

今年夏天某县遭受水灾. 为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视. 巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线.

1． 若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的路线.

2． 假定巡视人员在各乡（镇）停留时间T =2h，在各村停留时间t =1h，汽车行驶速度V =35km/h.要在24h 内完成巡视，至少应分几组；给出这种分组下最佳的巡视路线.

乡镇、村的公路网示意图见图

1.

图1

二、 假 设

1．汽车在路上的速度总是一定，不会出现抛锚等现象；

2．巡视当中，在每个乡镇、村的停留时间一定，不会出现特殊情况而延误时间；

3．每个小组的汽车行驶速度完全一样；

4．分组后，各小组只能走自己区内的路，不能走其他小组的路（除公共路外）.

三、模 型 的 建 立 与 求 解

将公路网图中，每个乡（镇）或村看作图中的一个节点，各乡（镇）、村之间的公路看作图中对应节点间的边，各条公路的长度（或行驶时间）看作对应边

上的权，所给公路网就转化为加权网络图，问题就转化为在给定的加权网络图中寻找从给定点O 出发，行遍所有顶点至少一次再回到O 点，使得总权（路程或时间）最小，此即最佳推销员回路问题.

在加权图G 中求最佳推销员回路问题是NP —完全问题，我们采用一种近似算法求出该问题的一个近似最优解，来代替最优解，算法如下：

算法一 求加权图G （V ，E ）的最佳推销员回路的近似算法：

1． 用图论软件包求出G 中任意两个顶点间的最短路，构造出完备图

G '(V , E ') ，∀(x , y )∈E '， ω(x , y )=mind G (x , y )；

2． 输入图G '的一个初始H 圈；

3． 用对角线完全算法产生一个初始H 圈；

4． 随机搜索出G '中若干个H 圈，例如2000个；

5． 对第2、3、4步所得的每个H 圈，用二边逐次修正法进行优化，得到近似最佳H 圈；

6． 在第5步求出的所有H 圈中，找出权最小的一个，此即要找的最佳H 圈的近似解.

由于二边逐次修正法的结果与初始圈有关，故本算法第2、3、4步分别用三种方法产生初始圈，以保证能得到较优的计算结果.

问题一 若分为3组巡视，设计总路程最短且各组尽可能均衡的巡视路线.

此问题是多个推销员的最佳推销员回路问题. 即在加权图G 中求顶点集V 的划分V 1, V 2, , V n ，将G 分成n 个生成子图G [V 1], G [V 2],..., G [V n ]，使得

（1）顶点O ∈V i , i =1，2，3, …, n ；

n （2） V i i =1=V (G ) ；

≤α，其中C i 为V i 的导出子图G [V i ]中的最佳推销（3）max ω(C i )-ω(C j )i , j

max ωC i i

员回路，ω(C i )为C i 的权，i ，j =1，2，3, …, n ；

（4）∑ω(C i )取最小.

i =1n

定义 称α0=max ω(C i )-ω(C j )i , j

max ωC i i 为该分组的实际均衡度. α为最大容

许均衡度.

显然0≤α0≤1，α0越小，说明分组的均衡性越好. 取定一个α后，α0与α满足条件（3）的分组是一个均衡分组. 条件（4）表示总巡视路线最短.

此问题包含两方面：第一，对顶点分组；第二，在每组中求最佳推销员回路，即为单个推销员的最佳推销员问题.

由于单个推销员的最佳推销员回路问题不存在多项式时间内的精确算法，故多个推销员的问题也不存在多项式时间内的精确算法. 而图中节点数较多，为53个，我们只能去寻求一种较合理的划分准则，对图１进行粗步划分后，求出各部

分近似最佳推销员回路的权，再进一步调整，使得各部分满足均衡性条件（3）.

从O 点出发去其他点，要使路程较小应尽量走O 点到该点的最短路. 故用图论软件包求出O 点到其余顶点的最短路，这些最短路构成一棵以O 为树根的树，将从O 点出发的树枝称为干枝，见图2，从图中可以看出，从O 点出发到其它点共有6条干枝，他们的名称分别为①，②，③，④，⑤，⑥.

根据实际工作的经验及上述分析，在分组时应遵从以下准则：

准则一：尽量使同一干枝及其分枝上的点分在同一组；

准则二：应将相邻的干枝上的点分在同一组；

准则三：尽量将长的干枝与短的干枝分在同一组.

由上述分组准则，我们找到两种分组形式如下：

分组一：（⑥，①），（②，③），（⑤，④）；

分组二：（①，②），（③，④），（⑤，⑥）．

显然分组一的方法极不均衡，故考虑分组二.

对分组二中每组顶点的生成子图，用算法一求出近似最优解及相应的巡视路线. 使用算法一时，在每个子图所构造的完备图中，取一个尽量包含图2中树上的边的H 圈作为其第2步输入的初始圈.

分组二的近似解见表1.

因为该分组的均衡度α0=ω(C 1)-ω(C 2)241.9-125.5==54.2% max ωC i 241.9i =1,2,3

所以此分法的均衡性很差.

为改善均衡性，将第Ⅱ组中的顶点C ，2，3，D ，4分给第Ⅲ组（顶点2为这两组的公共点），重新分组后的近似最优解见表2.

31216.4-191.1==11.69% 因该分组的均衡度α0=max ωC i 216.4i =1,2,3

所以这种分法的均衡性较好.

问题二 当巡视人员在各乡（镇）、村的停留时间一定，汽车的行驶速度一定，要在24h 内完成巡视，至少要分几组及最佳的巡视路线.

由于T =2h，t =1h，V =35km/h，需访问的乡镇共有17个，村共有35个. 计算出在乡（镇）及村的总停留时间为17⨯2h+35h=69h，要在24h 内完成巡回，若

69

由于该网络的乡（镇）、村分布较为均匀，故有可能找出停留时间尽量均衡

69的分组，当分4组时各组停留时间大约为h =17.25h ，则每组分配在路途上的4

时间大约为24h-17.25h=6.75h.而前面讨论过，分三组时有个总路程599.8km 的巡视路线，分4组时的总路程不会比599.8km 大太多，不妨以599.8km 来计算.

599.817h =17h ，若平均分配给4个组，每个组约需路上时间约为h=4.25h354

〈6.75h ，故分成4组是可能办到的.

现在尝试将顶点分为4组. 分组的原则：除遵从前面准则一、二、三外，还应遵从以下准则：

准则四：尽量使各组的停留时间相等.

用上述原则在图2上将图分为4组，同时计算各组的停留时间, 然后用算法一算出各组的近似最佳推销员巡回，得出路线长度及行走时间，从而得出完成巡视的近似最佳时间. 用算法一计算时，初始圈的输入与分3组时同样处理.

这4组的近似最优解见表3.

加框的表示此点只经过不停留.

22. 74-21. 69=4.62% 该分组实际均衡度α0=22. 74

可以看出，表3分组的均衡度很好，且完全满足24h 完成巡视的要求.