2014年亚太杯APMCM数学建模大赛A题无人机创造安全环境求解全过程文档及程序-CSDN博客

2014年亚太杯APMCM数学建模大赛

A题 无人机创造安全环境

原题再现

  20 国集团又称 G20是一个国际经济合作论坛。2016 年第 11 届 20 国集团峰会将在中国召开这是继 APEC 后中国将举办的另一个大型峰会。此类大型峰会举办城市甚至举办地周围的城市都会采取严格的措施来为峰会提供保障尤其是安全领域。举办地地方政府都将投入大量的人力、物力和财力来维持社会秩序以及应对突发事件。
  无人机作为一种高科技产品逐渐被用于国防和安保领域。现在假设我国政府决定第 11 届 G20 峰会在上海市杨浦区举办并打算采用无人机对整个杨浦区进行监视。目前的无人机对复杂的外部环境比较鲁棒能够持续飞行 4 个小时并且当你策略改变时无人机携带的复杂控制器可以被立即重新初始化。当地政府要求你们团队完成以下任务
  计划 1杨浦区所有的地方都不能脱离监控状态超过 15 分钟请问至少需要多少架无人机才能达到这一目标
  计划 2对于杨浦区而言有些地点由于其人流量比较大是相对比较重要的比如五角场的万达广场、复旦大学周边道路。这样的区域至少每 5 分钟被监测一次而有些人流量较小的地方可以多于 20 分钟被监测一次。请问你至少需要多少无人机来满足上述的条件
  计划 3假设所有的区域都是同等重要的都应该保持有规律地监测但是由于发生故障30%的无人机无法使用了。此时你的监测计划可以提供多大的监测范围

整体求解过程概述(摘要)

  本文根据杨浦区无人机监控的三个规划要求对无人机轨迹和监控区域进行了优化设计。该方案建立了基于遗传算法的无人机最优路径模型、无人机监控区域规划模型和模拟退火算法然后将两个模型相结合进行分析求解。
  为了规划a本文首先分析了无人机摄影测量系统的具体参数得出无人机监测面积为0.6849km2。同时通过对图像的处理将问题简化为满足无人机监控飞行路径节点和路径约束的问题。根据方案a发现该问题属于全局最优搜索问题。因此本文引入并使用遗传算法来解决这个问题。基于遗传算法建立了无人机最优路径模型。然后借助MATLAB计算出无人机的最短飞行路径长度为209.0776km通过物理运动学公式将无人机的数量转换为至少需要9架这满足了杨浦地区从监测状态到各地不超过15分钟的条件。
  本文提取了杨浦区2012年能够反映街道交通统计年鉴数据的人口密度进行聚类分析。根据聚类结果、街道和人口密度将本文划分为大人口密度、中等人口密度和小人口密度三级区域。接下来为每一级设计有针对性的区域无人机监控解决方案。同时分析了该问题属于局部最优搜索。因此本文选择了一种启发式随机搜索算法——模拟退火算法。并建立了基于模拟退火算法的无人机区域规划监控模型。最后本文计算出每一级区域需要无人机的数量分别为6架、4架和1架可以得出这样的结论在人口容量为约束条件下杨浦区监测区所有区域都需要无人机。
  根据方案c在分析问题后问题的解决方案基于方案a、b的核心。首先根据计划a所需的无人机数量本文计算出计划c只有6次无人机行动。利用基于遗传算法的无人机最优路径模型计算出无人机在15分钟内的最大监测面积为28.66km2这是基于监测面积的最大范围。根据杨浦区实际地形图的基本地形初始化六条规则。然后利用基于模拟退火算法的无人机监测区域规划模型得到6个无人机监测区位置图及相应的总监测范围最大面积占杨浦区总面积的66.94%。

模型假设

  1 假设无论杨浦贫困人口的地区分布在每一条街上每一条街的人口密度都是一样的

  2 无人机飞行轨迹的二维无限平面图形区域接近人员流动水平的实际需要监控区域的范围

  3 无人机时刻监测范围的区域差距可以忽略不计。

