1、1.问题引入与分析 1)98 1)98年全国大学生数学建模竞赛年全国大学生数学建模竞赛B B题题“最佳灾最佳灾 今年今年(1998年年)夏天某县遭受水灾夏天某县遭受水灾.为考察灾情、为考察灾情、组织自救，县领导决定，带领有关部门负责人到组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视全县各乡（镇）、村巡视.巡视路线指从县政府巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线府所在地的路线.情巡视路线情巡视路线”中的前两个问题是这样的：中的前两个问题是这样的：1）若分三组（路）巡视，试设计总路程最）若分三组（路）巡
2、视，试设计总路程最短且各组尽可能均衡的巡视路线短且各组尽可能均衡的巡视路线.2）假定巡视人员在各乡（镇）停留时间）假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间小时，在各村停留时间t=1小时，汽车行驶速度小时，汽车行驶速度V=35公里公里/小时小时.要在要在24小时内完成巡视，至少应分小时内完成巡视，至少应分几组；给出这种分组下最佳的巡视路线几组；给出这种分组下最佳的巡视路线.公路边的数字为该路段的公里数公路边的数字为该路段的公里数.2)2)问题分析：问题分析：本题给出了某县的公路网络图，要求的是在不本题给出了某县的公路网络图，要求的是在不同的条件下，灾情巡视的最佳分组方案和路线同
3、的条件下，灾情巡视的最佳分组方案和路线.将每个乡（镇）或村看作一个图的顶点，各乡将每个乡（镇）或村看作一个图的顶点，各乡镇、村之间的公路看作此图对应顶点间的边，各条镇、村之间的公路看作此图对应顶点间的边，各条再回到点再回到点O，使得总权（路程或时间）最小，使得总权（路程或时间）最小.公路的长度（或行驶时间）看作对应边上的权，所公路的长度（或行驶时间）看作对应边上的权，所给公路网就转化为加权网络图，问题就转化图论中给公路网就转化为加权网络图，问题就转化图论中一类称之为旅行售货员问题，即在给定的加权网络一类称之为旅行售货员问题，即在给定的加权网络图中寻找从给定点图中寻找从给定点O出发，行遍所有顶点
4、至少一次出发，行遍所有顶点至少一次 如第一问是三个旅行售货员问题，第二问是四如第一问是三个旅行售货员问题，第二问是四本题是旅行售货员问题的延伸本题是旅行售货员问题的延伸多旅行售货员问题多旅行售货员问题.本题所求的分组巡视的最佳路线，也就是本题所求的分组巡视的最佳路线，也就是m条条众所周知，旅行售货员问题属于众所周知，旅行售货员问题属于NP完全问题，完全问题，显然本问题更应属于显然本问题更应属于NP完全问题完全问题.有鉴于此，有鉴于此，经过同一点并覆盖所有其他顶点又使边权之和达到经过同一点并覆盖所有其他顶点又使边权之和达到最小的闭链（闭迹）最小的闭链（闭迹）.个旅行售货员问题个旅行售货员问题.即
5、求解没有多项式时间算法即求解没有多项式时间算法.一定要针对问题的实际特点寻找简便方法，想找到一定要针对问题的实际特点寻找简便方法，想找到解决此类问题的一般方法是不现实的，对于规模较大解决此类问题的一般方法是不现实的，对于规模较大的问题可使用近似算法来求得近似最优解的问题可使用近似算法来求得近似最优解.6.最佳灾情巡视路线的模型的建立与求解问题转化为在问题转化为在给定的加权网给定的加权网络图中寻找从络图中寻找从给定点给定点O出发出发,行遍所有顶点行遍所有顶点至少一次再回至少一次再回回到点回到点O,使得使得总权总权(路程或时路程或时时间时间)最小最小,即即最佳旅行售货最佳旅行售货员问题员问题.最佳
6、旅行售货员问题是最佳旅行售货员问题是NP完全问题完全问题,采用一种采用一种近似算法求其一个近似最优解，来代替最优解近似算法求其一个近似最优解，来代替最优解.算法一算法一 求加权图的最佳旅行售货员回路近似算法求加权图的最佳旅行售货员回路近似算法:1)用图论软件包求出用图论软件包求出G中任意两个顶点间的最短路中任意两个顶点间的最短路,构造出完全图构造出完全图),(,),(),(yxEyxEVG);,(minyxdG2)输入图输入图 的一个初始的一个初始H圈；圈；G3)用对角线完全算法（见用对角线完全算法（见23）产生一个初始圈）产生一个初始圈;4)随机搜索出随机搜索出 中若干个中若干个H圈，例如圈
7、，例如2000个；个；G5)对第对第2)，3)，4)步所得的每个步所得的每个H圈，用二边逐次圈，用二边逐次修正法进行优化，得到近似最优修正法进行优化，得到近似最优H圈；圈；6)在第在第5)步求出的所有步求出的所有H圈中，找出权最小的一个圈中，找出权最小的一个,此即要找的最优此即要找的最优H圈的近似解圈的近似解.因二边逐次修正法的结果与初始圈有关因二边逐次修正法的结果与初始圈有关,故本算法故本算法第第2)，3)，4)步分别用三种方法产生初始圈，以保步分别用三种方法产生初始圈，以保证能得到较优的计算结果证能得到较优的计算结果.问题一问题一 若分为三组巡视，设计总路程最短且各若分为三组巡视，设计总路
8、程最短且各组尽可能均衡的巡视路线组尽可能均衡的巡视路线.此问题是多个售货员的最佳旅行售货员问题此问题是多个售货员的最佳旅行售货员问题.4)min)(1niiC 此问题包含两方面：此问题包含两方面：a)对顶点分组对顶点分组,b)在每组中在每组中求求(单个售货员单个售货员)最佳旅行售货员回路最佳旅行售货员回路.因单个售货员的最佳旅行售货员回路问题不存因单个售货员的最佳旅行售货员回路问题不存存在多项式时间内的精确算法存在多项式时间内的精确算法.故故多多也不也不 而图中节点数较多，为而图中节点数较多，为53个，我们只能去寻求个，我们只能去寻求一种较合理的划分准则，对图一种较合理的划分准则，对图1进行粗
9、步划分后进行粗步划分后,求求出各部分的近似最佳旅行售货员回路的权出各部分的近似最佳旅行售货员回路的权,再进一再进一进一步进行调整，使得各部分满足均衡性条件进一步进行调整，使得各部分满足均衡性条件3).从从O点出发去其它点，要使路程较小应尽量走点出发去其它点，要使路程较小应尽量走O点到该点的最短路点到该点的最短路.故用软件包求出故用软件包求出O点到其余顶点的最短路点到其余顶点的最短路.这些最短路构成一棵这些最短路构成一棵O为树根的树为树根的树.将从将从O点出发的树枝称为点出发的树枝称为干枝干枝.从从O点出发到其它点共有点出发到其它点共有6条干枝，它们的名称条干枝，它们的名称分别为，分别为，.在分
10、组时应遵从准则：在分组时应遵从准则：准则准则1 尽量使同一干枝上及其分枝上的点分在同一组尽量使同一干枝上及其分枝上的点分在同一组.准则准则2 应将相邻的干枝上的点分在同一组；应将相邻的干枝上的点分在同一组；准则准则3 尽量将长的干枝与短的干枝分在同一组尽量将长的干枝与短的干枝分在同一组.由上述分组准则，我们找到两种分组形式如下：由上述分组准则，我们找到两种分组形式如下：分组分组1:（，），（，），（，）（，），（，），（，）分组分组2:（，），（，），（，）（，），（，），（，）分组分组1极不均衡极不均衡,故考虑分组故考虑分组2.分组分组2:(,),(,),(,)对分组对分组2中每组顶点的生成
11、子图中每组顶点的生成子图,用算法一求出用算法一求出近似最优解及相应的巡视路线近似最优解及相应的巡视路线.在每个子图所构造的完全图中在每个子图所构造的完全图中,取一个尽量包含取一个尽量包含上图中树上的边的上图中树上的边的H圈作为其第圈作为其第2)步输入的初始圈步输入的初始圈.分组分组2的近似解的近似解 因为该分组的均衡度因为该分组的均衡度54.2%9.2415.1259.241)(max)()(3,2,1210iiCCC.所以此分法的均衡性很差所以此分法的均衡性很差.为改善均衡性，将第为改善均衡性，将第组中的顶点组中的顶点C,2,3,D,4分给第分给第组（顶点组（顶点2为这两组的公共点），重新分
12、为这两组的公共点），重新分分组后的近似最优解见表分组后的近似最优解见表2.%.69.114.2161.1914.216)(max)()(3,2,1130iiCCC因该分组的均衡度因该分组的均衡度 所以这种分法的均衡性较好所以这种分法的均衡性较好.问题二问题二 当巡视人员在各乡（镇）、村的停留当巡视人员在各乡（镇）、村的停留停留时间一定停留时间一定,汽车的行驶速度一定汽车的行驶速度一定,要在要在24小时内小时内完成巡视完成巡视,至少要分几组及最佳旅行的巡视路线至少要分几组及最佳旅行的巡视路线.由于由于T=2小时小时,t=1小时小时,V=35公里公里/小时小时,需访问需访问的乡镇共有的乡镇共有17
13、个，村共有个，村共有35个个.计算出在乡计算出在乡(镇镇)及及村的总停留时间为村的总停留时间为17 2+35=69小时，要在小时，要在24小时小时内完成巡回，若不考虑行走时间，有内完成巡回，若不考虑行走时间，有:69/i24(i为为分的组数分的组数).得得i最小为最小为4，故，故至少要分至少要分4组组.由于该网络的乡由于该网络的乡(镇镇)、村分布较为均匀、村分布较为均匀,故有可故有可能找出停留时间尽量均衡的分组能找出停留时间尽量均衡的分组,当分当分4组时各组停组时各组停停留时间大约为停留时间大约为69/4=17.25小时，则每组分配在路小时，则每组分配在路路途上的时间大约为路途上的时间大约为2
14、4-17.25=6.75小时小时.而前面讨而前面讨论过论过,分三组时有个总路程分三组时有个总路程599.8公里的巡视路线，公里的巡视路线，分分4组时的总路程不会比组时的总路程不会比599.8公里大太多公里大太多,不妨以不妨以599.8公里来计算公里来计算.路上约用路上约用599.8/35=17小时小时,若平若平均分配给均分配给4个组个组,每个组约需每个组约需17/4=4.25小时小时6.75小小小时小时,故分成故分成4组是可能办到的组是可能办到的.现在尝试将顶点分为现在尝试将顶点分为4组组.分组的原则：除遵从分组的原则：除遵从前面准则前面准则1、2、3外，还应遵从以下准则：外，还应遵从以下准则
15、：准则准则4 尽量使各组的停留时间相等尽量使各组的停留时间相等.用上述原则在下图上将图分为用上述原则在下图上将图分为4组，同时计算组，同时计算各组的停留时间各组的停留时间,然后用算法一算出各组的近似最然后用算法一算出各组的近似最最佳旅行售货员巡回，得出路线长度及行走时间最佳旅行售货员巡回，得出路线长度及行走时间,从而得出完成巡视的近似最佳时间从而得出完成巡视的近似最佳时间.用算法一计用算法一计计算时，初始圈的输入与分三组时同样处理计算时，初始圈的输入与分三组时同样处理.这这4组的近似最优解见表组的近似最优解见表3.表表3符号说明：加有底纹的表示前面经过并停留过符号说明：加有底纹的表示前面经过并停留过,此次只经过不停留此次只经过不停留;加框的表示此点只经过不停留加框的表示此点只经过不停留.可看出可看出,表表3分组的均衡度很好分组的均衡度很好,且完全满足且完全满足24小时完成巡视的要求小时完成巡视的要求.该分组实际均衡度该分组实际均衡度 4.62%74.2269.2174.220
