B题 灾情巡视路线

    下图为某县的乡（镇）、村公路网示意图，公路边的数字为该路段的公里数。

今年夏天该县遭受水灾。为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视。巡视路线指从县所在地出发，走遍各乡（镇）、村，又回到县所在地的路线。

1、若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。

2、假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时。要在24小时内完成巡视，至少应分几组；给出这种分组下你认为最佳的巡视路线。

3、在上述关于T，t和V的假定下，如果巡视人员足够多，完成巡视的最短时间是多少；给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路线。

4、若巡视组数已定（如三组）。要求尽快完成巡视，讨论T,t和V改变对最佳巡视路线的影响。

B题  （灾情巡视路线）参考解答

一、问题的分析

    本题是一类图上点的行遍性问题，即要用若干条闭链复盖图上所有的顶点，并使某些指标达到最优。分组巡视的最短路是多旅行商问题，旅行商问题有两种形式：过每点一次且仅一次；过每点至少一次。理论上，两点间距离满足三角不等式时，两种形式等价。否则应作修改将后者化为前者，才能用旅行商问题的典型算法，实际上本题只需注意个别处即可。

    多旅行商问题（结合本题）可用以下方法化为单旅行商问题：

1）就本题的具体情况直观地分区，如东、北、南三区，或东、北、中、南四区。

2）将0点换成o1,o2,o3三点，它们之间不相连，但都与o点的邻点相连，求该图的最短闭链，再将o1,o2,o3三点合并即可。

3）直接求一条最短闭链，再割成三条链，并与o连成三条闭链。

    当然，为了达到均衡的目的，都应作局部调整。

二、问题的求解

1）分成三组巡视的最佳路线

    对单旅行商问题可以用多种方法求解，如分支定界、最小插入、对换调扰、最近邻点，以及神经网络、模拟退火、遗传算法等。

记三组巡视路线长度从小到大分别为c1,c2,c3，最佳路线应使min(c1,c2,c3)及min(c3-c1),并以前者为主。一种方案为：

0  1  A  33  31  R  29  Q  30  32   35  34  B  1  0  C1=125.9km

0 M  25  20  L  19  J  18  I  15  I  16  17  22  K  23  13  24  N  26  27  28  P  0   C 2=212.2km

1C  3  D  4  8  E  9  F  10  F  12  H  14  13  G  11  E  7  6  5  2  0

C3=215.9km

总长554.0km,均衡性C3-C1=90km

1)24小时内完成巡视的最佳路线

    经简单计算即知，需分4组巡视。应在1）的基础上考虑停留时间来分组，使各组巡视时间尽量均衡。一种方案为：（括号内为不停留的点）

1C  3  D  4  8  E  9  F  10  （F  9  E）  7  6  5  2  0     21.54小时

1（2  5  6）  L  19  J  13  14  H  12  G  11 （J  19） 20  25  M 0 22.03小时

0  (P) 28  27  24  23  22  17  16  I  15  (I)  18   k  21  (25)  N  26  (P)  0  21.14小时

11  A  33  31  R  29  Q  30  32  35  34  B  1  0  P  0   22.14小时

4组巡视时间均在22小时左右,相差仅0.23小时. 

2)最短时间完成巡视的最佳路线

     最短完成巡视时间由0到H的巡视时间决定(H是0到各点最短路中的最长者),为6.43小时,应在此约束下考虑对全部顶点的最小覆盖(由于T,t的不同,须作分析调整),能够得到22组的巡视路线.

3)T,t,V的讨论

T,t,V增大会使巡视路线更偏重顶点个数的均衡,而它们的减小会更偏重巡视路线的长度.在此定性分析的基础上,可以作一些定量计算。下载本文