302006
受第一小题的启发，我们依然想到运用遗传算法进行求解。
选择、交叉、变异函数不变，适应度函数定义为两次游览的总交通费用的倒数，这样，用于交通的费用越少，适应度就越高，个体就越能遗传到下一代。
由于景区总数只有20个，所以，我们下面采用一种分类遗传的方法，这样可以使结果更精确也可以使计算效率提高。做法是：将20个城市分为两部分，第一个暑假考察N个景区，第二个暑假考察20-N个景区，N从3开始到17（如果N小于3的话会导致不满足约束条件，即出现一个暑假游览所花费的时间大于30天），同时考虑到乌鲁木齐是省会，很多游览天山、昌吉等景区的旅行线路都是以乌鲁木齐为出发点的，所以为更切合实际，在这里我们也要求第一个暑假从乌鲁木齐出发（当然，这不是必要条件，我们后面采用的方法即不需要满足此条件）。对每一个给定的N用一次遗传算法。最后将每个N对应的交通上花费的时间作比较，我们发现，N从7到13所花费的时间较其他更少一些，故，作
N?[7,13] 的柱状图如下：
（图5：景区数量安排与耗时关系图）
模型的结果与分析：
从上图的结果，我们可以看到：当两个月各访问10个景点，并且按照我们列出的顺序访问，路上时间最少，而路途耗时与交通费几乎成正比，从而交通费也最省。
我们给出一组最优线路： 7 8 6 5 4 9 10 1 3 2 第一个暑假 12 11 14 13 15 17 18 20 19 16 第二个暑假 最佳旅游路线设计
10
302006
遗传算法的效果和求解能力都能达到我们所期望的，但是对于这一问题固有的特性，我们也可以直接从图的角度来建立模型：
2.2 从图的角度直观求解
两次暑假遍历所有的景区，也即是将原来20个景区的连通图分割成两个子图，并找出两条互不重叠的旅游路线。针对问题的特殊性，我们分如下几步来处理问题：
第一步，不断地剪去图中所有度为1的顶点，即编号为：2、8、9、11、12、16、19的点（11是因为剪去12后它成为了度为1的顶点）。
因为我们参观这类景区的时候，进出必然沿同一条线路，花费在这些路上的时间是不可缩减的。所以，在我们的最节约时间方案中一定会包含这些路径，故寻找最短路径的时候可以暂时将其从图上去除。
第二步，我们将度为2的顶点去除，但保留原来的路，即编号为：1、4、6、15、17、18、20的点。
原因与第一步类似，因为对于这类顶点，一般来说，游览它们的时候，是从顶点的一条边进入而从另一条边离开，所以，通过这类顶点的路径也是确定的，对我们所需要寻找的最短路径不会产生影响，可以暂时将其从图上去除。
执行这两步之后，得到如下结果：
（图6：简化后的景点图）
最佳旅游路线设计
11
302006
我们发现，余下的顶点的度数都大于等于3。我们把被去除的顶点“附属于”某一个度数大于等于3的顶点，即如果我们到达某个顶点x，我们就要遍历它的“附属”点。
要分割原先的图，并找出不重叠的两条路线就要选择如何分割这些度数大于等于3的顶点。
模型的结果与分析：
由于数据量较少，我们用枚举的方式得出了五种较为合理的分组方式。 分组 情况一 情况二 情况三 情况四 情况五 Group1 1—10 1—12、14 1—8 1—8、11、12、14 1—6、9、10 Group2 11—20 13、15—20 9—20 9 10 13 15—20 7,8,11—20 情况一： Group1 2 3 1 7 8 6 5 4 10 9 Group2 12 11 14 13 15 17 18 20 19 16 情况二： Group1 2 1 3 9 10 4 5 6 7 8 14 11 12 Group2 13 15 17 18 20 19 16 情况三： Group1 2 3 1 8 7 6 5 4 Group2 12 11 14 13 10 9 15 17 18 20 19 16 情况四： Group1 2 1 3 4 5 6 7 8 14 11 12 Group2 9 10 13 15 17 18 20 19 16 情况五： Group1 2 1 3 5 6 4 10 9 Group2 12 11 14 7 8 13 15 17 18 20 19 16 由上面五组游览方案，我们分别计算它们的游览时间以及所需的路费，可以得到如下表的结果： 单位（小时） 情况一 情况二 情况三 情况四 情况五 Group1 57.37 107.03 45.17 91.89 53.41 Group2 103.3 64.15 126.51 76.95 130.75 总时间 160.7 171.18 171.68 168.84 184.16
价格（元） 一 二 三 四 五 Group1 292.3 573.4 220.1 511.8 270 Group2 694.3 465.9 845.7 541.6 841.3 Sum 986.6 1039.3 1065.8 1053.4 1111.3 由上表，我们发现，情况一中所消耗的时间最短，所需的费用相应也最少。因此，我们认为，安排两个月的旅游线路最佳的分配方式由情况一的分组给出，具体的线路图可以表示如下：
最佳旅游路线设计
12
302006
（图7：最佳线路安排图）
模型三：
3.1 简化的模型
由于考察分三组进行，故我们可以把整个西藏的景区分为三部分，三个考察小组各考察一个部分，设他们考察所花费的时间分别为T1、T2、T3，完成整个考察工作是指三个小组都完成各自的考察任务，所以，尽早的完成考察也就是使三个小组完成考察时间的最大值最小，即：minmax{T1、T2、T3}。
引言中，我们已经通过蚁群算法计算出环游全部景区时，所耗费在路上的时间约12天，现在分三组进行，花费在路上的时间更会小于12天。而现在各景区停留考察花费的时间是原先的4倍，即33?4?132天，两者相差一个数量级。故，我们先考虑一个简化的模型，即忽略路上所花费的时间。
现在，问题就转化为一个简单的规划问题：
min?max(?cjxij) i?1,2, 3ij?120最佳旅游路线设计
13
302006
?3??xij?1 j?1,2,...,20s..t?i?1 ?x?0,1 i?1,2,3;j?1,2,...,20?ij
x其中i?1,2,3表示三组考察的线路，j?1,2,...,20表示20个景区，则ij表示x?1 x?0第i组是否考察第j个景区，若考察，则ij，否则ij。而第一个约束条件表示每个景点当且仅当被一个小组考察。目标函数中的
cj表示考察每个景区所花
费的时间，
?cxj?120jij表示第i组考察队伍所花费的考察时间，三组队伍的最大值表
示花费的总时间，我们希望这个值尽可能的小。
模型的结果与分析：
下面我们用LINGO软件对问题进行求解，最优解中，矩阵
{xij}的值不唯一，
但是目标函数的值是唯一的，都是44，由于总共用于所有景区的考察时间为132天，很容易得出三个考察组在各景区所花费的时间都为44天。这与我们从直观上理解——尽量使三个小组的考察时间平均——是一致的。
简化的线性规划模型的好处是不言而喻的，但是也存在着一些不足，从解的分布来看，三个考察组遍历景点所花费时间都为44天的情况有许多种，尽管用于往返景区途中的时间远小于逗留在景区内的时间，但是为了区分各组解并求得更精确的解，我们需要将路程上的时间消耗列入考虑的范围之内。对于Lingo计算出的若干组最优解，我们将路程时间纳入考虑，对于其中最优的一组：
第一组 2 3 1 8 6 5 4 第二组 9 10 13 15 17 18 20 19 第三组 12 11 14 7 16 我们计算得，三组停留在景区与往返于景区路上所花费的总时间的最大值为1138.09小时（47.42天）
但是，由于最优值对应的分布较多，通过Lingo多次计算不考虑路程的最优解再将路程消耗加入，从而比较，这样的做法略显烦琐，也不能保证枚举到所有可能的结果。为此，我们再一次运用遗传算法。
3.2遗传算法的求解
这一问题遗传算法的选择、交叉、变异运算并没有实质的区别，但是适应度函数方面我们做了比较大的改进：
我们根据三个小组遍历的景区计算他们各自在景区逗留和往返景区间的时
最佳旅游路线设计
14