98年数学建模竞赛水灾巡视论文.pdf

1 最佳灾情巡视路线 一、摘要 本文将最最佳巡视路线问题转化为图论中 TSP （旅行商问题） ， 将赋权无向图的权值 生成原始数据， 利用 floyd 算法生成两两节点的邻接矩阵， 并用模拟退火法求得近似解， 给出均衡度。对于问题 1 和问题 2 本文分别运用最小生成树、模糊聚类分析（采用 ward 法）进行分组，根据均衡度再进行微调。对问题 1 得出总路线最短均衡度较好的一组路 线为：578.5 公里,17.8%；总路线较好均衡度最佳的路线为：602 公里，11.3%。另外本 文还给出了其他两种算法：改进的模拟退火法（增加虚拟地点转化为 TSP 问题） ，其最 短路线和均衡度分别为：577.9 公里，18%；改进的蒙特卡罗算法（概率模型） ，其最短 路线和均衡度分别为：616.5,公里，36%。对于问题 2，本文按一定的规则利用最小生成 树分组，得到 4 组最短巡视时间为 22.53 小时，符合小于 24 小时的要求。 对于问题 3，本文做了如下的定性分析：当 V 不变，若 T，t 越大，则说明速度对总 时间的影响越小，那么最佳路线对地点的分配也就越平均；当 T,t 不变，若 V 越大，则 说明停留时间对总时间的影响越小，那么最佳路线对每组经过路程的分配也就越平均。 对于问题 4，本文的基本思路是两两配对根据邻接关系就近搜索配对，三点配对采 取得到的最短巡视时间为 6.43 小时，共 22 个巡视组。 本文采取的模型求解方法还有改进的空间。问题 1 和问题 2 的关键在于分组，根据 最小生成树和聚类法的分组是不完全合理的，均衡度和最短路线不能同时保证，需要进 行调节工作，可以采取边界调整法，且将最长路程的一组的点有规律的分到路程最短的 点以达到均衡度较小的原则；将相邻的点尽可能地分在一组；尽可能地减少重复的边， 形成一个回路； 试验多次得出最优的近似解。 此外， 模拟退火法对城市数量比较多的 TSP 问题不能较好地给出最优解；蒙特卡罗算法对概率空间的准确性要求较高。问题 3 做了 定性分析，但对于 T,V 相互的影响难以做分析，有待改进。 关键词：最小生成树 模糊聚类 蒙特卡罗改进 模拟退火法 就近搜索配对 2 二、问题的重述 已知某县的乡（镇） ，村公路图及里程数，为考察灾情，领导带领有关部门负责人 巡视灾区。若分三组巡视，求解出巡视路线的最短总路程且保证一定均衡度（问题 1） 。 根据给定的 T,t，V（乡镇停留时间，村停留时间，汽车行驶速度） ，若要在 24 小时内完 成巡视，求解最少需要的巡视组数（问题 2） ；若组数不限且要在最短时间内完成巡视， 求解最佳路线（问题 3） 。最后，讨论 T，t，V 三个量对最佳路线的影响（问题 4） 。 三、问题的分析 3.1 问题 1 考虑极端情形，三组巡视路线中有两组不参与巡视，则问题 1 转化为 TSP（单个旅 行商)问题。该问题可抽象为图论的赋权连通图问题，即图中该县公路网的里程数为赋 权无向连通图的边权， 找到一个包含节点 O 的回路， 使其至少遍历所有节点一次。 易知， 该情形总路程最短，但均衡度最差。 为达到题目所要求的路程最短且三组均衡的要求， 本题的关键是如何将该县的公路 网分为 3 个合理的子图，将多个旅行商问题转化为 3 个子图内单个旅行商的问题。 3.2 问题 2 从问题 1 的极端情形分析中知， 单个旅行商遍历所有节点的最短路程是三组巡视路 线最短总路程的下界，由此可知问题 2 中最短总路程在 506 公里以上。最短时间为 (500/35+1*35+2*17)/3=27.824， 因此三组不可能在 24 小时内完成巡视， 至少需要分 4 组一同巡视。 3.3 问题 3 由于巡视时间随着 T,t,1/V 的增大而增大， 因此我们可以对其进行定性分析以确定 对巡视的最佳路线的影响。 3.4 问题 4 分若干巡视组巡视的最短时间是某一组仅巡视离 O 点最远点所需的时间， 因此可用 Dijkstra 算法求出 O 点与其他点的距离， 按照一定的分组方式进行分组， 保证各组时间 小于等于仅巡视离 O 点最远点所需的时间。 四、符号的说明 1、i：乡（镇） 、村的编号，0 53i 2、j：巡视分组编号 3、C：巡视路线总路程 4、m：停留的乡（镇）的个数 5、n：停留的村的个数 6、tt：每组巡视所花费的时间 五、模型的假设 1、各个村（镇） 、乡，允许巡视组经过但不访问 2、水灾不会影响汽车行驶速度与巡视组停留时间 3 六、模型的建立 6.1 问题 1 目标函数： 123 min()CCC 0 min() ， 33 11 03 1 max()min() max() jj jj j j CC C 0 （ 0 01 ）为均衡度且越小越均衡。 6.2 问题 2 每组巡视所需的时间： 2 j jjj C ttmn V 目标函数： 1234 min()tttttttt min(max) j j tt 6.3 问题 3 由问题 2 可知： j jjj C ttTmtn V ，该函数是 T，t，1/V 的增函数，因此可对其进行定性分析。 6.4 问题 4 在初始数据分类测试之后可知，一些点例如 H,G,I 由于离 O 点较远，因此只可能单 个点为一组；根据就近配对分组思想，我们可处理一部分两两配对的问题。对于三个点 分组的情况，采取任意一乡两村的最佳遍历路径选取算法思路： 由起点出发经过三个点再回到起点总共有 4 种情况： 1、由起点出发到 city-0，此段路径上没有 city-1 和 city-2，此时应将 city1,2,3 按 距离起点由近到远 排列，由近到远依次遍历，即可保证最段路径。 2、到 city-0 的路径上有 city-1 没有 city-2，此种情况直接到 city-2，再由最短的路 径回到起点即可。 3、同 2 4、city-0 的路径上有 city-1 和 city-2，由起点直接到 city-0，再原路返回，即可。 七、模型的求解和结果 7.1 问题 1 7.1.1 最小生成树法 根据最小生成树求解的 Prim 算法，利用 C 语言编写程序（见附录）（见附录） ，我们得到最小 生成树，如下图所示： 4 根据最小生成树，按照以下原则进行分组： 1、分解点尽量靠近 O 点 2、三个子图的个数均衡，尽量在 17 个左右 3、尽可能使三个子图均为连通图，减少重复的路径，形成回路 由以上规则得出最佳路线如下表： 路径 路程 总路程 均衡度 OM2521K221716I 1514H(14)13(J)18 J19L(652)O 216.6 602.5 13.2% OP26N23242728Q 30(Q)29R313332 3534A1O 188.1 O(1)BC3D48E11 G12F10(F)9(E)7 652O 197.8 （注：括号内是旅行商经过但不巡视的点） 7.1.2 模糊聚类分析 根据模糊聚类的相关理论，以两两节点之间的距离为聚类标准进行分组，将赋权无向图 分为三个子图，即距离相近的点分为一簇。利用 matlab 工具箱中的谱系聚类法（程序 见附录见附录）对公路网图进行聚类分析（谱系聚类图见见附录附录） ，编写模拟退火法程序对三组 路线 TSP 问题进行求解，并根据结果调整分类。最好结果如下表： 5 路径 路程 总路程 均衡度 OM2520L19J18 I15(I)161722K 212324N(26P)O 195.0 578.5 17.8% O(2)5(6)7(E)9F 10(F)12H1413G 11E84D32O 210.5 OP262728Q30(Q )29R3133323534 A1BCO 173.0 （注：括号内是旅行商经过但不巡视的点） 7.1.3 改进的模拟退火法 分析： 如果此题只有一组人巡视的话， 此问题就是一个有 53 个城市的旅行商 （TSP） 问题，而对于 TSP 问题，我们用模拟退火法可以进行模拟求解。对于此题，我们可以通 过增加虚拟地点的方式扩充地图，从而将其转化为 TSP 问题。 建立：为了能将问题的解用一组数列表达，我们假设地图上存在 54,55 号地点，它 们是出发点（50）的“映像” 。所以 54,55 号点的性质有：到 50 号点的距离为 0 且到其 它各点的距离等于 50 号点到该点的距离。这样，1 到 55 个地点的排列就是问题 1 的解 空间。为了防止出现三组路程分布不均衡的情况，我们可以算出三组路径的极差，再经 过函数转换将其加到总路径长度里。这样，我们用模拟退火法求解出的最优解既可以使 总路程小也可以使各组路径分布尽量均衡。 （主程序见附录） 最佳路线如下表： 路径 路程 总路程 均衡度 O2925Q27283032313335341 BCO 194.9 577.9 18% OP26N242321K221716I15 18J19L2025MO 210.5 O3D48E9F1012H1413G11 7652O 172.5 6 7.1.4 改进的蒙特卡罗算法 蒙特卡罗法（Monte Carlo method）是以概率和统计的理论、方法为基础的一种计 算方法， 将所求解的问题同一定的概率模型相联系， 用电子计算机实现统计模拟或抽样， 以获得问题的近似解。 本题中将乡（镇） ，村分成三组即构成概率模型，每次以一定的规律选择组别，再 以一定的规律生成下一个视察地点，直到视察完所有地点。多次模拟，取出最优解。 本题算法中的概率模型 1.选择组别方法： 当前已走路程最短的越有可能被选中 2.选择下一个视察地点的标准： 距离当前城市越近的地点越有可能被选中 已被选中次数越少的城市越有可能被选中 三个组的当前城市趋向于越来越远 最佳巡视路线如下表所示： 路径 路程 总路程 均衡度 OC3D48E11G 13J18K212520 19L652O 205.1 617.9 3.4% OP26N232427 28Q29RA3331 3230323534B1 O 202.8 O2567E9F10 F12H1415I16 172223NMO 210.0 7.2 问题 2 在问题 1 得到最小生成树的基础上， 对三组的边界进行调整得到分成四组的最佳路线和 所需要的时间如下图： 图形 路径 最短路程 时间 OP26N24 23221617K 25M532 O 155.7 22.4486 7 O6L19J 1314H15I 1821M20 O 184 21.2571 OB343532 30Q2827 29R3133A 1O 158.4 22.5257 OCD48E 910F12G 117O 186.4 22.3257 684.4 max(time)= 22.5257 注：上图均衡度 0 22.5321.26 5.6% 22.53 ,因此四组路线均衡度极佳。 7.3 问题 3 1、当 V 不变，若 T，t 越大，则说明速度对总时间的影响越小，那么最佳路线对地点的 分配也就越平均。 2、当 T,t 不变，若 V 越大，则说明停留时间对总时间的影响越小，那么最佳路线对每 组经过路程的分配也就越平均。 7.4 问题 4 利用 Floyd 矩阵可知 O 点到其他各点的距离，在区间0,77.525之间，将此区间分为 0,42.525,42.525,60.025,60.025,77.525三个区间，节点的分布如下表： 区间 分组依据 节点 8 0 O (0,42.525 可支持 2 个乡（镇） 可支持 1 个乡（镇）2 个村 1 2 3 4 5 6 7 20 21 23 25 26 27 28 29 30 31 32 33 34 35 A B C D E L M N P Q R 42.525,60.025 可支持 1 个乡（镇）1 个村 8 9 11 17 18 19 22 24 F J K 60.025,77.525) 可支持 1 个乡（镇） 可支持 2 个村 10 12 13 14 15 16 G I 77.525 H 分组过程： O 点距 H 点（最远点）往返所需的最短时间为 6.43 小时，因此，其他分组的时间尽量要 在 6.43 小时以内，一下是分组过程： 1、在60.025,77.525)之内的点，只可支持 1 个乡（镇） ，因此 G，I 点分别为 2 组；另 外 10，12,13，14,15,16 点根据最短邻接关系两两配对后发现 13,14,为一组，15,16 为 一组，而 10，12 不可配对，再考虑其分别与42.525,60.025内的节点配对；根据最短 邻接关系发现 8,10 为一组，11，,12 为一组。 2、42.525,60.025内节点可支持 1 个乡（镇）1 个村，因此首先罗列所有乡（镇）- 村的配对组合，算出其最短距离，若最短距离小于 120.05 公里则形成配对；若满足条 件的分组不止一组，选择最短距离较大的分组。例如：9 可与 F,J,K 配对，其距离分别 为110.2,139,140.2， 则根据以上规则， 应选取 F 与之配对。 配对结果为： 9,F 为一组， 18,J 为一组，19,K 为一组；则该组内剩下 17,22,24，与0,42.525组内节点进行配对。 3、 最后0,42.525内节点有 24 个村和 11 个乡镇 （尽量使分组后所需的时间接近 6.43， 使得各个路线更加均衡） ，分为以下三种情况： 类型 情况 举例 来回一致型 6,7,E 回路型 5,25,L 9 叉路型 26,27,N 综上所述分组情况如下： （共 22 组，所需的最短时间为 6.43 小时） 分组 路径 路程 时间 3,4,D O23D32O 69.8 5.99 6,7,E O2567E7652O 83.4 6.38 5,25,L O256L25MO 82.8 6.37 24,M OMN24N26PO 91.5 5.61 18,J O256L19J18K2125M O 115.4 6.30 17,22,23 OM2521K172223N26P O 109.3 6.12 8,10 O2567E8E9F10F9 E7652O 147 6.20 1,B,C O1BCO 34.4 5.98 2,20,21 O2567L202125MO 91.4 5.61 11,12 O2567E1112F9E76 52O 137.8 5.94 13,14 O256L19J131413J19 L652O 145.4 6.15 15,16 OM2521K1716I15I18 K2125MO 150.8 6.31 G O2567E11G11E765 2O 125.4 5.58 H O2567E9F12H12F9 E7652O 155155 6.436.43 I OM2521K18I18K2125 MO 122.2 5.49 9,F O2567E9F9E765 2O 110.2 6.15 10 19,K O256L192021K2125M O 111.2 6.18 26,27,N OP26N262726NPO 78.1 6.23 P,R OP29RO 46 5.31 28,30,Q OP28Q30Q29RO 73.9 6.11 29,33,A O1A33AR29RO 68.6 5.96 31,32,34,35 OR31323534A1O 81.1 6.32 注：表中字体加粗部分为完成巡视所需的最短时间 八、模型的评价和改进 8.1 模型的评价 问题1 和问题2的关键在于分组， 根据最小生成树和聚类法的分组是不完全合理的， 均衡度和最短路线不能同时保证，因此需要进行调节工作，此时可以采取边界调整法， 且将最长路程的一组的点有规律的分到路程最短的点以达到均衡度较小的原则； 将相邻 的点尽可能地分在一组；尽可能地减少重复的边，形成一个回路；试验多次得出最优的 近似解。模拟退火法对城市数量比较多的 TSP 问题不能较好地给出最优解；蒙特卡罗算 法对概率空间的准确性要求较高。 问题 3 做了定性分析，但对于 T,V 相互的影响难以做分析，有待改进。 问题 4 分组的思路清晰，结果也较好。 8.2 模型的改进 问题 1 和问题 2 的分组问题可以采用更加严格的搜素方法， 例如最小生成树可采用 增环、扩环的调整策略等。问题 3 中可尝试数据测试、模拟的方法，得出影响的程度。 九、参考文献 1、于颂康.灾情巡视的最佳路线.J.数学的时间与认识.1999.1 2、王海龙，周辉仁.基于遗传算法的多旅行商问题研究.J.计算机应用研究.2009.5 3、韦芳芳，杨兰兰，柏瑞.灾情巡视路线的设计.J数学的实践与认识.1999.1 4、王大志，汪定伟.一类多旅行商问题的计算及仿真分析.J.系统仿真学报.2009.20 5、罗卢杨，龙继东，唐小军.灾情巡视路线寻优模型.J.数学的实践与认识.1999.1 6、杨庭栋，李晓涛，郑长江.最佳灾情巡视路线的数学模型.J.数学的实践与认 识.1991.1 十、附录 附录一 C 语言 floyd 算法 #include “stdafx.h“ 11 #include“string.h“ #include “iostream“ #define maxn 53 using namespace std; class MGraph float matrixmaxn+1maxn+1; int pathmaxn+1maxn+1; int smaxn+1; public: MGraph(); void shortpath(); void show(); ; FILE *fp; MGraph:MGraph() int start,end;float len; /邻接矩阵初始化 for(int i=1;itotaldis1 order3=order1 totaldis3=distance(address,order3) dist2=dist(order3,map) totaldis3=(max(dis