灾情巡视最佳路径选择(含程序).doc
- 文档编号:13763121
- 上传时间:2023-06-17
- 格式:DOC
- 页数:27
- 大小:694.04KB
灾情巡视最佳路径选择(含程序).doc
《灾情巡视最佳路径选择(含程序).doc》由会员分享,可在线阅读,更多相关《灾情巡视最佳路径选择(含程序).doc(27页珍藏版)》请在冰点文库上搜索。
灾情巡视最佳路径选择
摘要
本文解决的是对全县各乡镇和村庄进行灾情巡视线路的设计问题,该问题属于点的遍历性的TSP问题。
因此我们结合图论的相关知识并考虑到分组的均衡性,建立起了约束最优化线路模型来解决该问题。
针对问题一,我们先建立起目标函数(见5.11中式),随后根据各点的集中区域进行划分,引入均衡度ə进行分组方案的比较,最终采用方案二(见5.2中方案二)。
再利用破圈法得到了最短回路。
最后matlab编程求解(见附录一)得出三组的巡视路程分别为200.1公里,196.8公里,205.1公里,总路程为602公里,均衡度ə=0.0405。
具体路线安排见表二。
针对问题二,分析得到要在24小时完成巡视的任务最少要四组巡视人员,将问题一中各条线路的权重由路程改为了时间,并在结点处增加了结点权重。
Matlab求解(见附录二)得巡视的时间分别为21.73小时22.51小时,23.60小时,21.18小时。
所以至少分四组,具体路线安排见表三。
针对问题三,通过图论软件得出巡视到距离O最远的点H要的时间为6.43小时,要在这个时间上限内完成巡视,分析得到最优分配为24组。
最后借助图论软件求出最终方案(见表四)。
针对问题四,在不影响分组的均衡条件下,采用控制变量法对T,t,V分别为变量时的各自允许变化范围进行了研究。
得出了这三个变量的关系式,再根据式子进行了讨论,得到最终结果见表五。
关键词:
Hamilton圈破圈法TSP问题 路径最优化
1问题重述
1.1问题背景
今年夏天该县遭受水灾。
为考察灾情、组织自救,县领导决定,带领有关部门负责人到全县各乡(镇)、村巡视。
巡视路线指从县政府所在地出发,走遍各乡(镇)、村,又回到县政府所在地的路线。
1.2需要解决的问题
若分三组(路)巡视,试设计总路程最短且各组尽可能均衡的巡视路线。
假定巡视人员在各乡(镇)停留时间T=2小时,在各村停留时间t=1小时,汽车行驶速度V=35公里/小时。
要在24小时内完成巡视,至少应分几组;给出这种分组下你认为最佳的巡视路线。
在上述关于T,t和V的假定下,如果巡视人员足够多,完成巡视的最短时间是多少;给出在这种最短时间完成巡视的要求下,你认为最佳的巡视路线。
若巡视组数已定(如三组),要求尽快完成巡视,讨论T,t和V改变对最佳巡视路线的影响。
2模型的假设及符号说明
2.1模型假设
假设1:
假设汽车在路上以V匀速行驶,且不停留,不考虑故障,忽略外部因素影响
假设2:
巡视过程中除了正常停留外,没有因其它因素造成时间延误
假设3:
巡视路线可以重复
假设4:
对于要多次经过的乡(镇)或村只停留一次
假设5:
每个巡视人员只能走自己划分区域内的路线
2.2符号说明
符号
说明
G
表示加权图
Gi
表示子图
V
表示顶点,每一个乡(镇)或村看成一个点
E
表示边,乡(镇)或村之间的路线
w(x,y)
表示权重,乡(镇)或村之间的距离
S
表示回路路程总和
ə
表示路程均衡度
Li
表示每一条子回路
T
表示在每个乡(镇)停留的时间
I
表示在每个村停留的时间
Ti
表示第i组的巡视时间
V
表示汽车行驶速度
Z
表示划分的区域数
N
表示乡(镇)的数目
n
表示村的数目
Ni
表示第i组巡视乡(镇)的数目
ni
表示第i组巡视村的数目
m
表示所分的组数
表示时间均衡度
3问题分析
本文研究的是最佳巡视路线设计问题,要求从O点出发巡视完所有乡(镇)村后,在回到O点,此问题可以转化为旅行商问题,再设计相应的算法求解
针对问题一:
问题一要求设计3组巡视,巡视总路程最短且尽可能均衡,首先我们通过主观筛选法将原图划分为3个子图,每个子图顶点数大约为17个,相邻的点划在一个子图中,且尽量使每个子图构成一个回路,这样将原问题转化为单旅行商问题求解
针对问题二:
问题二在问题一的基础上加了时间的限制,在每一个顶点都有停留时间,且在24小时巡视完。
通过计算可得至少分为4组,才可能实现。
和问题一类似我们将原图划分为4个子图,分别计算每组的巡视时间,设计每组的巡视路线。
针对问题三:
问题三T,t和V的假定下,如果巡视人员足够多,完成巡视的最短时间,并设计最佳路线。
首先,我们分析可知巡视H使用的时间是最长的。
那么,设计分组时,其它组巡视的时间不能超过这一最长时间。
在计算过程中我们先从距O点远的点开始考虑,因为若巡视时间与最小时间相差较远可以考虑顺便访问途径的乡、村。
运用图论软件可以很好解决这一问题。
针对问题四:
巡视组数已定,要求尽快完成巡视,讨论T,t和V改变对最佳巡视路线的影响。
我们分别考虑当其中两个变量不变时对最佳路线的影响。
分为3种情况讨论。
4.数据分析及处理
4.1理论知识[1]
定义一个图G是指一个二元组(V(G),E(G)),其中:
其中元素称为图G的顶点。
2)E(G)是顶点集V(G)中的无序或有序的元素偶对
组成的集合,即称为边集,其中元素称为边.
定义图G的阶是指图的顶点数|V(G)|,用来表示;
图的边的数目|E(G)|用来表示.
用表示图,简记也用来表示边
设G=
令T=
一般说来,对于G的不同生成树T,C(T)也是不同的。
可以知道,其中必有一个最小者,而这正是人们最为感兴趣的。
因此,给定连通加权图G=
若对G的任意加权生成树T均有C(T0)≤C(T),则称T0是G的最小生成树。
下面给出一种求最小生成树的方法(破圈法):
设G是有n个结点的连通图,下面算法产生的是最小生成树。
算法的基本思想
先将图G的边按权的递减顺序排列后,依次检验每条边,在保持连通的情况下,每次删除最大权边,直到余下n-1条边为止。
4.2数据分析处理
我们把53个乡(镇)村看作53个顶点,它们之间的距离为权重,建立邻接矩阵,运用图论软件,可视化如下图所示
运用图论软件,自动选择最短路径,可以求得O点到53个顶点的最短距离及路径。
图一
5问题一的解答
5.1模型一的建立
5.1.1确定目标函数
公路网图中,每个乡(镇)或村,看作图中的一个节点,公路看作边,节点之间的距离看作对应边上的权,公路网问题就转化为加权网络图,问题一就转化为在加权网络图中,从给定点O出发,寻遍所有顶点再回到O,所得总权最小,即为多旅行商路线问题。
分三组巡视,则需要把图G分为3个子图,在每个子图Gi(i=1,2,3)中寻找最佳回路Li(i=1,2,3)。
巡视路线要尽可能均衡,因而每组巡视顶点数要尽量接近。
综上建立的模型为:
目标函数:
(0.1)
约束条件:
是对均衡度的度量,越小表示均衡度越好;S表示总的巡视路线,S越小表示巡回路线越短。
这两个目标函数不可能同时达到最小值,求解时要两者兼顾。
5.2模型的求解
因为最小生成树包含G中所有定点E,相邻两点之间的权重为这两点之间的距离,它描述了顶点之间的相近程度,故考虑最小生成树初步分块。
对于巡视组的划分,我们可以利用原图的最小生成树(所选择的都是权最小边).从县城出发的最短路生成树,或者原图的单旅行商路线等等子图作为依据,对边界进行合理划分后向内扩展等直观方法作近似处理.
分组巡视路线的最优解,应当采用增广完全图上的单旅行商路线分段的方法求得.但是根据原题图的规模以及边的稀疏性,用这种方法处理反而将使问题变得更为复杂,而且考虑到均衡性要求需做的调整工作也将是大量的,因此,可以采用先适当进行点的分组,分别求出各组的单旅行商路线,然后在组问进行适当调整的方法求得近似解。
问题一求解流程图(图二)
均衡度测试
建立数学模型
根据分区原则划3个分区
寻找最小生成树,求最短回路
分析问题
调整分区
接受模型
满足
不满足
算法实现:
求出G中任意两个顶点见的最短路,构造出完备图
输入图G的一个初始H圈。
用对角线完全算法产生一个初始H圈。
随机搜索出G中若干个H圈。
对2,3,4步所得每个H圈,用二边逐次修正法进行优化,得到近似最佳H圈。
在第5步求出的所有H圈中,找出权重最小的一个,即为要找的最佳H圈的近似解。
根据以下4条原则将原图划分为3组:
1从O点开始分解。
2分解的三个子图顶点数尽可能接近17个。
3尽量实每一个子图为连通图。
4尽量使每一个子图中与点O的最短路上的点在该子图内,尽量使每个子图的点在子图内形成回路。
运用破圈法得到图形如下,红色线条为最小生成树
方案一H划在第二组
图三
方案二H划在第3组
图四
I方案一的求解结果(具体程序见附录一)
表一
分组
路线
每组路程
均衡度
总路程
组
O--1--B--34--35--32—30--Q--28--27--24—23
--N--26--P--29--R--31—33--A--1--O
200.10
0.147
601.4
组
O--M--25--20--L—19--J--18—J—13--14--H—
14—15—I--16--17--22--K--21—25--M-O
216.6
组
O--2--5--6—7--E--11--G--12—F—10--F—
9—E--8--4--D--3—C--O
184.70
均衡度均衡度不够好,于是我们对路线进行了一些调整,把H划在第III组,这种方法更加合理。
II方案二的求解结果
表二
分组
路线
每组
路程
均衡度
总路程
组
O--1--B--34--35--32--30--Q--28--27--24--23—
N--26--P--29--R--31--33--A--1--O
200.10
0.0405
602.0
组
O--M--25--20--L—19--J--18--J—13—14—
15--I--16--17--22--K—21—25—M--O
196.8
组
O--2--5--6--7--E--11--G--12--H--12--F--10--F—9--E--8--4--D--3--C--O
205.10
均衡度均衡度很好,路程S增加不大,故调整后的方案更优。
5.3结果分析
问题一中,我们建立双目标最优化模型,但是二者不能同时达到最小值,对于两者我们都要兼顾,方案二在路程增加不大情况下,均衡度较好,因而我们选择方案二。
6问题二的解答
6.1模型的建立
6.1.1确定目标函数
在各乡(镇)停留时间T=2小时,在各村停留时间t=1小时(不考虑O点),在不考虑在路上时间情况下满足
(Z为组数)
Z的最小取值为3,若分为3组,每组在路上的时间为小时每组只能行走35公里,显然不可能实现。
考虑Z值取4,分为4组每组,在路上时间为小时,4组总共能行走的路程为公里大于问题一中求解的总路程,故Z=4是可能实现的。
据此,我们将原图分为4个子图。
综上模型为:
目标函数:
约束条件:
6.2模型的求解
分组时要考虑到在乡和村中停留的时间和在路程上消耗的时间,使在近处寻访的组多访问几个村和乡,远处的组则尽量少访问些村庄和乡,从而使各组的总的消耗时间比较均衡。
划分原则:
从O点开始分解分解的三个子图顶点数尽可能接近13个尽量实每一个子图为连通图尽量使每一个子图中与点O的最短路上的点在该子图内,尽量使每个子图的点在子图内形成回路。
据此,划分如下图所示
图五
运用问题一中同样的算法,可以得到结果如下(具体程序见附录二)
表三
组数
每组路线
每组路程
每组时间
巡视村
镇数
O--C--B--34—35—32--30--Q—29—
R—31—33—A—1--O
130.500
21.73
5个乡镇,8个村
O--P--28--27--26-N—23—24—23—22—
17—16—17--K—21—25—M--O
157.900
22.51
4个乡镇10个村
O--2—5--6-L—20—L--19—J--18--I—
15—14--H—14—13--J—19--L--6--5--2--0
196.000
23.60
4个乡镇,9个村
O-2--3--D--7--E--11--G--12--F—
10—F--9--E--8--4--D--3--2--0
181.200
21.18
4个乡镇,8个村
6.3结果分析
问题二在问题一基础上加了停留时间及巡视时间限制,但算法一样。
至少分为4组,才能在24小内完成巡视
7问题三的解答
7.1模型的建立
7.1.1确定目标函数
问题3中假设巡视人员足够多,即分组数不限,甚至每个村镇都能安排一个巡视人员。
那么,最短时间取决于最远那个村或镇。
分析发现H是所有点中距离O最远的点,则有:
即在T=2,t=1,v=35的情况下,完成巡视最短时间为6.43小时
设应分i组巡视,第i组巡视的乡(镇)数目,巡视村的数目,巡视路程综上建立的模型为
目标函数:
约束条件:
每一组的巡视时间不能大于
每一个顶点都要访问到,不能遗漏
分组数要尽可能少
均衡度不能大于我们规定上限
7.2模型的求解
寻找最优路径算法实现。
利用图论软件求出每一点到O点最短路径,进而得到任意点返回O点的所需的最短时间,将此时间作为各点的权值;由于每一点都要访问到,所以每一点都要走到。
任取一点,该点权值的两倍加上沿途访问的地点停留时间之和记为T',在tH-T'的时间内,看与该点相连的各点中有没有可以访问的点,若有,则继续;没有,则返回。
基于以上算法,借助图论软件编程得出结果如下表
表四
组号
访问路线
访问地点
所耗时间(小时)
1
O-1-B-C-0
1BC
5.98
2
0-1-A-34-35-O
A3435
6.03
3
O-R-31-33-A-1-O
R3133
5.52
4
O-31-32-30-Q-29-O
3230Q
6.17
5
O-R-29-Q-28-27-26-P-O
292827
5.07
6
O-P-26-N-24-N-26-P-O
P24
5.54
7
O-P-26-N-23-N-26-P-O
26N23
6.22
8
O-P-26-N-23-22-17-K-21-25-M-O
221721
6.12
9
O-M-25-20-25-M-O
M2520
6.18
10
O-2-5-6-7-6-5-2-O
2567
5.96
11
O-2-3-D-4-D-3-2-O
3D4
6
12
O-2-5-6-7-E-8-E-7-6-5-2-O
E8
5.84
13
O-2-5-6-7-E-9-F-10-F-9-E-7-6-5-2-O
F10
5.76
14
O-2-5-6-L-19-L-6-5-2-O
L19
5.64
15
O-M-25-21-K-18-K-21-25-M-O
K18
6.02
16
O-2-5-6-7-E-9-F-12-F-9-E-7-6-5-2-O
912
5.84
17
O-2-5-6-7-E-11-G-13-G-11-E-7-6-5-2-O
1113
6.08
18
O-2-5-6-7-E-11-G-13-14-13-G-11-E-7-6-5-2-O
14
5.56
19
O-2-5-6-7-E-9-F-12-H-12-F-9-E-7-6-5-2-O
H
6.42
20
O-2-5-6-L-19-J-19-L-6-5-2-O
J
6.1
21
O-M-25-21-K-18-I-18-K-21-25-M-O
I
5.5
22
O-2-5-6-7-E-11-G-11-E-7-6-5-2-O
G
5.58
23
O-M-25-21-K-18-I-15-I-18-K-21-25-M-O
15
5
24
O-M-25-21-K-17-16-17-K-21-25-M-O
16
4.44
8问题四的解答
8.1模型的建立
问题四巡视组数已定(如三组),要求尽快完成巡视,讨论T,t和V改变对最佳巡视路线的影响。
在问题三的基础上,即所分组数m为定值,要尽快完成巡视,即Ti尽可能小
要求m组中最大巡视时间最小
综上建立的模型为:
目标函数
时间均衡度[2]
约束条件
8.2模型的求解
规定当时间均衡度时最佳路线不变
最大巡视时间第e组Tg,最小巡视时间第f组Tf,
I.当T,t为定值时,巡视路线不变
V满足
.当T,V定值时,巡视路线不变
t满足
.当t,V定值时,巡视路线不变
T满足
取m=4,考虑问题二中分四组情况,取
则结果为:
表五
不变量
T和t不变
T和V不变
t和V不变
变量范围
当T和t为定值时,若,则最佳巡视路线不变;
当T和V伟定值时,若,则最佳路线巡视路线不变;
当t和V不变时,若,则最佳巡视路线不变。
9模型的评价、改进及推广
9.1模型的评价[3]
优点:
(1)本文所建立的模型是可以解决TSP问题,具有普遍性。
(2)提出的分组方法简便易行,可操作性强,且可逐步调整使分组达到均衡。
(3)在模型的结果表达和分析时与具体图相结合,使结果简单明了。
缺点:
(1)由于分组的存在,求出的只是一个近似最优解,并不能保证绝对最优。
(2)在划分区域的时候借助了划分经验,缺少严格的数学证明和推导。
(3)在第四问中只是定性理论分析缺乏数学证明,结果的严密性不强。
9.2模型的改进
(1)可以结合计算机进行多次仿真模拟使结果更加准确。
(2)在划分区域时可以增加方案,多种方案进行比较结果说服性会更强。
9.3模型的推广[4]
我们建立的模型不仅仅可以用于灾情的巡视,还可以解决旅行线路的设定等一系列由邮递员问题引申出来的子问题。
同时也可以解决图论的系列问题,如求最短路径,最优生成树等等。
参考文献
[1]E.米捏卡[美],《网络和图的最优化算法》中国铁道出版社,北京,1984
[2]卢开澄《图论及应用》,清华大学出版社,北京,1981
[3]韩中庚《数学建模方法及其应用》高等教育出版社2005
[4]谢兆鸿《数学建模技术》中国水利水电出版社2003.9
[5]张红梅杨铁军《matlab基础及其应用教程》
附录一
问题一的程序[5]
%分区I的求解程序
N=20;%输入地点个数
Result0=0.0;%用于记录最小的权值和
C=eye(N);
fori=1:
N
forj=1:
N
C(i,j)=inf;
end
end
fori=1:
N
C(i,i)=0;
end
%输入相关信息
C(1,2)=10.1;C(1,3)=6.0;C(1,4)=9.9;C(1,7)=12.9;
C(2,6)=10.5;C(2,11)=12.1;C(2,12)=15.2;
C(3,4)=5.9;C(3,8)=10.3;
C(4,8)=12.2;C(4,15)=17.6;
C(5,6)=10.5;C(5,9)=7.9;C(5,16)=13.2;
C(6,10)=7.8;
C(7,8)=8.6;C(7,12)=1.9;C(7,13)=9.2;
C(8,14)=7.4;C(8,15)=11.5;
C(9,16)=8.9;
C(10,11)=7.9;C(10,16)=18.2;
C(11,17)=8.3;
C(12,17)=7.2;
C(13,14)=7.3;C(13,19)=8.1;
C(14,19)=19;C(14,20)=20.3;
C(15,20)=8.2;
C(17,18)=7.7;
C(18,19)=10.3;
C(19,20)=14.9;
fori=1:
N-1
forj=i+1:
N
C(j,i)=C(i,j);
end
end
fori=1:
N
C(i,i)=0;
end
R=[1415201918171110169562127131483];
%随便输入一个环路
%下面求哈密顿圈
fori=1:
N-1
forj=i+2:
N
ifC(R(i),R(j))~=0&&C(R(i),R(j)) form=i+1: j forn=m+2: N ifC(R(m),R(n))~=0&&C(R(m),R(n)) k=R(m); R(m)=R(j); R(j)=k;%交换得到总权值更小的哈密顿圈 end end end else continue; end end end R=[1415201918171110169562127131483]; fori=1: N-1 j=i+1; Result0=Result0+C(R(i),R(j)); end Result0=Result0+C(R(j),R (1))+C(1,3)+C(3,4)-9.9; fprintf('路径为: '); fori=1: N ifi==2 fprintf('34'); else fprintf('%d',R(i)); end end fprintf('\n最小的路径和为: %3.2f\n',Result0); 路径为: 13415201918171110169562127131483 最小的路径和为: 200.10 对应路径为: O-1-B-34-35-32-30-Q-28-27-24-23-N-26-P-29-R-31-3
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 灾情 巡视 最佳 路径 选择 程序
![提示](https://static.bingdoc.com/images/bang_tan.gif)