灾情巡视路线模型.doc

灾情巡视路线模型
摘要
本文研究的是考察灾情最佳巡视线路设计的问题，属于多旅行商问题，为此我们建立了网络图模型。利用最小生成树图形和最短路树图形相结合，通过分析、计算比较得出最优解。

对于问题一，我们建立赋权网络图。利用matlab编程得到此网络图的最小生成树图和最短路径树图，以两图相重合的部分作为分区的界限，将整个网络图分为三个分区。以总路程最短和均衡度最小作为目标函数建立多目标规划模型，利用哈密顿算法编写matlab程序求得各组最优巡回路线(见附表1)。

对于问题二，基于对问题一结果的分析，发现分三组的情况下，不能满足题目要求。因此我们首先考虑分四组的情况。在分三组的基础上根据分组原则将图大致划分为4各子图。同样以巡视路程最短和时间均衡度最小为目标函数，各巡视时间小于24小时作为约束条件建立多目标规划模型。利用哈密顿算法编程求得各组最佳巡视路线及巡视时间（见附表2）。

对于问题三，在巡视人员足够多的情况下，巡视距离点最远的点所用的时间为最短时间，根据最短路径树，从远到近，依次巡视各村镇，在所用时间不大于最短时间的前提下，各组尽可能多的巡视几个村镇，进行分组确立巡视点，并对已巡视过的点进行逐个剔除。通过人工记录，得出分组情况及巡视路线（见附表3），最短时间为6.4286小时。

对于问题四，在组数固定时，则各组的最短路径就已确定，、、改变影响的只是整个巡视时间。我们利用matlab编程画图得到、、与巡视时间的关系曲线。观察曲线发现：①当速度较小时，的变化对巡视时间的影响较大；②停留时间与巡视时间呈线性关系，无论取何值，对巡视时间影响都较大。此两种情况下都需适当调整分组。

关键词 最小生成树 最短路径树 赋权网络图 哈密顿算法

