2008.8.20退火法灾情巡视路线灾情巡视最优路线模的拟退火解法1

《2008.8.20退火法灾情巡视路线灾情巡视最优路线模的拟退火解法1》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、灾情巡视最优路线模的拟退火解法一、问题描述对于最短路、最大流、中国邮递员、旅行推销员等最优路线问题，常采用各自不同的方法求解。若在这些问题中再加入一些约束条件，则原方法往往不再有效，如98年大学生数模竞赛中的B题就是如此。我们设计的方法较好地解决了这一问题。现以98年B题为例，介绍该法及其实现。下面为该题文字部分，并称其四问分别为问题1至问题4：下图（略）为某县的乡（镇）、村公路网示意图，公路边的数字为该路段的公里数。今年夏天该县遭受水灾。为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇

2、）、村巡视。巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线。１．若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。２．假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里／小时。要在24小时内完成巡视，至少应分几组；给出这种分组下你认为最佳的巡视路线。３．在上述关于T，t和V的假定下，如果巡视人员足够多，完成巡视的最短时间是多少；给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路线。４．若巡视组数已定（如三组），要求尽

3、快完成巡视，讨论T，t和V改变对最佳巡视路线的影响。二、问题分析及模型的建立因为是分组巡视（不妨设分N组），要直接确定一个组巡视哪些地点是困难的。由于将各组巡视的路线连接起来可看成一条N次相继从县城出发又回到县城的路线，这样，多组巡视就化成了单组巡视。经分析，我们认为前3问及第4问计算部分都是组合规划中的约束优化问题，均属以模型（I）为基础的约束最优路线模型。下面根据各问的要求，分别对4个问题进行具体讨论。对于问题1，如果选取总路程最短的所有巡视路线中最均衡的，一般这一路线仍会很不均衡。故除了要总路程短，

4、另需“均衡”提出一定的要求，即组间巡视路线的长度差不大于某给定值L。还有路线能够分成3次从县城O出发再回到O、各组经过地点的并集为所有顶点的集合只之约束。模型如下：(II)其中F为巡视总路程，N为要求的分组数（本问N=3），n是优化过程中路线的实际分组数，fmax和fmin分别为n组中最长和最短组的巡视路程，Pi为第i组巡视地点的集合，A是所有顶点的集合。约束条件(fmax-fmin)£L用来保证各组路程基本均衡，目标函数中加入l(fmax-fmin)是为了使各组的路程尽可能均衡，这是一个约束多目标规划。

5、权重l的取值应远小于目标函数中F的权系数1，否则会因离散问题函数值的跳跃现象而导致优化困难。这里，我们取l=1/L。对问题2和3，因在原图中不是任意两顶点间均有边，故在多组巡视时可能存在二组以上经过的公共点，从而使顶点赋权遇到如下困难：若先赋点权，则这些公共点的权会被重复计算；而若在优化过程中赋点权，则又有公共点究竟应该由哪次（组）巡视的问题。对此，我们采用Dijkstra法算出任意两点间的最短路程并除以速度V转化为时间，并用其作为两顶点间边的权构造一新图。第三个约束条件保证了每点至少经过一次，而这时若路

6、线中含除县城外的重复地点将至少增加1个小时（除县城为0外，其它点权为1或2小时），因而能保证优化结果中不出现县城以外的重复点。经分析，我们认为这两问同属分组数和路线双重优化问题，具体模型如下：(III)其中N、n、A、Pi与模型（II）相同，F为各组巡视时间之和，fmax为n组中时间最长组的巡视时间，TMAX是巡视允许的最长时间。对问题2，TMAX=24；对问题3，因人员足够多，故每个地点可由一组单独巡视，因此完成巡视的最短时间是这些单点巡视的最佳路线中花时间最长的组对应的巡视时间，其值TMAX由程序计算

7、确定。对最少分组数的优化，模型中没有体现，我们是通过主程序与辅助控制函数协同工作来实现该目的的，即在优化过程中，若路线调整发现最短与次短组的时间之和不大于TMAX，且满足约束，则记录该路线后返回，并由主程序将分组数减1后重新优化，如果重新优化找不到满足约束的可行路线，则认为找到了最优解；而若优化函数没有找到满足约束的可行路线，主程序则将分组数加1后进行下一轮优化。我们用m和M分别表示求解时尝试的最小和最大分组数，对问题2，取m=4，M=8，而对问题3，m=20，M=35。对于问题4，其最佳路线是指在分组数

8、已确定的情况下，巡视时间最长的组所对应的时间尽量短的路线。下面给出其模型，各参数的含义同模型（III），关于T、t和V对路线的影响，我们将在结果与分析部分给出。(IV)三、模型的求解(一）算法选择由以上分析可知，本题的所有问题都可视为“在一定约束下，从一点出发再回到该点的最优路线寻求问题”。如问题1可看成有约束的“一般旅行推销员”问题，但即使是无约束的“旅行推销员”问题，也尚未找到解这类问题最优解的多项式算法[3]，对本题n=