摘要 ：我国幅员辽阔，气候、地形复杂，自然灾害频发。为了在最短时间内赶赴到受灾 地区进行救援和搜救工作，必须对救援搜寻的路线进行分析和设计，将救援的时间和 代价缩小到最小。由于线路图可以看作赋权图，问题可转化为多旅行商问题，即有多 个旅行商人从同一点出发要拜访 n 个城市，每个城市只能拜访一次，最后每个旅行商 人回到起点，求如何设计路线使得总行程最小的问题。

本文主要研究灾情巡视的最佳路线设计问题，首先将交通图转换为赋权连通图， 并用两种最短路算法算出各村庄到巡视起点的最短距离及路线；其次用破圈法生成赋 权连通图的最小生成树；用最小生成树分解原则，将其分解为若干个子树以确定巡视 组数和区域，添加必要的连线从而确定巡视路线；接着用寻找最优回路法则来改造巡 视路线达到巡视距离最小的目的，最后对巡视路线进行分析优化，讨论不同情况下的 最优路线。 

关键词：最短路算法；破圈法；最优回路法则 

Abstract：China is a vast country with complex climate, terrain and natural disasters. In order to rush to the affected areas in the shortest time to rescue and search, people must analyze and design the rescue route to reduce the time and cost of the rescue to a minimum. As the road map can be seen as a weighted graph, the problem can be translated into a multi-traveling salesman problem. That there are multiple traveling salesmen from the same point to  visit n cities, each city can only be visited once, and finally each merchants travel back to the starting point, and how to design to make the minimum total travel route.

In this paper, we study the best route design problem of disaster patrol. Firstly, we translate the traffic map into the weighted connectivity map, and use the two shortest path algorithm to calculate the shortest distance and route of the village to the starting point of the tour. Secondly, the minimum spanning tree of the graph is decomposed into a number of subtrees to determine the number of patrol groups and regions, and the necessary routes are added to determine the patrol route. Thirdly, we use the search for the best circuit to modify the patrol route to achieve the purpose of the smallest patrol distance. Finally, the tour route is analyzed and optimized to discuss the optimal route under different circumstances.

Keywords: Shortest path algorithm; Breaking circle method; Optimal loop rule

目    录 

第一章    绪论 1

1.1 研究背景及意义 1

1.2 主要研究内容 2

第二章    模型建立 3

2.1 问题重述 3

2.2 问题分析 3

2.3 条件假设 3

2.4 模型的符号说明 4

2.5 模型建立 4

第三章  模型求解 5

3.1 最短路径算法 5

3.1.1 Dijkstra 算法. 5 

3.1.2 Floyd 算法  7 

3.2 破圈法和避圈法 10

3.2.1 破圈法 . 10 

3.2.2 避圈法 . 10 

3.2.3 避圈法和破圈法的比较  11 

3.3 最小生成树分解原则 12

3.4 寻找最优回路的有效优化规则 15

3.4.1 扩环策略.. 15 

3.4.2 增环策略.. 15 

3.4.3 换枝策略.. 16