一、 问题重述
1.1背景分析：
今年夏天该县遭受水灾。为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视。巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线。
1.2需要解决的问题：
1）若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。
2）假定巡视人员在各乡（镇）停留时间T=2小时，在各村停留时间t=1小时，汽车行驶速度V=35公里/小时。要在24小时内完成巡视，至少应分几组；给出这种分组下你认为最佳的巡视路线。
3）在上述关于T , t和V的假定下，如果巡视人员足够多，完成巡视的最短时间是多少；给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路线。
4）若巡视组数已定(如三组），要求尽快完成巡视，讨论T，t和V改变对最佳巡视路线的影响。

二、 模型假设
2.1假设地面情况一切正常，不会影响汽车行驶速度；
2.2假设第二次经过的乡镇，不计算停留时间；
2.3对于同一乡镇，如果某一小组停留过，其他小组经过时不计算停留时间；
2.4假设经过邻县村不做任何停留；
2.5假设县镇府所在地灾情不派小组人员巡视。

三、 符号说明

第个小组所走路程

衡量均衡度（越小，均衡度越好；反之，均衡度越差）

巡视一个乡（镇）所花时间

巡视一个村所花时间

汽车的行驶速度

第个小组巡视所用时间

最短路径树中从O点出发到所有点距离中的最大距离

最短路径树中点距出发点的距离

完成所有巡视所用的最短时间

巡视完所规定的点外的剩余时间

小组巡视乡镇的个数

小组巡视村得个数

四、 问题分析
本文研究的是考察灾情最佳巡视线路设计的问题，准确合理的路线设计对灾情巡视救治起着重要作用。为很好的解决此问题，为此我们建立了网络图模型。
对于问题一，题目要求在分三组巡视的情况下，使总路程最短且各小组所走路程均衡。先考虑分区，我们将得出的最小生成树图形和最短路树图形，进行比较并找出其公共部分。分组要求尽量不破坏最短生成树和最小生成树，所以我们以公共部分为界限，将此网络图分为三组。为使每小组所走路程均衡，我们引入了均衡度。它表示最大路程和最小路程的差值与最大路程的比值。越小，表示均衡度越好。以总路程最短和均衡度最小作为目标函数建立多目标规划模型，利用哈密顿原理得出各组的巡回路线，并对其分析修正求得各组最优巡回路线。

对于问题二，要求在24小时内完成所有巡视。 通过第一问的结果，求得在分三组的情况下所用的平均时间大于24小时，所以我们先考虑分四组。我们的分组原则为：1、每子区域所分得的点近似相等；2、尽量使每一个子区域连通；3、使每一个子区域中与点O的最短路上的点在该区域内。根据以上分组原则将整个图大致划分为四个子图，同样利用哈密顿算法求得在相对均衡的情况每个小组的最短路径和所需时间。如果部分时间大于24小时，则调整分组方式；若所有时间均大于24小时再考虑多加一组。直到找到相对均衡条件下的最佳路线。

对于问题三，考虑在人员足够多的情况下，求出最短的巡视时间。假设一个小组只巡视一个点的情况下，则去巡视离点最远的点所花时间最长。我们以巡视小组中所耗时间最长的小组所用时间作为这次整个巡视的最短时间。要使这次巡视时间最短，则要求去巡视离点最远的点所花时间最小，由图一可知，离O点最远的点为H，所以就以巡视所花时间作为。当此小组只巡视H时，最小。在不超过的情况下，根据其他小组的剩余时间确定沿途是否巡视其他点。其中巡视原则为：①当一组人员巡视完规定点后时，在剩余时间允许的情况下，优先考虑原巡视点附近而距离较远的点，②最大限度使用剩余时间，主要考虑原则①。按照此原则，逐个巡视，直至巡视完所有点。

对于问题四，若巡视组数已定，则每个小组的最短路径就已确定，、、改变只影响的是整个的巡视时间。要求尽快完成巡视，即巡视时间要尽可能小。巡视时间包括到巡视点的行驶时间和在巡视点的停留时间。行驶时间主要取决于速度，而停留时间由、决定。所以此问题讨论的是当、、改变时对巡视时间的影响，即对、、的灵敏度分析。

五、 数据处理
由题目可知，共有53个乡镇，即在网络图赋权网络图中共有53个点. 其中表示图G的53个节点，表示相关联的两点的边集，表示相关联两点间的权值。
定义决策变量：

其中相关联表示两点之间有权值，不相关表示之间没有权值。
将这些点和权值生成图的矩阵，对于不相关的两点权值作为无穷大处理（数据.txt）。用MATLAB编写程序，得出该网络图的最小生成树。再运用迪克斯特拉算法求出出发点到各点的最短距离，即网络图的最短路径树。画出的两种图形如图1所示。

六、 模型建立与求解
6.1 问题一
6.1.1 模型建立
通过问题一的分析，建立多目标规划模型。
（1）三组巡视的总路线最短：

（2）巡视路线尽量均衡：

我们设当时，认为均衡度比较好。
综上得出目标函数：

约束条件：每个小组所走的路线必须是条回路。

6.1.2 模型求解
根据问题一的分析，根据两图的公共部分作为分组的界限，分组图如下（图2）：

将分好的三个子区域分别利用哈密顿原理进行编程求解，得到三个小组的巡视路线为：
第一组：O, P ,26 ,N ,23, 24 ,27 ,28 ,Q, 29, Q ,30, 32 ,31, R ,A, 33, 35 ,34 ,B, 1 ,O
行走的总路程为
第二组：O ,M ,21, K ,22 ,17, 16 ,I ,18 ,I ,15 ,14, 13, 14,H ,12 ,G ,11, J ,19, L ,20, 25 M ,O
行走的总路程为
第三组：O, 2 ,5 ,6 ,7, E, 9 ,F, 10 ,F, 9 ,E, 8 ,4 ,D, 3, C, O
行走的总路程为
三组所行走的总路程：

6.1.3均衡度分析
根据三组所行走的路程求得均衡度：

因为，我们认为均衡度不好，需要对分组进行修正。
通过结果发现第二小组所行走的路程比较多，而第三小组行走路程较短，我们考虑将分区2中离分区1较近但距1较远的11，G，12三个点划到第三分区中，而分区的区域不变。在此情况下，重新利用哈密顿算法编程得到三个小组的巡视路线如下表 1：
小组
路线
行走路程
第一组
O, P ,26 ,N ,23, 24 ,27 ,28 ,Q, 29, Q ,30, 32 ,31, R ,A, 33, 35 ,34 ,B, 1 ,O
206.8km
第二组
O,M,25,21,K,22,17 ,16 ,I ,18 ,I ,15 ,H ,14 ,13 ,J ,19 ,L ,20, 25, M, O
216.6km
第三组
O ,2 ,5 ,6, 7 ,E, 9 ,F ,10, F ,12 ,G ,11, E ,8, 4, D ,3 ,C, O
186.4km

则三组所行走的总路程：

此分区下的均衡度：

由可知，此种情况下的分区较为合理。各小组的巡视路线如下图3

6.2问题二
6.2.1模型准备：
根据第一问的结果得出在分三组的情况下，各小组所用时间：
第一组：
第二组：
第三组：
通过以上数据观察可知，分三组时不能满足题目要求，所以我们先考虑分四组。

6.2.2模型建立
根据问题二分析，建立多目标规划模型。
要求设计最佳巡视路线，即使总路程最短，并且所用时间相对均衡，得出目标函数：

约束条件：每个小组巡视所用时间均不超过24小时，即

6.2.3 模型求解
根据问题二分析，得出整个区域的分组情况。利用哈密顿算法编程求得各小组最短巡视路线及所用时间如下：
第一组:
巡视区域：A,B,Q,R,1,29,30,31,32,33,34,35
最短路程，所用时间
第二组：
巡视区域：K,M,N,P,16,17,21,22,23,24,25,26,27,28
最短路程，所用时间
第三组
G,H,I,J,11,12,13,14,15,18,19,20
最短路程，所用时间
第四组
C,D,E,F,2,3,4,5,6,7,8,9,10
最短路程，所用时间

6.2.4均衡度分析
根据以上所求结果，发现所用时间都小于24小时。但第三组用时较多，几乎接近24小时，而第一组用时较少。我们对各组所用时间进行均衡度分析：

因为，我们认为此分组结果不够合理，需要重新调整分组方式。
通过观察分析，将2分区中的村28划分到1中，同时将3分区中的村11划分到4中，同样利用matlab编程求得各组的最短巡视路线和所用时间，如下表2：
组号
巡视点
寻访个数
巡视路径
总路程长
耗时长（小时）
第一组
A B Q R 1 28 29 30 31 32 33 34 35
13
O,1,B,A,34,35,33,31,32,30,Q,28,Q,29,R,O
142.1
21.06
第二组
K M N P 16 17 21 22 23 24 25 26 27
13
O,P,26,27,26,N,24,23,22,17,
16,17,K,21,25,M,O
152.1
21.35
第三组
G H I J L 12 13 14 15 18 19 20
12
O,M,6,L,19,J,13,G,12,H,
14,15,I,18,J,19,20,25,M,O
196.5
22.61
第四组
C D E F 2 3 4 5 6 7 8 9 10 11
14
O,2,5,6,7,E,11,G,12,F,10,
F,9,E,8,4,D,3,C,O
186.4
23.33

根据表中数据可知，所有时间均小于24小时，对时间进行均衡度分析为：

我们认为此情况下的分组较为合理，同时得出各组的路线图为：

6.3问题三
由最短树路径树可知，从点到所有点距离中的最大距离，从点出发到点。同时计算出其所用时间：

即完成此次巡视所用的最短时间。
在不超过的情况下，其他小组巡视点的剩余时间：

其中

下面对剩余时间的利用进行讨论：
当时，直接返回县政府；
当时，巡视一个村；
当时，巡视两个村或一个乡（镇）；
当时，巡视三个村或一个村和一个乡（镇）；
当时，巡视四个村、两个个乡（镇）或两个村和一个乡（镇）；
当，巡视五个村、三个村和一个乡（镇）或一个村和两个乡（镇）；
当，情况不存在。
根据对的讨论和我们的巡视原则，逐个除去已巡视的点，直到所有点巡视完结束，最终求得需要23组。各小组巡视情况如下表3：
小组
路线
巡视点
剩余时间
兼巡视点
最终路线
1
O,2,5,6,7,E,9,F,12,H
H
0
无
O,2,5,6,7,E,9,F,12,H
2
O,2,5,6,L,19,J,13,14
14
1.27
13
O,2,5,6,L,19,J,13,14
3
O,M,25,21,K,18,I,15
15
1.43
18
O,M,25,21,K,18,I,15
4
O,2,5,6,7,E,9,F,12
12
1.58
9
O,2,5,6,7,E,9,F,12
5
O,2,5,6,7,E,9,F,10
10
1.66
8
O,2,5,6,7,E,8,E9,F,10
6
O,2,5,6,7,E,11,G
G
0.85
无
O,2,5,6,7,E,11,G
7
O,M,25,21,K,18,I
I
0.94
无
O,M,25,21,K,18,I
8
O,M,25,21,K,17,16
16
1.98
17
O,M,25,21,K,17,16
9
O,2,5,6,7,E,11
11
2.23
E
O,2,5,6,7,E,11
10
O,2,5,6,7,E,9,F
F
1.28
7
O,2,5,6,7,E,9,F
11
O,2,5,6,L,19,J
J
1.33
19
O,2,5,6,L,19,J
12
O,P,26,N,23,22
22
2.63
K
O,P,26,N,23,22,K,22
13
O,P,26,N,24
24
2.90
23,26
O,P,26,N,24,23,24
14
O,M,25,21
21
3.17
M,25
O,M,25,21
15
O,2,5,6,L
L
2.20
5,6
O,2,5,6,L
16
O,M,25,20
20
3.24
N
O,M,25,N,25,20
17
O,1,A,34,35
35
3.37
A,34
O,1,A,34,35
18
O,R,29,Q,30
30
3.39
Q,29
O,R,29,Q,30
19
O,2,3,D,4
4
3.43
3,D
O,2,3,D,4
20
O,R,31,32
32
3.70
R,33
O,R,31,33,31,32
21
O,P,26,27
27
3.81
P,28
O,P,26,27,28,27
22
O,R,31
31
4.17
1,B
O,R,31,1,B
23
O,2,C
C
3.77
2
O,C,O,2

6.4问题四
完成所有巡视所用最短时间：

我们以问题一中的第一组为例，其中。为方便讨论，将T,t统一作为时间变量，设(),则上式可改写为：

当停留时间t不变时，利用matlab作图得到巡视时间与行驶速度的关系如下：

由图示可知，当取值较小时，对巡视时间影响较大，即速度小范围波动时，我们也需重新考虑分组。
取值较大时，对巡视时间影响较小，即小范围波动时，不需要调整分组情况。

当速度不变时，同样利用matlab作图得到巡视时间与停留时间的关系如下图：

由图形可知，与成线性变化。即无论取何值，对的影响较大，当停留时间小范围波动时，也需重新考虑分组。

七、 模型评价、改进与推广
7.1 模型评价
7.1.1 优点：
1）本模型运用最小生成树和最短路径树相结合的方法，将区域分为三个部分，使求解简化；
2）引入均衡度的概念，使模型检验合理方便；
3）模型运用网络图的方法给出了灾情最佳巡视路线，缩短了时间，对与灾情的防治有极大帮助；
7.1.2 缺点：
1）运用哈密顿圈原理求得的回路不是最优解，检验修正路线的工作量较大。
2）问题四中，在对、、的灵敏度分析中，只对其变化作了定性分析，而未作定量分析。

7.2 模型改进
1）此模型只针对当前数据，对灾情的广泛区域没有实用性，我们可以建立动态规划模型，这样在数据发生变动的情况下，也可使用；
2）问题三中，根据我们设计的巡回路线，部分小组剩余时间较多而未充分利用，我们可以改进设计路线原则，尽量减少人力。

7.3 模型推广
该模型不仅可以运用到最佳灾情路线的确定问题，还可以推广到推销、投递、旅行商等实际问题中。

八、 参考文献
【1】杨桂元 黄几立/主编，数学建模[M]，—合肥：中国科学技术大学出版社，2008.8
【2】刘承平，数学建模方法[M]，—北京：高等教育出版，2002.7
【3】杨溪 王海龙 谭学平，灾情巡视路线网络模型[J]，甘肃高师学报，第4卷第2期（1999）
【4】俞文，多旅行商路线的几个问题[J]，数学的实践与认识，第29卷第1期，1999年1月

附录
灾情巡视图

第一问结果（表1）
小组
路线
行走路程
第一组
O, P ,26 ,N ,23, 24 ,27 ,28 ,Q, 29, Q ,30, 32 ,31, R ,A, 33, 35 ,34 ,B, 1 ,O
206.8km
第二组
O,M,25,21K,22,17 ,16 ,I ,18 ,I ,15 ,H ,14 ,13 ,J ,19 ,L ,20, 25, M, O
216.6km
第三组
O ,2 ,5 ,6, 7 ,E, 9 ,F ,10, F ,12 ,G ,11, E ,8, 4, D ,3 ,C, O
186.4km

第二问结果（表2）
组号
巡视点
寻访个数
巡视路径
总路程长
耗时长（小时）
第一组
A B Q R 1 28 29 30 31 32 33 34 35
13
O,1,B,A,34,35,33,31,32,30，Q,28,Q,29,R,O
142.1
21.06
第二组
K M N P 16 17 21 22 23 24 25 26 27
13
O,P,26,27,26,N,24,23,22,17,
16,17,K,21,25,M,O
152.1
21.35
第三组
G H I J L 12 13 14 15 18 19 20
12
O,M,6,L,19,J,13,G,12,H,
14,15,I,18,J,19,20,25,M,O
196.5
22.61
第四组
C D E F 2 3 4 5 6 7 8 9 10 11
14
O,2,5,6,7,E,11,G,12,F,10,
F,9,E,8,4,D,3,C,O
1864
23.33

第三问结果（表3）
小组
路线
巡视点
剩余时间
兼巡视点
最终路线
1
O,2,5,6,7,E,9,F,12,H
H
0
无
O,2,5,6,7,E,9,F,12,H
2
O,2,5,6,L,19,J,13,14
14
1.27
13
O,2,5,6,L,19,J,13,14
3
O,M,25,21,K,18,I,15
15
1.43
18
O,M,25,21,K,18,I,15
4
O,2,5,6,7,E,9,F,12
12
1.58
9
O,2,5,6,7,E,9,F,12
5
O,2,5,6,7,E,9,F,10
10
1.66
8
O,2,5,6,7,E,8,E9,F,10
6
O,2,5,6,7,E,11,G
G
0.85
无
O,2,5,6,7,E,11,G
7
O,M,25,21,K,18,I
I
0.94
无
O,M,25,21,K,18,I
8
O,M,25,21,K,17,16
16
1.98
17
O,M,25,21,K,17,16
9
O,2,5,6,7,E,11
11
2.23
E
O,2,5,6,7,E,11
10
O,2,5,6,7,E,9,F
F
1.28
7
O,2,5,6,7,E,9,F

11
O,2,5,6,L,19,J
J
1.33
19
O,2,5,6,L,19,J
12
O,P,26,N,23,22
22
2.63
K
O,P,26,N,23,22,K,22
13
O,P,26,N,24
24
2.90
23,26
O,P,26,N,24,23,24
14
O,M,25,21
21
3.17
M,25
O,M,25,21
15
O,2,5,6,L
L
2.20
5,6
O,2,5,6,L
16
O,M,25,20
20
3.24
N
O,M,25,N,25,20
17
O,1,A,34,35
35
3.37
A,34
O,1,A,34,35
18
O,R,29,Q,30
30
3.39
Q,29
O,R,29,Q,30
19
O,2,3,D,4
4
3.43
3,D
O,2,3,D,4
20
O,R,31,32
32
3.70
R,33
O,R,31,33,31,32
21
O,P,26,27
27
3.81
P,28
O,P,26,27,28,27
22
O,R,31
31
4.17
1,B
O,R,31,1,B
23
O,2,C
C
3.77
2
O,C,O,2

最短路径树matlab程序：

clear all
clc
d=[];
a=load('C:\Documents and Settings\Administrator\桌面\数据.txt');
a(find(a==inf))=0;
[b,c]=find(a>0);
for i=1:length(b)
d=[d;a(b(i),c(i))];
end
DG =sparse(b,c,d);
UG=tril(DG);
h = view(biograph(UG,[],'ShowArrows','off','ShowWeights','on'))
[dist,path,pred] = graphshortestpath(DG,1);

最小生成树matlab程序：
%%
clc;clear;
a=load('C:\Documents and Settings\Administrator\桌面\数据.txt');
result=[];p=1;tb=2:length(a);
while length(result)~=length(a)-1
temp=a(p,tb);temp=temp(:);
d=min(temp);
[jb,kb]=find(a(p,tb)==d);
j=p(jb(1));k=tb(kb(1));
result=[result,[j;k;d]];p=[p,k];tb(find(tb==k))=[];
end

M文件（将此M文件保存在matlab的工作目录下）
function [circle,long]=modifycircle(c1,L)
global a
flag=1;
while flag>0
flag=0;
for m=1:L-3
for n=m+2:L-1
if a(c1(m),c1(n))+a(c1(m+1),c1(n+1))<...
a(c1(m),c1(m+1))+a(c1(n),c1(n+1))
flag=1;
c1(m+1:n)=c1(n:-1:m+1);
end
end
end

问题一matlab程序
第一组：
%%
clc,clear
global a
c=load('C:\Documents and Settings\user\桌面\数据.txt');
UG=sparse(c);
b=graphallshortestpaths(UG,'directed',false);
a=b([1 2 3 15:19 41 42 44:53],[1 2 3 15:19 41 42 44:53]);
L=size(a,1);
c1=[1:7 9:20 8];
[circle,long]=modifycircle(c1,L);
c2=[1 5 11 4 9 10 12 13 6 14 15 17 16 7 2 18 20 19 3 8];
[circle2,long2]=modifycircle(c2,L);
if long2[1 9:14 31:40 43],[1 9:14 31:40 43]);
L=size(a,1);
c1=[1:17 18];
[circle,long]=modifycircle(c1,L);
c2=[1 7 16 5 17 12 11 3 13 10 2 9 8 4 14 6 15 18];
[circle2,long2]=modifycircle(c2,L);
if long2cuments and Settings\user\桌面\数据.txt');
UG=sparse(c);
b=graphallshortestpaths(UG,'directed',false);
a=b([1 4:7 8 20:30],[1 4:7 8 20:30]);
L=size(a,1);
c1=[1 15 16 17 3:14 2];
[circle,long]=modifycircle(c1,L);
c2=[1 2 7 3 8 12 15 16 17 4 13 5 14 11 10 9 6];
[circle2,long2]=modifycircle(c2,L);

