3.5 巡视路线的确定 17

3.6 巡视路线的优化 19

3.7 模型评价及改进 21 

小    结 . 22 

参考文献. 23 

致谢.. 24 

第一章    绪论 

1.1 研究背景及意义

自然灾害给人类造成了巨大的人员损失，因得不到救援而死亡的人数在灾后死亡 总人数中占了很大比例。造成这样的主要原因是巡视人员在巡视的过程中浪费了大量 的时间，从而错过了最佳救援时间。因此，灾情巡视路线的设计是很有必要的,它可 以在灾后为巡视提供科学有效的手段，使幸存者因救援不及而死亡的悲剧不再上演。 

灾情巡视路线的设计问题困扰人们很久。人们最早使用穷举法，但在受灾地域范 围较大时，计算时间指数级的增长是令人难以接受的，于是启发式算法应运而生。这 类算法能在可接受计算时间范围内找到的最好的路线，但不保证路线是否可行和最优。 随着计算复杂理论的逐渐完善，人们对最优解的认识有了改变，开始采用数学规划算 法和解空间松弛算法来设计路线。后来为了避免计算陷入局部最优以及计算效率的问 题，人们提出了一些新的思想和算法。如以群居性昆虫行为特性推导出的蚂蚁算法， 又如根据混沌现象 ,将混沌机制、启发式搜索方法、人工神经网络和模拟退火等算法 相结合,建立了更多优质高效的算法,来提高算法的计算效率和对全局最优点的获取 能力。

1.2 主要研究内容 

本次毕业设计主要研究灾情巡视的最佳路线设计问题，以受灾乡镇为例，对受灾 区域进行巡视和指挥救援工作，寻找从起点出发途经每个受灾乡镇再返回起点所需时 间最短的巡视路线。具体如下： 

1.如何分割网络图模型，能够保证分组的均衡性； 

2.如何在最短的时间完成巡视； 

3.如何设计使巡视路线总长度最短； 

4.如果各巡视小组驾车驶往各村庄的速度可以不同，如何安排行驶速度可以将巡 视人员平均分配； 

5.对不同的巡视要求设计不同的巡视路线。

第二章   模型建立 

2.1 问题重述 

某县发生自然灾害，领导决定率领有关部门到全县各村巡视开展救援工作。为了 救援工作的及时开展，决定将所有人员进行分组，负责相应区域的巡视工作。要求必 须将每村巡视一遍，最后返回起点汇报巡视情况，针对受灾程度安排救援工作。 2.2  问题分析 

上述问题要求从县政府出发，走遍各乡镇，然后再回到出发点，使路程最短或时 间最短。在公路网图中，各村被看作是图中的一个结点，两村之间的公路看作图中的 一条边，长度作为对应边的长度，这样公路图就转换为赋权图[1]。若我们想巡视路程 长度最短，就必须减少巡视路线中的重复点，所以尽量让巡视路线是一个回路。研究 图中是否存在一个圈恰好经过所有点一次就是图论中的哈密尔顿问题；但是若不存在 这样的回路，就必须考虑分组，让每个分组中存在这样的回路，而这些回路都经过起 点，这就类似于多旅行商问题[2]。 

2.3 条件假设 

1．全县各乡村的之间的道路路况良好。

2．各小组巡视一个村庄的时间即停留时间与巡视人数有关。

3．巡视小组可以经过村庄不巡视。

4．巡视人员驾车从一个村庄到另一个村庄的速度一样且车辆不发生故障。

5．起点不需要巡视直接出发即可。