《建模案例：最佳灾情巡视路线》由会员分享，可在线阅读，更多相关《建模案例：最佳灾情巡视路线（7页珍藏版）》请在金锄头文库上搜索。
1、建模案例：最佳灾情巡视路线这里介绍1998年全国大学生数学模型竞赛B题中的两个问题.、问题今年夏天某县遭受水灾.为考察灾情、组织自救，县领导决定，带领有关部门 负责人到全县各乡（镇）、村巡视.巡视路线指从县政府所在地出发，走遍各乡 （镇）、村，又回到县政府所在地的路线.1. 若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的路线.2. 假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小 时，汽车行驶速度V=35公里/小时.要在24小时内完成巡视，至少应分几组；给 出这种分组下最佳的巡视路线.乡镇、村的公路网示意图见图11-9.图 11-9假设1 .汽车在路上的速度总是一定，
2、不会出现抛锚等现象；2 .巡视当中，在每个乡镇、村的停留时间一定，不会出现特殊情况而延误时间;3 .每个小组的汽车行驶速度完全一样；4.分组后，各小组只能走自己区内的路，不能走其他小组的路，除公共路外.三、模型的建立与求解将公路网图中，每个乡（镇）或村看作图中的一个节点，各乡（镇）、村之 间的公路看作图中对应节点间的边，各条公路的长度（或行驶时间）看作对应边 上的权，所给公路网就转化为加权网络图，问题就转化为在给定的加权网络图中 寻找从给定点O出发，行遍所有顶点至少一次再回到O点，使得总权（路程或 时间）最小，此即最佳推销员回路问题.在加权图G中求最佳推销员回路问题是NP完全问题，我们采用一种
3、近似 算法求出该问题的一个近似最优解，来代替最优解，算法如下：算法一求加权图G （V, E）的最佳推销员回路的近似算法：1. 用图论软件包求出 G中任意两个顶点间的最短路，构造出完备图Gf（V, E），V（x, y）e E， & （x, j）= Mind G, j）；2. 输入图G的一个初始H圈；弓3. 用对角线完全算法（见23）产生一个初始H圈；4. 随机搜索出G，中若干个H圈，例如2000个；5. 对第2、3、4步所得的每个H圈，用二边逐次修正法进行优化，得到近 似最佳H圈；6. 在第5步求出的所有H圈中，找出权最小的一个，此即要找的最佳H 圈的近似解.由于二边逐次修正法的结果与初始圈有关
4、，故本算法第2、3、4步分别用三 种方法产生初始圈，以保证能得到较优的计算结果.问题一若分为三组巡视，设计总路程最短且各组尽可能均衡的巡视路线.此问题是多个推销员的最佳推销员回路问题.即在加权图G中求顶点集V的 划分V1,V2,.匕，将G分成n个生成子图Gy1 GV2.gVJ，使得（1） 顶点 O e 匕i=1，2, 3.:n 之 （2）ni_ 1 Vi = V （g ）（3） Max &.）-&），其中c为v.的导出子图g中的最佳推销员 Max ）卯C .回路，3（C）为 C 商权，i，j=1，2, 3n Y w （C, ）= Min定义i称M： b （J E C,）为该分组的实际均衡度.a
5、为最大容许均。_衡度.显然0 a 0 1，a0越小，说明分组的均衡性越好.取定一个a后，a0与a满 足条件（3）的分组是一个均衡分组.条件（4）表示总巡视路线最短.此问题包含两方面：第一、对顶点分组；第二、在每组中求最佳推销员回路， 即为单个推销员的最佳推销员问题.由于单个推销员的最佳推销员回路问题不存在多项式时间内的精确算法，故 多个推销员的问题也不存在多项式时间内的精确算法.而图中节点数较多，为53 个，我们只能去寻求一种较合理的划分准则，对图1 1-9进行粗步划分后，求出各部分的近似最佳推销员回路的权，再进一步进行调整，使得各部分满足均衡 性条件（3）.从O点出发去其它点，要使路程较小应
6、尽量走O点到该点的最短路.故用图 论软件包求出O点到其余顶点的最短路，这些最短路构成一棵O为树根的树， 将从O点出发的树枝称为干枝，见图11-10,从图中可以看出，从O点出发 到其它点共有6条干枝，它们的名称分别为，.根据实际工作的经验及上述分析，在分组时应遵从以下准则： 准则一：尽量使同一干枝上及其分枝上的点分在同一组； 准则二：应将相邻的干枝上的点分在同一组； 准则三：尽量将长的干枝与短的干枝分在同一组.由上述分组准则，我们找到两种分组形式如下：分组一：（，），（，），（，） 分组二：（，），（，），（，）显然分组一的方法极不均衡，故考虑分组二对分组二中每组顶点的生成子图，用算法一求出近似
7、最优解及相应的巡视路 线.使用算法一时，在每个子图所构造的完备图中，取一个尽量包含图11-10中树 上的边的H圈作为其第2步输入的初始圈分组二的近似解见表1.表1 （单位：公里）小组名称路线总路线长度路线的 总长度IO-P-28-27-26-N-24-23-22-17-16-I-15-I-18-K -21-20-25-M-O191.1558.5IIO256L19J11G1314H12F10F9E-7-E 84D3C241.9mOR29Q303231333534AB1O125.5因为该分组的均衡度a 0 =（C1）一?（C ） = 241 .9 - 125 .5 = 54.2%Max ro（C2
8、41 .9i=1,2,31所以此分法的均衡性很差.为改善均衡性，将第II组中的顶点C, 2, 3, D, 4分给第m组（顶点2为 这两组的公共点），重新分组后的近似最优解见表2.表2 （单位：公里）编号路线路线长度路线总 长度IO P 28 27 26 N 24 23 22 17 _16I15I-18K-2120-25-M O191.1599.8IIO 256 7 E 8 E9F 10F12H14 13 G 11J19 L65 2O216.4mOR29Q303231333534 A 1 B C 3 D 4 D 3 2 O192.3iTTt八 awC J(C J 216.4 191.1 .因该分
9、组的均衡度a =m；x(c ) =216.4= n.69%i=1,2,3所以这种分法的均衡性较好.问题二当巡视人员在各乡（镇）、村的停留时间一定，汽车的行驶速度一 定，要在24小时内完成巡视，至少要分几组及最佳的巡视路线.由于T=2小时，t=1小时，V=35公里小时，需访问的乡镇共有17个，村共 有35个.计算出在乡（镇）及村的总停留时间为17x 2+35=69小时，要在24小 时内完成巡回，若不考虑行走时间，有 69 24 （i为分的组数）.得i最小为4, i故至少要分4组.由于该网络的乡（镇）、村分布较为均匀，故有可能找出停留时间尽量均衡 的分组，当分4组时各组停留时间大约为69 = 17
10、.25小时，则每组分配在路途上 4的时间大约为24-17.25=6.75小时.而前面讨论过，分三组时有个总路程599.8公 里的巡视路线，分4组时的总路程不会比599.8公里大太多，不妨以599.8公里 来计算.路上时间约为5998 = 17小时，若平均分配给4个组，每个组约需17 =4.25 354小时6.75小时，故分成4组是可能办到的.现在尝试将顶点分为4组.分组的原则：除遵从前面准则一、二、三外，还应 遵从以下准则：准则四：尽量使各组的停留时间相等.用上述原则在图11-10上将图分为4组，同时计算各组的停留时间，然后用算 法一算出各组的近似最佳推销员巡回，得出路线长度及行走时间，从而得
11、出完成 巡视的近似最佳时间.用算法一计算时，初始圈的输入与分三组时同样处理.这4组的近似最优解见表3.表3 （路程单位：公里；时间单位：小时）组名路线停留总长度时间O2567E8E 11G12H12F10195.8F9E7652O17IIOR29Q30Q28 2726N24232217199.21616172223N行走时间5.595.69完成巡视 的总时间22.5921.6926POOM252021K18 mI151413J19L6 159.118MOORA33313235 IV34B1C3D4D1661832O4.544.7422.5422.74上表中符号说明：加有底纹的表示前面经过并停留过，此次只经过不需停留;加框的表示此点只经过不停留.该分组实际均衡度a = 2274”剧=4.62% 022.74可以看出，表3分组的均衡度很好，且完全满足24小时完成巡视的要求.