if long214 2];
[circle,long]=modifycircle(c1,L);
c2=[1 6 3 2 14 12 13 11 9 10 8 4 7 5];
[circle2,long2]=modifycircle(c2,L);
if long2tpaths(UG,'directed',false);
a=b([1 12 14 15 16 34 35 39:45],[1 12 14 15 16 34 35 39:45]);
L=size(a,1);
c1=[1 2 4:14 3];
[circle,long]=modifycircle(c1,L);
c2=[1 5 13 14 4 11 10 9 7 6 2 8 12 3];
[circle2,long2]=modifycircle(c2,L);
if long2
第三组
%%
clc,clear
global a
c=load('C:\Documents and Settings\user\桌面\数据.txt');
UG=sparse(c);
b=graphallshortestpaths(UG,'directed',false);
a=b([1 8:11 13 30:33 36 37 38],[1 8:11 13 30:33 36 37 38]);
L=size(a,1);
c1=[1:13];
[circle,long]=modifycircle(c1,L);
c2=[1 6 12 2 8 3 7 9 10 4 11 5 13];
[circle2,long2]=modifycircle(c2,L);
if long2
c1=[1 3:15 2];
[circle,long]=modifycircle(c1,L);
c2=[1:15];
[circle2,long2]=modifycircle(c2,L);
if long2