问题分析

  本文基于通用无人机监测上海杨浦区11日在G20峰会上设定的三种场景结合通用无人机摄影测量系统系数和杨浦区面积、边界等实际情况初步分析了飞机数量和无人机对杨浦区每架飞机所需飞行时间的全面监控可能为进一步深入研究和分析各种方案提供了逻辑依据。
  基本思路

  1 视觉摄像机焦距与面积的关系

  视觉相机焦距与视角之间存在一定的关系。传统尺寸的35mm胶片相机35mm是胶片的宽度包括穿孔部分35mm胶片的感光面积为36x24mm转换为数码相机对角线长度越近为43.2mm表面的CCD/CMOS标尺在数码单反相机中越大很多都接近35mm胶片感光CCD/CMOS尺寸。

  2 航空摄影高度的确定

  显示相机焦距与面积的关系航空摄影确定飞行高度的地面分辨率航空摄影GSD取决于飞行高度公式为

  3 本文在50毫米的无人机摄影测量系统中选择了相机镜头因为无人机摄影图像要用来制作成1:2000比例的地图数字产品DEM、DOM、DLG地面分辨率的航空图像GSD应该是20厘米结合上述理论通过数值计算得到相应的GSD飞行高度为1100m。无人机监测范围半径

  方案1的分析方法
  根据材料信息目前无人机在复杂的外部环境中也持续了四个小时的飞行由于以上对无人机摄影测量系统的参数选择、分析和计算监控过程将监控获取的图像转化为数字产品是镜头焦距为50毫米的无人机在实际监测中的飞行高度h=1100米监测面积为0.6849平方公里已知在上海杨浦区的区域面积为60.61平方公里略估算一架无人机在飞行初期完成一个杨浦区所需的时间为1小时37。614分钟初步估计所需的无人机数量为8架或9架。进一步分析问题在所有与杨浦区交会的前提下不从监测状态出发超过15分钟至少配备一架无人机以确保第十一届二十国集团峰会的顺利召开本文将问题转化为优化每架无人机的飞行路径采用局部最优全局最优的原则即通过运用遗传算法ga计算得出无人机监测整个杨浦区所有区域的最短路径通过路径长度和无人机飞行速度之间的运动学公式转换原理得出无人机数量至少需要

  方案2分析方法
  根据总体人口分布不均的特点十一届二十国集团峰会期间杨浦区周边交通点位的位置和环境发生了变化对存在安全隐患的溪流所在地人口较为稀少必须对溪流所在地进行更多的安全监控。11日G20峰会在安全监测计划2中要求对相对较大区域的交通至少每5分钟进行一次监测对相对较小区域的交通一次可监测20分钟以上有针对性地加强区域安全监测可以有效保障11日G20峰会的顺利召开。方案2不同于方案1加入交通是无人机路径规划的一个可变约束条件监测区域人口在一般人口密度下可以反应交通状况本文首先对杨浦区各街道的人口密度进行聚类分析杨浦区根据人口密度分为三个层次最大人口密度控制的无人机至少每5分钟监测一次人口密度较大的区域控制无人机距离监测状态不到15分钟而人口密度较小的区域控制无人人机监测一次可以超过20分钟在第一个方案的基础上进行了无人机最优控制路径轨迹的研究以二维平面图为初始化图形分析、研究并利用模拟退火算法的核心思想在满足不同分段的人口流动水平的前提下监测时间间隔通过初始化图形来填充每个流量级别的区域得出交通密度区域所需的无人机数量最后将每个区域的数量相加即得到至少需要规划的无人机的数量

  方案3的分析方法
  将所有区域识别为同等重要区域所有区域距离监测状态不超过15分钟处理方案1的处理问题相同差异是由于故障导致30%的无人机已经无法使用是根据无人机所需数量计划1计算只提供6架无人机监视杨浦区6无人机如何使监控区域最大处理逻辑与方案2类似基于无人机15分钟即可监控最大区域基于杨浦区地图形状初始化6个形状在优化的基础上仍然使用模拟退火算法将六个基本图形之间的重叠面积尽可能小并定位到杨浦区中心最后计算出六个基本形状覆盖面积的大小杨浦区的总面积只有70%的无人机监测可以提供最大的监测范围。

