图二
方案二 H划在第3组
图三
I方案一的求解结果（具体程序见附录一）
表一
分组 I组 路线 O--1--B--34--35--32—30--Q--28--27--24—23 --N--26--P--29--R--31—33--A--1--O O--M--25--20--L—19--J--18—J—13--14--H— 14—15—I--16--17--22--K--21—25--M-O O--2--5--6—7--E--11--G--12—F—10--F— 9—E--8--4--D--3—C--O 每组路程 200.10 216.6 184.70 均衡度 总路程 II组 III组 0.147 601.4 均衡度?=0.147?0.1均衡度不够好，于是我们对路线进行了一些调整，把H划在第III组，这种方法更加合理。 II方案二的求解结果
表二
分组 I组 II组 路线 O--1--B--34--35--32--30--Q--28--27--24--23— N--26--P--29--R--31--33--A--1--O O--M--25--20--L—19--J--18--J—13—14— 15--I--16--17--22--K—21—25—M--O O--2--5--6--7--E--11--G--12--H--12--F--10--F—9--E--8--4--D--3--C--O 每组 路程 200.10 196.8 205.10 均衡度 总路程 0.0405 602．0 III组 均衡度0.0405?0.1均衡度很好，路程S增加不大，故调整后的方案更优。 5.3结果分析
问题一中，我们建立双目标最优化模型，但是二者不能同时达到最小值，对于两者我们都要兼顾，方案二在路程增加不大情况下，均衡度较好，因而我们选择方案二。
6.问题二的解答
6.1模型的建立
6.1.1确定目标函数
在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时（不考虑O点），在不考虑在路上时间情况下满足
T?N?t?n?24（Z为组数） Z24?3-17?2-35=1小
3时每组只能行走35公里，显然不可能实现。考虑Z值取4，分为4组每组，在
24?4?17?2?35?6.75路上时间为小时，4组总共能行走的路程为
46.75?4?35?945公里大于问题一中求解的总路程，故Z=4是可能实现的。据此，
Z的最小取值为3，若分为3组，每组在路上的时间为
我们将原图分为4个子图。 目标函数：
?minS?(L1?L2?L3?L4)?(maxLi?maxLi) ?1?i?41?i?4?min??maxLi? 约束条件：
T?Ni?t?ni?Li?24?i?1,2,3,4? V6.2模型的求解
分组时要考虑到在乡和村中停留的时间和在路程上消耗的时间，使在近处寻访的组多访问几个村和乡，远处的组则尽量少访问些村庄和乡，从而使各组的总的消耗时间比较均衡。
1从O点开始分解○划分原则：○2分解的三个子图顶点数尽可能接近13个尽3量实每一个子图为连通图○○4尽量使每一个子图中与点O的最短路上的点在该
子图内，尽量使每个子图的点在子图内形成回路。据此，划分如下图所示
运用问题一中同样的算法，可以得到结果如下(具体程序见附录二)
表三
组数 I II III 每组路线 O--C--B--34—35—32--30--Q—29— R—31—33—A—1--O O--P--28--27--26-N—23—24—23—22— 17—16—17--K—21—25—M--O O--2—5--6-L—20—L--19—J--18--I— 15—14--H—14—13--J—19--L--6--5--2--0 O-2--3--D--7--E--11--G--12--F— 10—F--9--E--8--4--D--3--2--0 IV 每组路巡视村 每组时间 程 镇数 130.500 5个乡镇，21.73 8 个村 4 个乡镇157.900 22.51 10 个村 4个乡镇，23.60 196.000 9个村 4个乡镇，181.200 21.18 8 个村 6.3结果分析
问题二在问题一基础上加了停留时间及巡视时间限制，但算法一样。至少分为4组，才能在24小内完成巡视
7.问题三的解答
7.1模型的建立 7.1.1确定目标函数
问题3中假设巡视人员足够多，即分组数不限，甚至每个村镇都能安排一个巡视人员。那么，最短时间取决于最远那个村或镇。分析发现H是所有点中距离O最远的点，则有：
77.5?2?2?6.43h 35即在T=2，t=1,v=35的情况下，完成巡视最短时间为6.43小时
tH?设应分i组巡视，第i组巡视的乡(镇)数目Ni，巡视村的数目ni，巡视路程Li 目标函数：
L??min?max(T?Ni?t?ni?i)?
V??7.1.2确定约束条件
I每一组的巡视时间不能大于tH II每一个顶点都要访问到，不能遗漏
III分组数要尽可能少
IV均衡度不能大于我们规定上限
7.2模型的求解
寻找最优路径算法实现。利用图论软件求出每一点到O点最短路径，进而得到任意点返回O点的所需的最短时间，将此时间作为各点的权值；由于每一点都要访问到，所以每一点都要走到。任取一点，该点权值的两倍加上沿途访问的地点停留时间之和记为T'，在tH-T'的时间内，看与该点相连的各点中有没有可以访问的点，若有，则继续；没有，则返回。基于以上算法，借助图论软件编程得出结果如下表
表四
组号
1 O-1-B-C-0
访问路线
访问地点 所耗时间 (小时) 1 B C 5.98