1998年全国大学生数学建模竞赛题之欧阳理创编

1998年全国大学生数学建模竞

赛题目

时间：2021.03.05 创作：欧阳理 B题 灾情巡视路线

下图为某县的乡（镇）、村公路网示意图，公路边的数字为该路段的公里数。

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

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

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

(3) 在上述关于T , t和V的假定下，如果巡视人员足够多，完成巡视的最短时间是多少；给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路线。

欧阳阳理创编 2021.03.04

欧阳阳理创编 2021.03.04

(4) 若巡视组数已定(如三组），要求尽快完成巡视，讨论T，t和V改变对最佳巡视路线的影响。

灾情巡视路线模型

摘 要

本文将求最佳巡视路线间题转化为图论中求最佳推销员回路（哈米尔顿回路）的问题,并用近似算法去寻求近似最优解。对赋权图中的路径分组问题定义了均衡度用以衡量分组的均衡性。对问题1和问题2先定出几个分的准则进行初步分组,并用近似算法求每一组的近似最佳推销员回路,再根据均衡度进行微调,得到较优的均衡分组和每组的近似最佳推销员回路。对问题1，运用求任意两点间最短路的Floyd算法,得出总路程较短且各组尽可能均衡的路线,各组的巡视路程分别为216.4公里,191.1公里,192.3公里,总路程599.8公里。对问题2,证明了应至少分为4组,并求出了分为4组时各组的较优巡视路线,各组的巡视时间分别为22.74小时,22.59小时,21.69小时,22.54小时。对问题3,求出完成巡视的最短时间为6.43小时,并用较为合理的分组的准则,分成22个组 对问题4，研究了在不影响分组的均衡条件下, T,t,V的允许变化范围,并得出了这三个变量的关系式,并由此对分三个组的情况进行了具体讨论。

欧阳阳理创编 2021.03.04

欧阳阳理创编 2021.03.04

关键词：最佳推销员回路问题 哈米尔顿回路 赋权图 近似算法均衡度

一、问题重述

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

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

(2) 假定巡视人员在各乡（镇）停留时间T=2小时，在各

村停留时间t=1小时，汽车行驶速度V=35公里/小时。要在24小时内完成巡视，至少应分几组；给出这种分组下你认为最佳的巡视路线。

(3) 在上述关于T , t和V的假定下，如果巡视人员足够

多，完成巡视的最短时间是多少；给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路线。 (4) 若巡视组数已定(如三组），要求尽快完成巡视，讨

论T，t和V改变对最佳巡视路线的影响。

二、问题分析

本题给出了某县的公路网络图，要求的是在不同的条件

欧阳阳理创编 2021.03.04

欧阳阳理创编 2021.03.04

下，灾情巡视的最分组方案和路线.将每个乡（镇）或村看作一个图的顶点，各乡镇、村之间的公路看作此图对应顶点间的边，各条公路的长度（或行驶时间）看作对应边上的权，所给公路网就转化为加权网络图，问题就转化图论中一类称之为旅行售货员问题，即在给定的加权网络图中寻找从给定点O出发，行遍所有顶点至少一次再回到点O，使得总权（路程或时间）最小.

本题是旅行售货员问题的延伸－多旅行售货员问题.本题所求的分组巡视的最佳路线，也就是m条经过同一点并覆盖所有其他顶点又使边权之和达到最小的闭链（闭迹）.如第一问是三个旅行售货员问题，第二问是四个旅行售货员问题.

众所周知，旅行售货员问题属于NP完全问题，即求解没有多项式时间算法.显然本问题更应属于NP完全问题. 有鉴于此，一定要针对问题的实际特点寻找简便方法，想找到解决此类问题的一般方法是不现实的，对于规模较大的问题可使用近似算法来求得近似最优解.

三、模型假设

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

忽略天气、故障等因素的影响。

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

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

欧阳阳理创编 2021.03.04

欧阳阳理创编 2021.03.04

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

四、符号说明

w(i,j)……………………………………..任意两点i，j间

的间距。

ei……………………………………..各点的停留时间，

即点权。

V………………………………………汽车行驶速度。 dij………………………………从任意点i至点j的时dw(i,j)/V间，则ij。

五、模型建立与求解

公路网图中，每个乡（镇）或村看作图中的一个节点，各乡（镇）、村之间的公路看作图中对应节点间的边，各条公路的长度（或行驶时间）看作对应边上的权，所给公路网就转化为加权网络图，问题就转化为在给定的加权网络图中寻找从给定点O出发，行遍所有顶点至少一次再回到O点，使得总权（路程或时间）最小，此即最佳推销员回路问题。

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

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

1． 用图论软件包求出G中任意两个顶点间的最短路，构造出完备图G(V,E)，x,yE，

x,yMindGx,y； 2． 3．

输入图G的一个初始H圈；

用对角线完全算法（见[23]）产生一个初始H

圈； 4． 随机搜索出G中若干个H圈，例如2000个； 5． 对第2、3、4步所得的每个H圈，用二边逐

欧阳阳理创编 2021.03.04

欧阳阳理创编 2021.03.04

次修正法进行优化，得到近似最佳H圈； 6． 在第5步求出的所有H圈中，找出权最小的一个，此即要找的最佳H圈的近似解.

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

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

（1）顶点OVi i=1，2，3……n

n（2）i1ViVG

MaxwCiwCji,ji（3），其中Ci为Vi的导出子图

GVi中的最佳推销员回路，Ci为Ci的权，i，j=1，2，

MaxwCi3……n

（4）

wCiMini1n

0MaxwCiwCji,j为该分组的实际均衡

i 定义 称

度。为最大容许均衡度。

MaxwCi 显然001，0越小，说明分组的均衡性越好.取定

一个后，0与满足条件（3）的分组是一个均衡分组.条件（4）表示总巡视路线最短。

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

由于单个推销员的最佳推销员回路问题不存在多项式时间内的精确算法，故多个推销员的问题也不存在多项式时间内的精确算法.而图中节点数较多，为53个，我

欧阳阳理创编 2021.03.04

欧阳阳理创编 2021.03.04

们只能去寻求一种较合理的划分准则，对图１1－9进行粗步划分后，求出各部分的近似最佳推销员回路的权，再进一步进行调整，使得各部分满足均衡性条件（3）。

图11-10 O点到任意点的最短路图（单位：公里）

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

①，②，③，④，⑤，⑥。

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

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

准则二：应将相邻的干枝上的点分在同一组； 准则三：尽量将长的干枝与短的干枝分在同一组. 由上述分组准则，我们找到两种分组形式如下： 分组一：（⑥，①），（②，③），（⑤，④） 分组二：（①，②），（③，④），（⑤，⑥） 显然分组一的方法极不均衡，故考虑分组二。

对分组二中每组顶点的生成子图，用算法一求出近似

欧阳阳理创编 2021.03.04

欧阳阳理创编 2021.03.04

最优解及相应的巡视路线.使用算法一时，在每个子图所构造的完备图中，取一个尽量包含图11-10中树上的边的H圈作为其第2步输入的初始圈。

分组二的近似解见表1。 表1（单位：公里）

小组 名称 I 路 线 总路线长度 191.1 241.9 路线的总长度 558.5 O-P-28-27-26-N-24-23-22-17-16-I-15-I-18-K-21-20-25-M-O II O-2-5-6-L-19-J-11-G-13-14-H-12-F-10-F-9-E-7-E -8-4-D-3-C III O-R-29-Q-30-32-31-33-35-34-A-B-1-O 125.5 因0=

i1,2,3为该分组的均衡度54.2%

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

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

表2（单位：公里）

编号 路线 路线总 长度 长度 I O—P—28—27—26—N—24—23—22—17—191.1 599.8 16—I—15—I—18—K—21—20—25—M—O II O—2—5—6—7—E—8—E—9—F—10—F—216.4 12—H—14—13—G—11—J—19—L—6—5—2—O III O—R—29—Q—30—32—31—33—35—34—192.3 A—1—B—C—3—D—4—D—3—2—O 路 线 C1C2241.9125.5MaxCi241.9因该分组的均衡度C3C1216.4191.1MaxC216.4i0i1,2,311.69%

所以这种分法的均衡性较好。 问题二

欧阳阳理创编 2021.03.04

欧阳阳理创编 2021.03.04

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

6924i巡回，若不考虑行走时间，有: (i

为分的组数).得

i最小为4，故至少要分4组。

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

6917.25间大约为4小时，则每组分配在路途上的时间大

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

599.81735间约为小时，若平均分配给17需4=4.25小时〈6.75小时，故分成

4个组，每个组约

4组是可能办到的。

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

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

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

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

表3（路程单位：公里；时间单位：小时）

组名 I 路线 停留 行走 总长度 时间 时间 O—2—5—6—7—E—8—E—11195.8 17 5.59 —G—12—H—12—F—10—F—9—E—7—6—5—2—O 路 线 完成巡视 的总时间 22.59 欧阳阳理创编 2021.03.04

欧阳阳理创编 2021.03.04

O—R—29—Q—30—Q—28—27—26—N—24—23—22—17—16—17—K—22—23—N—26—P—O III O—M—25—20—21—K—18—I—15—14—13—J—19—L—6—M—O IV O—R—A—33—31—32—35—34—B—1—C—3—D—4—D—3—2—O II 199.2 16 5.69 21.69 159.1 18 4.54 22.54 166 18 4.74 22.74 上表中符号说明：加有底纹的表示前面经过并停留过，此次只经过不需停留；加框的表示此点只经过不停留。

22.7421.690该分组实际均衡度=22.744.62%

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

问题三

我们发现从O点巡视H点的最短时间是所有最短时间中最长的，其距离为77.5公里。其时间为

因此，T=2小时，t=1小时，V=35公里/小时。若巡视人员足够多，完成巡视的最短时间为6.43小时。

在最短时间内限定一下，完成巡视的最优路线应满足如下条件：

（1） 每个组巡视的总时间不能超过最短时间

tH6.43小时；

（2） 所有点都必须访问到，不能漏点； （3） 所需巡视组数要尽量少；

在寻求最优路线时，从距离O点较远的一些点（如点12、10、15、22）开始搜索比较容易，因为到这些点的路线比较少。

具体方法如下：

第一步：依据图1算出从O点到每一个点的最短距离;

欧阳阳理创编 2021.03.04

欧阳阳理创编 2021.03.04

第二步：找出其中最大的一个，算出从O点沿最短的路巡视的时间ti，并求出

ttHti;

第三步：若t1,则这一组只能访问这一点；若t1,则在余下的点找到距离O点最远的点，根据条件看这一组能否巡视这一点；

第四步：若能巡视，则算出t，转到第三步；

第五步：若不能则依次判断次远点、第三远点……,满足总巡视时间不超过tH，就让这组巡视到这一点，直到t1,然后再从第二步开始。

通过以上方法，最后我们找到的最优解是22个组，如下表所示：

编号 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 巡视路径 停留地点 所需时间 O-H-O H 6.43 O-2-5-6-L-19-J-13-14 13,14 6.15 -13-J-19-L-6-5-2-0 O-M-25-21-K-18-I-15 15,16 6.31 -I-16-17-K-21-25-M-O O-2-5-6-7-E-9-F-12-G 12,11 5.94 -11-E-7-6-5-2-O O-2-5-6-7-E-8-E-9-F 8,10 6.22 -10-F-9-E-7-6-5-2-O O-2-5-6-7-E-11-G-11 G 5.58 -E-7-6-5-2-O O-2-5-6-7-E-9-F-9-E 9,F 6.14 -7-6-5-2-O O-2-5-6-L-19-J-18-K J,18 6.29 -21-25-M-O O-M-25-21-K-18-I-18 I 5.49 -K-21-25-M-O O-M-25-21-K-17-22-23 17,22,23 6.12 -N-26-P-O O-2-5-G-L-19-L-6-5-2-O L,19 5. O-M-25-20-21-23-24-N-26 20,21,24 6.10 -P-O O-M-25-21-K-21-25-M-O 25,K 5.50 O-2-5-6-7-E-7-6-5-2-O 6,7,E 6.38 O-R-31-32-35-34-A-1-O 31,32,35,34 6.32 O-R-29-Q-30-Q-28-P-O Q,30,28 6.11 欧阳阳理创编 2021.03.04

时间差 0 0.28 0.12 0.49 0.21 0.85 0.29 0.14 0.94 0.31 0.79 0.33 0.93 0.05 0.11 0.32 欧阳阳理创编 2021.03.04

17 18 19 20 21 22 O-P-26-27-26-N-26-P-O O-2-3-D-4-D-3-2-O O-1-A-33-31-R-29-R-O O-2-5-M-O O-1-B-C-O O-P-O-R-O 26,27,N 3,D,4 A,33,29 2,5,M 1,B,C P,R 6.23 5.99 5.97 5.40 5.98 5.32 0.20 0.44 0.46 1.03 0.45 1.11 问题四

巡视组数已定, 要求尽快完成巡视, 讨论T，t和V的改变对最佳巡视路线的影响。要尽快完成巡视, 就得要求每组完成巡视时间尽量均衡, 因为总的完成巡视时间按最长的完成巡视时间计算。现在讨论在均衡度允许的范围内已分成

n组后，改变T，t和V对最佳巡视路线的影响。显然在分组不变的情况下, 无论了T,t 、V如何改变, 对每组内的最佳巡视路线是没有影响的，但可能会影响各组间的均衡性。因此该问题实际上讨论T，t和V对于分组的影响，即在不破坏原来分组均衡的条件下，T，t和V允许的最大变化范围。

在分n组的情况下，设

Si：表示第i组的最佳推销员回路路线总长度； ：表示第i组所要停留的乡镇的数目；

XiYi：表示第i组所要停留的村的数目； i=1,2,3,…,n

显然，当XiXj,YiYj,SiSj;i,j1,2,3,,n时，即每组的乡（镇）数、村数、最佳巡回的长度均相等，因而分组绝对均衡时，即0=0时，无论T，t和V如何改变都不会改变原来分组的均衡。

（一）不影响分组的均衡时，T，t和V的最大允许变

化范围的讨论：

对任意一个组i，其完成巡视的时间

设均衡分组的最大允许时间均衡度为，即

TiTjMaxTii1,2,3,,n则有

欧阳阳理创编 2021.03.04

欧阳阳理创编 2021.03.04

i1,2,3,记

差，则

MaxTi,,n则表示均衡分组所允许的最大时间误

SiSjV(XiXj)T(YiYj)t (1)

由（1）式我们得到

(XiXj)T(YiYj)tSiSjV （2）

由式（2）可得

1. 当

>0时，要保持原均衡分组不变，T必须满足

的条件为

SiSj(YY)tijVMaxXiXj0XiXjSiSj(YY)tijVTXMiniXj0XiXj XiXj（3）

2.当YiYj0时，要保持原均衡分组不变，t必须满足的

条件为

SiSj(XiXj)tVMaxYiYj0YiYjSiSj(XiXj)tVTYMiniYj0YiYj (4)

3.当SiSj>0时，由（2）式得

① 当

(XiXj)T(YiYj)t时， 当XiXjTYiYjt时，有

SiSjVminSiSj0XXTYYtjiji （6）

有

由（3）—（6）式，当T,t,V三个变量中任意两个变量无论如何变化，都可计算出为保持均衡性分组不变，三个变量所允许的最大变化范围。

（二）分三组的实例讨论

现对分三组的情况进布寸 论 对问题一中所得的三个

欧阳阳理创编 2021.03.04

欧阳阳理创编 2021.03.04

分组 若考虑停留时间和行驶时间 且取Ttt01T02小时，

小时，VV035公里/小时，结果如表5： 表5 （路程单位：公里；时间单位：小时）

Xi编号 Si行驶时间 13 191.1 5.46 I II 11 192.3 5.49 III 11 216.4 6.18 29.1828.4602.5%29.18实际均衡度为。

5 6 6 Yi总时间 28.46 28.49 29.18 实际时间误差为02.5%29.180.72小时。

现分别规定均衡分组的最大允许均衡度2.5%和5%，即最大容许的时间误差分别为0.72小时和1.44小时，计算出T,t,V三个参量中固定任意两个时，要不破坏原均衡分组，另一个参量所容许的变化范围，结果如下表：

表6

2.5%V,t不变 1.25T2 T,V不变 1t1.38 T,t不变 V35 0.72小时 5%1.44小时 0.51T2.740.63t1.75 V17.3 上表可以看出：

（1）当实际均衡度02.5%刚好等于最大容许均衡度2.5%时，要保持原均衡分组，当t，V不变时，T只能减小，且下界为1.25小时；T的上界为T02小时；

T，V不变时，t只能增大，且上界为1.38小时；t的下界为t01小时；

t，T不变时，V只能增大，且下界为35；无上界； （2）当实际均衡度02.5%小于最大容许均衡度5%时，即0时要保持原均衡分组，当t，V不变时，T变化的下界为0.51小时；T的上界为2.74小时；

T，V不变时，t的上界为1.75小时；t的下界为

欧阳阳理创编 2021.03.04

欧阳阳理创编 2021.03.04

0.63小时；

t，T不变时，V增大但无上界，且下界为17.3公里/小时；

（三）对实例结果的分析

上述实例的均衡分组有一个特点，各组的停留时间相等,即取TT02小时，tt01小时，VV035公里/小时，在表5的分组中

定义4 各组的停留时间相等的均衡分组称为停留时间相等的均衡分组，由（7）式得

现讨论对停留时间相等的均衡分组,T,t,V的变化规律，对停留时间相等的均衡分组，分组的实际时间误差：

''Siji其中，为使最大的组的标号；为使Sj最小的组的标

号。 （*）

XiXjT0YiYjt00,当T,t不变时,即TT0,tt0时，因

由（6）式知道，要保持平衡分

组,V的下界应为

取0时，由（9）式得 时，由（9）式得

故有以下定理 定理 当VV0,TT0,tt00时,对图进行停留时间相等的

均衡分组后,设该分组的实际时间误差为0。

（1）若取最大允许时间误差0,当T,t不变时,要使该均衡分组保持不变,V的下界为V0即V只能增加不能减少；

（2）若取最大允许时间误差0,当T,t不变时,要使该均衡分组保持不变,V的变化范围的下界小于V0。

五、优缺点分析

优点

1、本文提出的分组准则简便易行,可操作性强,且可逐步调整使分组达到均衡；

欧阳阳理创编 2021.03.04

欧阳阳理创编 2021.03.04

2、用均衡度的概念定量的刻画了分组的均衡性； 3、在用近似算法求近似最佳推销员回路时,采取了三种不同的方法产生初始圈,使得算法比较完善,得到了误差很小的近似最优解；

4、从理论上定量地讨论了T,V,t的变化又 中 均衡分组灵敏度的影响,得到了很好的结果。

缺点（略）

六、参考文献

[1] 赵静，数学建模与数学实验（第三版），北京：高等教育出版社，2008；

[2] 胡运权，运筹学基础及应用（第三版），哈尔滨：哈尔滨工业大学出版社，1998；

[3] 孙惠泉，图论及其应用，北京：科学出版社，2004。

附录

用Floyd 算法求赋权图中任意两点间最短路径及路长, MATLAB程序代码如下：

n=53;A=xlsread('D:\\file1.xls'); D=A; %赋初值 for(i=1:n) for(j=1:n) R(i,j)=j; end;

end %赋路径初值 for(k=1:n) for(i=1:n) for(j=1:n)

if(D(i,k)+D(k,j)end %更新rij

k %显示迭代步数

D %显示每步迭代后的路长

欧阳阳理创编 2021.03.04

欧阳阳理创编 2021.03.04

R %显示每步迭代后的路径 pd=0;

for i=1:n %含有负权时 if(D(i,i)<0) pd=1; break; end;

end %存在一条含有顶点vi 的负回路 if(pd) break;

end %存在一条负回路, 终止程序 end %程序结束

时间：2021.03.05 创作：欧阳理 欧阳阳理创编 2021.03.04