1998年数学建模灾情巡视路线的设计

1基于多旅行商的最优灾情巡视路线设计摘要本文将求最佳灾情巡视路线问题转化为图论中求最佳旅行商回路的问题，并用近似算法去寻求近似最优解.针对第一问，首先从题目给出图中人工提取出部分点间残缺的最短路权矩阵，利用Floyd算法将权矩阵完备化，在原图中标记各点间的最短路径，得到有六条主干的公路图.其次依据三项分类原则将公路主干图分成三组，得到两种分类.再比较两种分类的均衡性，将公路分为（①，②），（③，④），（⑤，⑥）.再用模拟退火算法求出各组中的最短路径.计算得出最短路径的均衡度为56.62%，大于标准0.2.于是对分类结果进行修正，将第一组的几个点分到第三组.修正后得到最短路径的均衡度为8.45%，得到近似最优巡视路线.针对第二问，首先将第一问中的权矩阵处理得到最少花费时间矩阵，由题目要求建立不等式，求解出需将公路分为四组.故在第一问的分类方法中增加时间考量，将公路分为四组.再用模拟退火算法求出各组最少花费时间路径，得到此时的均衡度为4.62%.得到近似最优巡视路线.针对第三问，有题设条件建立不等式，得各组最短花费时间不超过6.43h.故采用一种最短路线调整算法求出在最短时间6.43小时内,用22组就可以完成巡视.针对第四问，研究了在不影响分组的均衡条件下，,,TtV的允许变化范围,并得出了这三个变量的关系式，并由此对分三个组的情况进行了具体讨论.关键词：旅行商问题Floyd模拟退火均衡度2一、问题重述已知某县遭受水灾.为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视.下图为此县的乡（镇）、村公路网示意图，公路边的数字为该路段的公里数.要求巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线.1.若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线.2.假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时.要在24小时内完成巡视，至少应分几组；给出这种分组下你认为最佳的巡视路线.3.在上述关于T,t和V的假定下，如果巡视人员足够多，完成巡视的最短时间是多少；给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路线.4.若巡视组数已定（比如三组），要求尽快完成巡视，讨论T，t和V改变对最佳巡视路线的影响.图1公路网示意图二、问题分析如果巡视人员只分一组，巡视路线是指巡视人员从县政府O出发，沿乡村公路遍历各乡镇、村，最后回到县政府.把该问题抽象为图论的赋权连通图问题，3即有一赋权无向连通图(,)GVE,OV；两村之间公路的长度，即为该示向图的边权()e.寻找一条最佳的路线,即在图(,)GVE中，找到一条包含的回路，它至少经过所有的顶点E一次，使总路程（总时间）最小，这是一个一般推销员问题(generalsalesmanproblem).如果巡视人员分成若干组,每组考察一部分区域,且所有乡村都考察到.如果能把这些乡村分块，即图(,)GVE中把图分为若干个连通的子图G，每个子图iG中寻找一条包含O的回路iL，则对每个子图iG而言，化为一般推销员问题.完成巡视的时间应是各组巡视时间中最长的时间，故为使巡视效率高，应尽量使各组巡视时间接近，反映在图G分块时应尽量均衡.三、符号说明所有用到符号如下：ijw公路图的权矩阵ijx公路图的邻接矩阵kC某分组下的第k组路径长度C总路程T在各个乡镇的停留时间t在各个村的停留时间V汽车行驶的平均速度km第k组巡视乡镇个数kn第k组巡视村个数Kh第k组花费时间ijM第i点到第j点花费时间四、模型假设所有模型基于以下假设：41)汽车在路上的速度总是一定，不会出现抛锚等现象；2)巡视当中，在每个乡镇、村的停留时间一定，不会出现特殊情况而延误时间；3)每个小组的汽车行驶速度完全一样；4)分组后，各小组只能走自己区内的路，不能走其他小组的路（除公共路外）.五、模型建立与求解5.1问题一的模型第一问中，要在返回O点的条件下，找到三组路径，使得总路径最短且三组划分均衡.因此我们考虑先以三组尽可能均衡为目标，划分出各组，把问题转化为三个旅行商问题.之后求出各分组的最短路径.具体实施过程如下：首先我们对数据进行了处理，从图中人工提取出各邻接点之间的权及较近两点之间的最短路的权，得到图1的残缺权矩阵（见附录）.之后利用Floyd算法求出缺省值，得到图一的完备权矩阵（部分如下表）.表1完备权矩阵局部表在用Flody算法求缺省值时，我们能得到O点到其他点的最短路，在原图中进行标注，去掉没有标注的路，得到如下图：5图2O点到各点公路图易见，从O点出发到其它点共有6条干枝，我们对其进行标注：图3公路主干图然后我们对图三中的公路进行分类，将其分为三组，分组依据如下：1）尽量使同一干枝上及其分枝上的点分在同一组.2）应将相邻的干枝上的点分在同一组.3）尽量将长的干枝与短的干枝分在同一组.由上述分组准则，我们找到两种分组形式如下：分组1:（⑥，①），（②，③），（⑤，④）6分组2:（①，②），（③，④），（⑤，⑥）显然分组1极不均衡，我们考虑分组2.这样我们就把多旅行商问题转化为了单旅行商问题.对分组2中的各组建立模型如下：1111min1..10,1nnkijijijnijinijjijCxwxstxx用模拟退火算法求解得分组2的路线如下：小组名称路线总路线长度分组2总长度第一组（①，②）O-2-5-6-L-19-J-11-G-13-14-H-12-F-10-9-E-7-E-8-4-D-3-C-O228.8511.25第二组（③，④）O-P-28-27-26-N-24-23-22-17-16-I-15-I-18-K-21-20-25-M-O183.2第三组（⑤，⑥）0-R-29-Q-30-32-31-33-35-34-A-B-1-O99.25表2分组二最短路线表引入均衡度指标：maxminmaxkkkCCC，规定0.2分组均衡.计算得分组二的均衡度为131228.899.250.5662228.8CCC，所以此分法的均衡性很差.为改善均衡性，将第一组中的顶点C,2,3,D,4分给第三组（顶点2为这两组的公共点），重新分分组后的近似最优解如下：小组名称路线总路线长度分组2总长度第一组（①，②）O-2-5-6-7-E-8-E-9-F-10-F-12-H-14-13-G-11-J-19-L-6-5-2-O176.7552.97第二组（③，④）O-P-28-27-26-N-24-23-22-17-16-I-15-I-18-K-21-20-25-M-O183.2第三组（⑤，⑥）0-R-29-Q-30-32-31-33-35-34-A-1-B-C-3-D-4-D-3-2-O193表三分组二修正最短路线表算得该分组的均衡度为313193176.70.0845193CCC，故该方法均衡度很好.巡视路线图如下：图4问题一路线图5.2问题二的模型问题二是在问题一的基础上加了时间考量.故首先由时间限制对图二进行分组，这就将问题二转化成了问题一的单旅行商问题.具体分组过程如下：由于2Th，1th，35/Vkmh，需访问的乡镇共有17个，村共有35个.计算出在乡（镇）及村的总停留时间为17*235*69hhh，要在24h内完成巡回，加上行走时间得不等式:6924ChhmV.得m最小为4，故至少要分4组.现在尝试将顶点分为4组.分组的原则：除遵从前面依据1)、2)、3)外，还应遵从以下准则：4)尽量使各组的停留时间相等.8用上述原则在图2上将图分为4组，得到四组分别为：（⑥，①），（②），（③），（⑤，④）.这样就将多旅行商问题转化为单旅行商问题，要求总花费时间最少，即要各组花费时间最少，由此我们建立了如下模型，对各组分别进行求解.41min1..10,1kknijinijjijhxstxx其中，21kkkkChmnV.用模拟退火算法求解这4组的近似最优解见下表.组名路线路线总长度停留时间行走时间完成巡视的总时间IO—2—5—6—7—E—8—E—11—G—12—H—12—F—10—F—9—E—7—6—5—2—O195.8175.5922.59IIO—R—29—Q—30—Q—28—27—26—N—24—23—22—17—16—17—K—22—23—N—26—P—O199.2165.6921.69IIIO—M—25—20—21—K—18—I—15—14—13—J—19—L—6—M—O159.1184.5422.54IVO—R—A—33—31—32—35—34—B—1—C—3—D—4—D—3—2—O166184.7422.74表4最少耗时路径表该分组实际均衡度22.7421.690.046222.74.可以看出，表3分组的均衡度很好，且完全满足24h完成巡视的要求，不需要再进行修正.巡视路线图如下：9图5问题二路线图5.3问题三的求解问题三没有人员限制，要求出耗时最短路线.从O点巡视H点的最短时间是所有最短时间中最长的,其距离为77.5公里,算出时间为：77.5226.4335Ht因此，2Th,1th，35/Vkmh时，若巡视人员足够多，完成巡视的最短时间为6.43小时.在最短时问的限定下,完成巡视的最优路线应满足如下条件1)每个组巡视的总时间不能超过最短时问小时6.43Ht；2)所有的点都必须访问到，不能漏点；3)所需巡视组数要尽量少；在寻求最优路线时，从距离O点较远的一些点开始搜索比较容易,因为到这些点的路线比较少.具体方法如下:第一步依据图2算出从O点到每一个点的最短距离；第二步找出其中最大的一个，算出从O点沿最短路巡视所需的时间it，并求Hittt；第三步若1t，则这一组只能访问这一点.若1t，则在余下的点中找到10距离O点最远的点，根据条件看这一组能否巡视这一点；第四步若能巡视则算出t，并转到第三步；第五步若不能,则依次判断次远点、第三远点…,满足总巡视时间不超过Ht，就让这组巡视这一点，直到1t，然后再从第二步开始.通过以上的力法,最后我们找到的最优解是22个组.如下表：编号巡视路径停留地点所需时间时间差1O-H-OH6.4302O-2-5-6-L-19-J-13-14-13-J-19-L-6-5-2-O13、146.150.283O-M-25-21-K-18-I-15-I-16-17-K-21-25-M-O15、166.310.124O-2-5-6-7-E-9-F-12-G-11-E-7-6-5-2-O12、115.940.495O-2-5-6-7-E-8-E-9-F-10-F-9-E-7-6-5-2-O8、106.220.216O-2-5-6-7-E-11-G-11-E-7-6-5-2-OG5.580.857O-2-5-6-7-E-9-F-9-E-7-6-5-2-O9、F6.140.298O-2-5-6-L-19-J-18-K-21-25-M-OJ、186.290.149O-M-25-21-K-18-I-18-K-21-25-M-OI5.490.9410O-M-25-21-K-17-22-23-N-26-P-O17、22、236.120.3111O-2-5-6-L-19-L-6-5-2-OL、195.640.7912O-M-25-20-21-23-24-N-26-P-O20、21、246.100.3313O-M-25-21-K-21-25-M-O25、K5.500.9314O-2-5-6-7-E-7-6-5-2-O6、7、E6.380.0515O-R-31-32-35-34-A-1-O31、32、35、346.320.1116O-R-29-Q-30-Q-28-P-OQ、30、286.110.3217O-P-26-27-26-N-26-P-O26、27、N6.230.201118O-2-3-D-4-D-3-2-O3、D、45.990.4419O-1-A-