1 约束最优路线的模拟退火解法 说明：以98年全国大学生数模竞赛中的B题（即“灾情巡视路线”）为例，介绍能解一类较广泛的约束最优路线问题的方法模拟退火法[1]
该法对“灾情巡视路线”这类有约束以及“（一般）旅行推销员”、“中国邮递员”等无约束组合优化问题均能求得较好的近似解，具有适用范围广和可拓展的优点
一、问题描述 对于最短路、最大流、中国邮递员、旅行推销员等最优路线问题，常采用各自不同的方法求解
若在这些问题中再加入一些约束条件，则原方法往往不再有效，如98年大学生数模竞赛中的B题就是如此
我们设计的方法较好地解决了这一问题
现以98年B题为例，介绍该法及其实现
下面为该题文字部分，并称其四问分别为问题1至问题4： 下图（略）为某县的乡（镇）、村公路网示意图，公路边的数字为该路段的公里数
今年夏天该县遭受水灾
为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视
巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线
１．若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线
２．假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里／小时
要在24小时内完成巡视，至少应分几组；给出这种分组下你认为最佳的巡视路线
３．在上述关于T，t和V的假定下，如果巡视人员足够多，完成巡视的最短时间是多少；给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路线
４．若巡视组数已定（如三组），要求尽快完成巡视，讨论T，t和V改变对最佳巡视路线的影响
二、问题分析及模型的建立 因为是分组巡视（不妨设分N 组），要直接确定一个组巡视哪些地点是困难的
由于将各组巡视的路线连接起来可看成一条N 次相继从县城出发又回到县城的路线，这样，多组巡视就化成了单组巡视
经分析，我们认为前3问及
