建模案例：最佳灾情巡视路线-同济大学数学科学学院

《建模案例：最佳灾情巡视路线-同济大学数学科学学院》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、建模案例：最佳灾情巡视路线这里介绍1998年全国大学生数学模型竞赛B题中的两个问题.今年夏天某县遭受水灾•为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视•巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线.1.若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的路线.2.假定巡视人员在各乡（镇）停留时间T=2h,在各村停留时间tlh,汽车行驶速度V=35km/h.要在24h内完成巡视，至少应分几组；给出这种分组下最佳的巡视路线.乡镇、村的公路网示意图见图1・假设1.汽车在路上的速度总是一定，不会出现抛锚等现象;2.巡视当中，在

2、每个乡镇、村的停时间一定，不会出现特殊情况而延误时间;3.每个小组的汽车行驶速度完全一样；4.分组后，各小组只能走自己区内的路，不能走其他小组的路（除公共路外）・三、模型的建立与求解将公路网图中，每个乡（镇）或村看作图中的一个节点，各乡（镇）、村之间的公路看作图中对应节点间的边，各条公路的长度（或行驶时间）看作对应边上的权，所给公路网就转化为加权网络图，问题就转化为在给定的加权网络图中寻找从给定点O出发，行遍所有顶点至少一次再回到o点，使得总权（路程或时间）最小，此即最佳推销员回路问题.在加权图G中求最佳推销员回路问题是NP—完全问题，我们采用一种近似算法求出该问题的一个近似最优解

3、，来代替最优解，算法如下:算法一求加权图G（V,E）的最佳推销员回路的近似算法：1.用图论软件包求出G中任意两个顶点间的最短路，构造出完备图G'（V,E'）,V（x,y）eE',co[x,y）=mindG（兀,y）；2.输入图G‘的一个初始H圈；3.用对角线完全算法产生一个初始H圈；4.随机搜索出G'中若干个H圈，例如2000个；5.对第2、3、4步所得的每个H圈，用二边逐次修正法进行优化，得到近似最佳H圈；6.在第5步求出的所有H圈中，找出权最小的一个，此即要找的最佳H圈的近似解.由于二边逐次修正法的结果与初始圈有关，故本算法第2、3、4步分别用三种方法产生初始圈，以保证能得到较

4、优的计算结果.问题一若分为3组巡视，设计总路程最短且各组尽可能均衡的巡视路线.此问题是多个推销员的最佳推销员回路问题•即在加权图G中求顶点集V的划分%,岭,…，匕,将G分成〃个生成子图G[V；],G[岭]，…,G[«],使得（1）顶点OgVi9Z=L2,3,•・・,〃；⑵[Jvt.=v（g）;i=（3）叱x0C）P（Cj

5、“，其中g为％的导出子图G[%]中的最佳推销maxco（Cz）i员回路，0（cj为G的权,i,7=1,2,3,…（4）取最小./=1maxco（C-co（C定义称％=亠——:—为该分组的实际均衡度也为最大容max69（Cj许均衡度.显然0<6Z0

6、说明分组的均衡性越好•取定一个Q后，Go与。满足条件（3）的分组是一个均衡分组•条件（4）表示总巡视路线最短.此问题包含两方面：第一，对顶点分组；第二，在每组中求最佳推销员回路,即为单个推销员的最佳推销员问题.由于单个推销员的最佳推销员回路问题不存在多项式时间内的精确算法，故多个推销员的问题也不存在多项式时间内的精确算法•而图中节点数较多，为53个，我们只能去寻求一种较合理的划分准则，对图1进行粗步划分后，求出各部分近似最佳推销员回路的权,使得各部分满足均衡性条件（3）・再进步调整,图20点到任意点的最矩路图（单位：km）从O点出发去其他点，要使路程较小应尽量走O点到该点的最短路•

7、故用图论软件包求出O点到其余顶点的最短路，这些最短路构成一棵以（）为树根的树,将从O点出发的树枝称为干枝，见图2,从图中可以看出，从O点出发到其它点共有6条干枝，他们的名称分别为①，②，③，④，⑤，⑥.根据实际工作的经验及上述分析，在分组时应遵从以下准则：准则一：尽量使同一干枝及其分枝上的点分在同一组；准则二：应将相邻的干枝上的点分在同一组；准则三：尽量将长的干枝与短的干枝分在同一组.由上述分组准则，我们找到两种分组形式如下：分组一：（⑥，①），（②，③），（⑤，④）；分组二：（①，②），（③，④），（⑤，⑥）.显然分组一的方法极不均衡，故考虑分组二.对分组二中每组顶点的生成子图，

8、用算法一求出近似最优解及相应的巡视路线•使用算法一时，在每个子图所构造的完备图中，取一个尽量包含图2中树上的边的H圈作为其第2步输入的初始圈.分组二的近似解见表1.表1（单位：km）小组名称路线总路线长度路线的总长度IO-P-28-27-26-N-24-23-22-17-16-I-15-I-18-K-21-20-25-M-O191.1558.5IIO-2-5-6-L-19-J-11-G-13-14-H-12-F-10-F-9・E-7-E・8-4-D-3-C241.9I