模型的建立与求解整体论文缩略图

全部论文及程序请见下方“ 只会建模 QQ名片” 点击QQ名片即可

程序代码

部分程序如下:

G=G.*1.5;
jin=[1 2 3 5 44 51 61 63 62 57 38 31];
bj=zeros(1,63);
while(1)
s=0;
for i=1:1:63
 if bj(i)>0
 continue;
 else
 s=i;
 fprintf('%d',s);
 bj(s)=1;
 break;
 end
end
if s==0
 break;
end
time=0;
while (1)
 min=99;
 minx=0;
 for i=1:1:63
 if G(s,i)~=0 && G(s,i)*(1+bj(i))<min && i~=s
 min=G(s,i)*(1+bj(i));
 minx=i;
 end
 end
 if time+G(s,minx)<7.5
 fprintf('->%d',minx);
 bj(minx)=bj(minx)+1;
 time=time+G(s,minx);
 s=minx;
 else
break;
 end
end
fprintf('\n');
end

x=zeros(1,4);
for i=1:1:63
 switch T(i)
 case 5
 a(1,x(1)+1)=i;
 x(1)=x(1)+1;
 case 12
 a(2,x(2)+1)=i;
 x(2)=x(2)+1;
 case 18
 a(3,x(3)+1)=i;
 x(3)=x(3)+1;
 case 25
 a(4,x(4)+1)=i;
 x(4)=x(4)+1;
 end
end
bj=zeros(1,63);
n=size(G,1);
for i=1:1:n
 for j=1:1:n
 if i~=j && G(i,j)==0
 G(i,j)=inf;
 end
 if G(i,j)==1.571*1.5
 % G(i,j)=inf;
 end
end
end
D=G;
for i=1:1:n
 for j=1:1:n
 R(i,j)=j;
 end 
end 
for k=1:n
for i=1:n 
 for j=1:n
 if D(i,k)+D(k,j)<D(i,j)
 D(i,j)=D(i,k)+D(k,j);
 R(i,j)=R(i,k);
 end 
 end 
 end 
end 
while(1)
 for i=1:1:4
 s=0;
 for j=1:1:x(i)
 if bj(a(i,j))==0
 s=a(i,j);
 bj(a(i,j))=bj(a(i,j))+1;
 t=i;
 fprintf('%d',s);
 break;
 end
 end
 if s~=0
 break;
 end
 end
 if s==0
 break;
 end
 time=0;
 tt=T(s)/2;
 if t==1
 min=inf;
 minx=0;
 for j=1:1:x(i)
 if time+D(s,a(i,j))<tt && bj(a(i,j))==0 && 
D(s,a(i,j))<min && a(i,j)~=s
 min=D(s,a(i,j));
minx=a(i,j);
 end
 if minx~=0
 break;
else
 continue;
 end
 end
 if minx~=0
 time=time+D(s,minx);
 ttt=s;
 while (ttt~=minx)
 fprintf('-->%d',R(ttt,minx));
 ttt=R(ttt,minx);
 bj(ttt)=bj(ttt)+1;
 end 
 s=minx;
 end
 end
 q=0;
 while time<tt
 min=inf;
 minx=0;
 for i=1:1:63
 if G(s,i)~=inf && T(i)+(25*bj(i))<min && i~=s && 
q*bj(i)<1
 min=T(i)+(25*bj(i));
 minx=i;
 end 
 end
 if minx==0
 break;
 end
 if time+G(s,minx)<tt
 if bj(minx)~=0
 q=1;
 end
 fprintf('->%d',minx);
 bj(minx)=bj(minx)+1;
 time=time+G(s,minx);
 s=minx;
 else
 break;
 end
 end 
 fprintf(' \n');
end
sum(bj)

全部论文及程序请见下方“ 只会建模 QQ名片” 点击QQ名片即可