灾情巡视路线模型.doc

数学建模
图论模型及方法
组别第1组
学生一电力131 刘乐
学生二新能131 怡广志
学生三新能131 加乐乐
时间 2015年5月4日
灾情巡视路线模型
摘要
本文研究的是考察灾情最佳巡视线路设计的问题,属于多旅行商问题,为此我们建立了网络图模型。利用最小生成树图形和最短路树图形相结合,通过分析、计算比较得出最优解。
对于问题一,我们建立赋权网络图。利用matlab编程得到此网络图的最小生成树图和最短路径树图,以两图相重合的部分作为分区的界限,将整个网络图分为三个分区。以总路程最短和均衡度最小作为目标函数建立多目标规划模型,利用哈密顿算法编写matlab程序求得各组最优巡回路线(见附表1)。
对于问题二,基于对问题一结果的分析,发现分三组的情况下,不能满足题目要求。因此我们首先考虑分四组的情况。在分三组的基础上根据分组原则将图大致划分为4各子图。同样以巡视路程最短和时间均衡度最小为目标函数,各巡视时间小于24小时作为约束条件建立多目标规划模型。利用哈密顿算法编程求得各组最佳巡视路线及巡视时间(见附表2)。
对于问题三,在巡视人员足够多的情况下,巡视距离点最远的点所用的时间为最短时间,根据最短路径树,从远到近,依次巡视各村镇,在所用时间不大于最短时间的前提下,各组尽可能多的巡视几个村镇,进行分组确立巡视点,并对已巡视过的点进行逐个剔除。通过人工记录,得出分组情况及巡视路线(见附表3),。
对于问题四,在组数固定时,则各组的最短路径就已确定,、、改变影响的只是整个巡视时间。我们利用matlab编程画图得到、、与巡视时间的关系曲线。观察曲线发现:①当速度较小时,的变化对巡视时间的影响较大;②停留时间与巡视时间呈线性关系,无论取何值,对巡视时间影响都较大。此两种情况下都需适当调整分组。
关键词: 最小生成树最短路径树赋权网络图哈密顿算法
问题重述
:
今年夏天该县遭受水灾。为考察灾情、组织自救,县领导决定,带领有关部门负责人到全县各乡(镇)、村巡视。巡视路线指从县政府所在地出发,走遍各乡(镇)、村,又回到县政府所在地的路线。
:
1)若分三组(路)巡视,试设计总路程最短且各组尽可能均衡的巡视路线。
2)假定巡视人员在各乡(镇)停留时间T=2小时,在各村停留时间t=1小时,汽车行驶速度V=35公里/小时。要在24小时内完成巡视,至少应分几组;给出这种分组下你认为最佳的巡视路线。
3)在上述关于T , t和V的假定下,如果巡视人员足够多,完成巡视的最短时间是多少;给出在这种最短时间完成巡视的要求下,你认为最佳的巡视路线。
4)若巡视组数已定(如三组),要求尽快完成巡视,讨论T,t和V改变对最佳巡视路线的影响。
灾情巡视图
模型假设
,不会影响汽车行驶速度;
,不计算停留时间;
,如果某一小组停留过,其他小组经过时不计算停留时间;
;
。
符号说明
第个小组所走路程
衡量均衡度(越小,均衡度越好;反之,均衡度越差)
巡视一个乡(镇)所花时间
巡视一个村所花时间
汽车的行驶速度
第个小组巡视所用时间
最短路径树中从O点出发到所有点距离中的最大距离
最短路径树中点距出发点的距离
完成所有巡视所用的最短时间
巡视完所规定的点外的剩余时间
小组巡视乡镇的个数
小组巡视村得个数
问题分析
本文研究的是考察灾情最佳巡视线路设计的问题,准确合理的路线设计对灾情巡视救治起着重要作用。为很好的解决此问题,为此我们建立了网络图模型。
对于问题一,题目要求在分三组巡视的情况下,使总路程最短且各小组所走路程均衡。先考虑分区,我们将得出的最小生成树图形和最短路树图形,进行比较并找出其公共部分。分组要求尽量不破坏最短生成树和最小生成树,所以我们以公共部分为界限,将此网络图分为三组。为使每小组所走路程均衡,我们引入了均衡度。它表示最大路程和最小路程的差值与最大路程的比值。越小,表示均衡度越好。以总路程最短和均衡度最小作为目标函数建立多目标规划模型,利用哈密顿原理得出各组的巡回路线,并对其分析修正求得各组最优巡回路线。
对于问题二,要求在24小时内完成所有巡视。通过第一问的结果,求得在分三组的情况下所用的平均时间大于24小时,所以我们先考虑分四组。我们的分组原则为:1、每子区域所分得的点近似相等;2、尽量使每一个子区域连通;3、使每一个子区域中与点O的最短路上的点在该区域内。根据以上分组原则将整个图大致划分为四个子图,同样利用哈密顿算法求得在相对均衡的情况每个小组的最短路径