全国大学生《数学建模》竞赛：1998B

最佳灾情巡视路线的数学模型 单8杨庭栋李哓涛郏长江页 (解放军后勤工学院,重庆400016) 指导教师赵静公()县某 编者按本文力求运用数学概念和方法来严格处理涉及的各种对象;力求借助于几何直 观和生活体验的启发作用,为计算机搜索制定行之有效的操作规则:在数值结果方面,粗估与细 节化相结合,从而提供较为完备的数值描述本文第四部分定理证明中有误,为版面计从删欲 全豹,试索原文 摘要本文将求最佳巡视路线间题转化为图论中求最佳推销员回路的问题,并用近似 算法去寻求近似最优解对分组问题定义了均衡度用以衡量分组的均衡性,对问题1和问题2先 定出几个分组的准则进行初步分组,并用近似算法求每一组的近似最佳推销员回路,再根据均 衡度进行微调,得到较优的均衡分组和每组的近似最佳推销员回路,对问题1得出总路程较短 且各组尽可能均衡的路线,各组的巡视路程分别为216.4公里,191.1公里,192.3公里,总路程 为599.8公里对问题2,证明了应至少分为4组,并求出了分为4组时各组的较优巡视路线各 组的巡视时间分别为2274小时,22.59小时,21.69小时,22,54小时,对间题3,求出完成巡视的 最短时间为6,43小时,并用较为合理的分组的准则,分成22个组对问题4研究了在不影响分 组的均衡条件下,T,t,V的允许变化范围,并得出了这三个变量的关系式,并由此对分三个组 的情况进行了具体讨论 、问题重述(略) 二、模型的假设与符号说明(略 三、模型的建立与分析 本问题要求在某县的乡(镇)村公路网中,寻找从县政府所在地(图中O点)出发,走遍 各乡(镇)村,又回到县政府所在地,使总路程或时间最少将公路网图中,每个乡(镇)或村 看为图中的一个节点,各乡(镇)村之间的公路看作图中对应节点间的边,各条公路的长度 (或行驶时间)看作对应边上的权,所给公路网就转化为图论中的加权网络图,问题就转化 为一个图论问题,即在给定的加权网络图中寻找从给定点O出发,行遍所有顶点至少一次 再回到O点,使得总权(路程或时间)最小,同(,苦是,男宝是 为了讨论方便,先给出图论中相关的一些定义 定义1经过图G的每个顶点正好一次的圈,称为G的哈米尔顿圈,简称H圈 定义2在加权图G=(V,E)中 的可1,平关主的 (1)权最小的哈米顿圈称为最佳H圈; 发弃 (2)经过每个顶点至少一次且权最小的闭通路称为最佳推销员回路. 由定义2可知,本问题是一个寻求最佳推销员回路的问题最佳推销员回路的间题可转 化为最佳H圈的问题.方法是由给定的图G=(V,E)构造一个以V为顶点集的完备图G =(,E),E中每条边(x,y)的权等于顶点x与y在图G中最短路径的权,即

最佳灾情巡视路统的数学模型 371 V(x,y)∈E',o(x,y)= min d o(x,y).甲二 在图论中有以下定理 已的时量 定理1加权图G的最佳推销员回路的权和G′的最佳H圈的权相同 定理2在加权完备图中求最佳H圈的问题是NP一完全问题 我们采用一种近似算法求出该问題的一个近似最优解,来代替最优解,算法如下: 算法一求加权图G(V,E)的最佳推销员回路的近似算法:一 1.用图论软件包求出G中任意两个顶点间的最短路,构造出完备图G(V,E) 其长断由(x,y)∈E,0(x,y)= min dal(x,y),即个 2.输入图G的一个初始H圈; 3.用对角线完全算法2产生一个初始H圈; 4.随机搜索出G′中若干个H圈,例如2000个; 5.对2、3、4步所得的每个H圈,用二边逐次修正法进行优化得到近似最佳H圈; 6.在第5步求出的所有H圈中,找出权最小的一个,此即要找的最佳H圈的近似解 此算法程序见附录(略)(由于二边逐次修正法的结果与初始圈有关,故本算法第2、3、4 步分别用三种方法产生初始圈,以保证能得到较优的计算结果) 问题一,若分为三组巡视,设计总路程最短且各组尽可能均衡的巡视路线 此问题是多个推销员的最佳推销员回路问题即在加权图G中求顶点集V的划分V 2…,Vn,将G分成n个生成子图Gv1,Gv21,,GIVJ使得 (1)顶点O∈V,i=1,2,3,…,n G). max a(C)-a(C )I (3)-mxa(C)≤a,其中C为V的导出子图Gw1]中的最佳H圈 a(G1)为C的权,i,j=1,2,3,…,n (4)∑a(C)=mn max o(C))-o(C)I 定义3称a axa(C)为该分组的实际路程均衡度a为最大容许 均衡度,显然0≤a0≤1,a越小,说明分组的均衡性越好取定一个a后,a与a满足条件 (3)的分组是一个均衡分组条件(4)表示总巡视路程最短 此问题包含两方面:第一,对顶点分组;第二,在每组中求最佳推销员回路,即为单个推销 员的最佳推销员问题我们只能去寻求一种较合理的划分准则,对图1进行初步划分后,求出 各部分的近似最佳推销员回路的权,再进一步进行调整,使得各部分满足均衡性条件(3) 从O点出发去其它点,要使路程较小应尽量走O点到该点的最短路.故用图论软件包 求出O点到其余顶点的最短路,这些最短路构成一棵O为树根的树,将从O点出发的树枝 称为干枝,见图1,从图中可以看出,人O点出发到其它点共有6条干枝,它们的名称分别为 ①,②,③,④,⑤,⑥.,,,立高 根据实际工作的经验及上述分析,在分组时应遵从以下准则: 准则一尽量使同一干枝上及其分枝上的点分在同一组;

372 全国大学生数学建模竞赛优秀论文汇编 准则二应将相邻的干枝上的点分在同一组;3 准则三尽量将长的干枝与短的干枝分在同一组 平以中 由上述分组准则,我们找到两种分组形式如下:亲最0图对1三 分组一:(⑥,①),(②,③),(⑤,④);同中名 分组二:(①,②),(③,④),(⑤,⑥); 出同出束氧路将一且国 显然分组一的方法极不均衡,故考虑分组二 对分组二中每组顶点的生成子图,用算法一求出近似最优解及相应的巡视路线使用算 法一时在每个子图所构造的完备图中取一个尽量包含图1中树上的边的H圈作为其第2 步输入的初始圈 ⑤ 全 Q ① ② 图1O点到任意的最短路线图 9分组二的近似解见表1出的2中其 表1(单位:公里) 小组名称 总路线长度路线的总长度 10-P-28=27-26=N-24-23-22-17-16-1-15 1-18-K-21-20-25-M 191.1 Ⅱ0-2-5-6-L-19-J-11-G-13-14-H-12 10=F-9E-7-E-8-4-D-3-C=o 241.9 Ⅲ0-R-29-0-30-32-31-33-35-34-A-B=1 558,5 因为该分级的均衡度 a(C1)-(C2)241.9-125.5 去出边C a(C;) 241.9 2% 东其点O 所以此分法的均衡性很差. 为改善均衡性,将第Ⅱ组中的顶点C,2,3,D,4划归第Ⅲ组,重新分组后的近似最优解 见表2,各组的近似最优巡视路线见图2

最佳灾情巡视路线的数学模型 373 表2(单位:公里 编号 路线 路线长度路线总长度 I|o-P-28-27-26-N-24-23-22-17-16=1-15 K-21-20-25-M-O 191.1 Ⅱo-2-5-6-7-E-8-E-9-F-10-F-12-H-14 13-G-11-J-19-L-6-5-2-0 216.4 599.8 O-R-29-Q-30-32-31-33-35-34-A-1-B 人印, B 一图2分为3组时各组的巡视路线图 注:图中粗线部分为Ⅱ组与Ⅲ组共同经过的路线 下面对此结果进行分析因该分组的均衡度 a(C1)-o(C2)=2164-191,11 m3(C) 216.4 1.69% 所以这种分法的均衡性较好.若取最大容许的均衡度a=12%,则这是一个均衡分组 用算法一算出整个网络图的近似最佳推销员巡回为O-C-3-2-5-D-4-8- E-9-F-10-F-12-H-12-G-11-J-19-L-7-6-M-N-25-20 21-K-18-J-13-14-15-1-16-17-22-23-24-27-26-P-28-Q 30-Q-29-R-31-33-31-32-35-34-AB-O 总路长为588.6公里.而表2中三组巡回的总路线长为599.8公里可以认为这样设计 的分组方法和巡回路线能使总路线近似最短 问题二当巡视人员在各乡(镇)、村的停留时间一定,汽车的行驶速度一定,要在 小时内完成巡视,至少要分几组及最佳的巡视路线 由于T=2小时,t=1小时,V=35公里/小时,需访问的乡镇共有17个,村共有35 个,计算出在乡(镇)及村的总停留时间为17×2+35=69小时,要在24小时内完成巡回, 考虑行走时间,故至少要分4组 由于该网络的乡(镇)、村分布较为均匀,故有可能找出停留时间尽量均衡的分组,当分 4组时各组停留时间大约为=17.25小时,则每组分配在路途上的时间大约为24-17.25 =6.75小时.而前面讨论过,分三组时有个总路599.8公里的巡视路线,分4组时的总路程

374 全国大学生数学建模竞赛优秀论文汇编 不会比5998公里大太多,不妨以5998公里来计算路上时间约为 17小时,若平均 分配给4个组,每个组约需=425小时<65小时,故分成4组是可能办到的 现在尝试将顶点分为4组分组的原则:除遵从前面准则一、二、三外,还应遵从以下准 准则四尽量使各组的停留时间相等 用上述原则在图1上将图分为4组,同时计算各组的停留时间,然后用算法一算出各组 的近似最佳推销员巡回得出路线长度及行走时间,从而得出完成巡视的近似最佳时间用 算法一计算时,初始圈的输入与分三组时同样处理 注1.图中粗线表示其中两组都要经过的路段,2,方框中的点表示其中两组都经过的地 主3.方框中有两字符,罗马字符表示要停留于此地的巡视组另一字符表示此地点的代号 这4组的近似最优解见表3,各组的近似最优巡视路线见图3 表2(单位:公里 组名 路线 路线停留行走完成巡视 总长度时间时间的总时间 10-2-5-6-7-E-8-E-11-G-12-H-12 10-F-9-E-7-6 1995.8175.5922.59 ∥O-R-29-Q-30-Q-28-27-26-N-24 23-22-17-16-17-K-22-23-N-26 165.6921.69 ⅢO=M=25=20-21-K-18=1-15-14-13 J-19-L-6-M-O 1591184 Ⅳ|O-R-A-33-31-32-35-34-B+1-C D-4D-3-2-0阴 :166-184.74 22.74 Ⅳ 总是()出 H 的所 一图3分为4组时各组的巡视路线图