灾情巡视线路

本文旨在设计出合理的灾情巡视路线，使得巡视路线从县政府所在地出发，走遍各乡村后，又能回到县政府所在地，该问题属于分组旅行员推销问题。对于问题一我们先利用避圈法画出了最小生成树，然后依据最小生成树的枝干进行划分，分组时为我们要均衡考虑三组走的总路程尽量小和三组的均衡度较小，分组后我们根据分组组情况画出哈密顿圈经过多次比较选出其中最优的路径已知某县的乡（镇）、村公路网示意图（见附录一），公路边的数字为该路段的公里数。今年夏天该县遭受水灾。为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视。巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线