word关于灾情巡视路线的模型摘 要 本文将求最优巡视路线间题转化为图论中求最优推销员回路哈米尔顿回路的问题,并用近似算法去寻求近似最优解。对赋权图中的路径分组问题定义了均衡度用以衡量分组的均衡性。对问题1和问题2先定出几个分的准如此进展初步分组,并用近似算法求每一组的近似最优推销员回路,再根据均衡度进展微调,得到较优的均衡分组和每组的近似最优推销员回路。对问题1，运用求任意两点间最短路的Floyd算法,得出总路程较短且各组尽可能均衡的路线,各组的巡视路程分别为216.4公里,191.1公里,192.3公里,总路程599.8公里。对问题2,证明了应至少分为4组,并求出了分为4组时各组的较优巡视路线,各组的巡视时间分别为22.74小时,22.59小时,21.69小时,22.54小时。对问题3,求出完成巡视的最短时间为6.43小时,并用较为合理的分组的准如此,分成22个组 对问题4，研究了在不影响分组的均衡条件下, T,t,V的允许变化围,并得出了这三个变量的关系式,并由此对分三个组的情况进展了具体讨论。关键词：最优推销员回路问题 哈米尔顿回路 赋权图 近似算法 均衡度一、问题重述1998年夏天某县遭受水灾。为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各17个乡镇、35个村巡视。巡视路线指从县政府所在地出发，走遍各乡镇、村，又回到县政府所在地的路线。(1) 假如分三组路巡视，试设计总路程最短且各组尽可能均衡的巡视路线。 (2) 假定巡视人员在各乡镇停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时。要在24小时完成巡视，至少应分几组；给出这种分组下你认为最优的巡视路线。 (3) 在上述关于T , t和V的假定下，如果巡视人员足够多，完成巡视的最短时间是多少；给出在这种最短时间完成巡视的要求下，你认为最优的巡视路线。 (4) 假如巡视组数已定(如三组，要求尽快完成巡视，讨论T，t和V改变对最优巡视路线的影响。 二、问题分析此题给出了某县的公路网络图，要求的是在不同的条件下，灾情巡视的最分组方案和路线.将每个乡镇或村看作一个图的顶点，各乡镇、村之间的公路看作此图对应顶点间的边，各条公路的长度或行驶时间看作对应边上的权，所给公路网就转化为加权网络图，问题就转化图论中一类称之为旅行售货员问题，即在给定的加权网络图中寻找从给定点O出发，行遍所有顶点至少一次再回到点O，使得总权路程或时间最小. 此题是旅行售货员问题的延伸多旅行售货员问题.此题所求的分组巡视的最优路线，也就是m条经过同一点并覆盖所有其他顶点又使边权之和达到最小的闭链闭迹.如第一问是三个旅行售货员问题，第二问是四个旅行售货员问题. 众所周知，旅行售货员问题属于NP完全问题，即求解没有多项式时间算法.显然本问题更应属于NP完全问题. 有鉴于此，一定要针对问题的实际特点寻找简便方法，想找到解决此类问题的一般方法是不现实的，对于规模较大的问题可使用近似算法来求得近似最优解.三、问题假设1. 汽车在路上的速度总是一定，不会出现抛锚等现象；忽略天气、故障等因素的影响。2. 巡视当中，在每个乡镇、村的停留时间一定，不会出现特殊情况而延误时间；3. 每个小组的汽车行驶速度完全一样；4. 分组后，各小组只能走自己区的路，不能走其他小组的路，除公共路外。5. 情况不受灾情影响，即车辆在所有公路上所有公路上都可以顺利通过。四、符号说明符号符号说明任意两点，间的间距各点的停留时间，即点权汽车行驶速度从任意点至点的时间，如此五、模型建立与求解公路网图中，每个乡镇或村看作图中的一个节点，各乡镇、村之间的公路看作图中对应节点间的边，各条公路的长度或行驶时间看作对应边上的权，所给公路网就转化为加权网络图，问题就转化为在给定的加权网络图中寻找从给定点O出发，行遍所有顶点至少一次再回到O点，使得总权路程或时间最小，此即最优推销员回路问题。在加权图G中求最优推销员回路问题是NP完全问题，我们采用一种近似算法求出该问题的一个近似最优解，来代替最优解，算法如下：算法一 求加权图GV，E的最优推销员回路的近似算法：1 用图论软件包求出G中任意两个顶点间的最短路，构造出完备图， ；2 输入图的一个初始H圈；3 用对角线完全算法见23产生一个初始H圈；4 随机搜索出中假如干个H圈，例如2000个；5 对第2、3、4步所得的每个H圈，用二边逐次修正法进展优化，得到近似最优H圈；6 在第5步求出的所有H圈中，找出权最小的一个，此即要找的最优H圈的近似解.由于二边逐次修正法的结果与初始圈有关，故本算法第2、3、4步分别用三种方法产生初始圈，以保证能得到较优的计算结果。问题一：，将G分成n个生成子图，使得1顶点 i=1，2，3n23，其中为的导出子图中的最优推销员回路，为的权，i，j=1，2，3n4 定义 称为该分组的实际均衡度。为最大容许均衡度。 显然，后，与满足条件3的分组是一个均衡分组.条件4表示总巡视路线最短。此问题包含两方面：第一、对顶点分组；第二、在每组中求最优推销员回路，即为单个推销员的最优推销员问题。由于单个推销员的最优推销员回路问题不存在多项式时间的准确算法，故多个推销员的问题也不存在多项式时间的准确算法.而图中节点数较多，为53个，我们只能去寻求一种较合理的划分准如此，对图19进展粗步划分后，求出各局部的近似最优推销员回路的权，再进一步进展调整，使得各局部满足均衡性条件3。图11-10 O点到任意点的最短路图单位：公里 从O点出发去其它点，要使路程较小应尽量走O点到该点的最短路.故用图论软件包求出O点到其余顶点的最短路，这些最短路构成一棵O为树根的树，将从O点出发的树枝称为干枝，见图0，从图中可以看出，从O点出发到其它点共有6条干枝，它们的名称分别为，。根据实际工作的经验与上述分析，在分组时应遵从以下准如此：准如此一：尽量使同一干枝上与其分枝上的点分在同一组；准如此二：应将相邻的干枝上的点分在同一组；准如此三：尽量将长的干枝与短的干枝分在同一组.由上述分组准如此，我们找到两种分组形式如下：分组一：，分组二：，显然分组一的方法极不均衡，故考虑分组二。对分组二中每组顶点的生成子图，用算法一求出近似最优解与相应的巡视路线.使用算法一时，在每个子图所构造的完备图中，取一个尽量包含图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-OIIO-2-5-6-L-19-J-11-G-13-14-H-12-F-10-F-9-E-7-E-8-4-D-3-CIIIO-R-29-Q-30-32-31-33-35-34-A-B-1-O因为该分组的均衡度=54.2%所以此分法的均衡性很差。为改善均衡性，将第组中的顶点C，2，3，D，4分给第组顶点2为这两组的公共点，重新分组后的近似最优解见表2。 表2单位：公里编号路 线 路线 长度路线总长度IOP282726N2423221716I15I18K212025MOIIO2567E8E9F10F12H1413G11J19L652OIIIOR29Q303231333534A1BC3D4D32O因该分组的均衡度11.69%所以这种分法的均衡性较好。问题二由于T=2小时，t=1小时，V=35公里/小时，需访问的乡镇共有17个，村共有35个.计算出在乡镇与村的总停留时间为172+35=69小时，要在24小时完成巡回，假如不考虑行走时间，有: (i为分的组数).得i最小为4，故至少要分4组。 由于该网络的乡镇、村分布较为均匀，故有可能找出停留时间尽量均衡的分组，当分4组时各组停留时间大约为小时，假如平均分配给4个组，每个组约需=4.25小时6.75小时，故分成4组是可能办到的。现在尝试将顶点分为4组.分组的原如此：除遵从前面准如此一、二、三外，还应遵从以下准如此：准如此四：尽量使各组的停留时间相等。用上述原如此在图11-10上将图分为4组，同时计算各组的停留时间,然后用算法一算出各组的近似最优推销员巡回，得出路线长度与行走时间，从而得出完成巡视的近似最优时间.用算法一计算时，初始圈的输入与分三组时同样处理。这4组的近似最优解见表3： 表3路程单位：公里；时间单位：小时组名路 线路线总长度停留时间行走时间完成巡视的总时间IO2567E8E11G12H12F10F9E7652O 17IIOR29Q30Q282726N242322171617K2223N26PO16IIIOM252021K18I151413J19L6MO18IVORA3331323534B1C3D4D32O16618上表中符号说明：加有底纹的表示前面经过并停留过，此次只经过不需停留；加框的表示此点只经过不停留。该分组实际均衡度=4.62%可以看出，表3分组的均衡度很好，且完全满足24小时完成巡视的要求。问题三我们发现从O点巡视H点的最短时间是所有最短时间中最长的，其距离为77.5公里。其时间为 因此，T=2小时，t=1小时，V=35公里/小时。假如巡视人员足够多，完成巡视的最短时间为6.43小时。 在最短时间限定一下，完成巡视的最优路线应满足如下条件：（1） 每个组巡视的总时间不能超过最短时间；（2） 所有点都必须访问到，不能漏点；（3） 所需巡视组数要尽量少；在寻求最优路线时，从距离O点较远的一些点如点12、10、15、22开始搜索比拟容易，因为到这些点的路线比拟少。具体方法如下：第一步：依据图1算出从O点到每一个点的最短距离;第二步：找出其中最大的一个，算出从O点沿最短的路巡视的时间，并求出;第三步：假如如此这一组只能访问这一点；假如如此在余下的点找到距离O点最远的点，根据条件看这一组能否巡视这一点；第四步：假如能巡视，如此算出，转到第三步；第五步：假如不能如此依次判断次