建模案例：最佳灾情巡视路线
这里介绍 1998 年全国大学生数学模型竞赛 B 题中的两个问题.
一、问 题
今年夏天某县遭受水灾.为考察灾情、组织自救，县领导决定，带领有关部
门负责人到全县各乡（镇）、村巡视.巡视路线指从县政府所在地出发，走遍各
乡（镇）、村，又回到县政府所在地的路线.
1． 若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的路线.
2． 假定巡视人员在各乡（镇）停留时间 T=2h，在各村停留时间 t=1h，汽
车行驶速度 V=35km/h.要在 24h 内完成巡视，至少应分几组；给出这种分组下
最佳的巡视路线.
乡镇、村的公路网示意图见图 1.
图 1
二、 假 设
1．汽车在路上的速度总是一定，不会出现抛锚等现象；
2．巡视当中，在每个乡镇、村的停留时间一定，不会出现特殊情况而延误时间；
3．每个小组的汽车行驶速度完全一样；
4．分组后，各小组只能走自己区内的路，不能走其他小组的路（除公共路外）.
三、模 型 的 建 立 与 求 解
将公路网图中，每个乡（镇）或村看作图中的一个节点，各乡（镇）、村
之间的公路看作图中对应节点间的边，各条公路的长度（或行驶时间）看作对
