数模竞赛-虹桥机场的智能调度

论文封面1装订线“工大出版社杯”第十八届西北工业大学数学建模竞赛暨全国大学生数学建模竞赛选拔赛题目B题密封号2017年5月2日剪切线密封号2017年5月2日计算机学院第34队队员1队员2队员3姓名郭春雨刘濠赫宁晨伽班级1001160701011601020116032装订线摘要本文主要研究在保证安全性和效率性的双重考虑下，对上海虹桥机场起降飞机调度的实际优化问题，建立数学模型，对机场的构型进行简化，以达到多目标优化的效果，提高机场的运作效率，尽可能的避免因调度不合理而造成的悲剧。问题一针对机场飞机的安全调度问题，我们认为这个不仅仅是一个单纯的路线安排问题。而是要综合考虑航班准点以及避免A类事故发生的问题。但是根据第一问的要求，我们把效率因素放到相对次要的地位，而是首先考虑飞机的安全问题。为此，我们首先采用0-1整数规划，对航班着陆的进行规划，设置三个决策变量分别与排序、是否位于一个跑道、时间先后问题进行整数规划。之后根据调度安全性的约束条件，写出另外一系列约束表达式（如5.1的分析），综合以上两步得到的不等式组进行规划，得到一个满足条件并且最优的解。取Generation=100，按照遗传算法进行求解，按照顺序分别对航班进行安排后即得到了如表5-4中的最终结果。问题二在第一问分析的基础之上，我们需要对整体的规划进行更加深入的优化，在保证航班的安全性的基础之上，尽量提高飞机调度整体效率。为此我们更改了航班起飞和降落原有的时间安排，在假设没有客观因素影响，飞机能够按照指定时间起飞和降落的基础之上，利用整数规划、遗传算法、lingo求解最短路径等方法对整体进行重新调整，把整个一个小时的调度过程缩短在2100秒之内，达到了预期的目的。具体调度结果见表5-6。关键词：遗传算法、0-1整数规划、lingo求解最短路径、三个决策变量3目录一问题重述-------------------------------------------------------------------------------------4二问题分析-------------------------------------------------------------------------------------42.1问题1的分析--------------------------------------------------------------------------62.2问题2的分析---------------------------------------------------------------------------7三模型假设-------------------------------------------------------------------------------------7四定义与符号说明----------------------------------------------------------------------------8五模型的建立和求解-------------------------------------------------------------------------85.1.1模型的建立-----------------------------------------------------------------------85.1.2模型的求解---------------------------------------------------------------------11由附件中给出的程序给出一组随机数生成初始的双染色体如下表5-1：115.1.2结果的分析---------------------------------------------------------------------145.2问题2的模型--------------------------------------------------------------------------145.2.1模型的建立---------------------------------------------------------------------145.2.2模型的求解---------------------------------------------------------------------145.2.3结果的分析---------------------------------------------------------------------16六模型的评价--------------------------------------------------------------------------------16七参考文献-----------------------------------------------------------------------------------17八附件------------------------------------------------------------------------------------------178.1附录1：生成随机数函数c语言代码：-----------------------------------------178.2附录2lingo求解最短路径---------------------------------------------------------188.3附录3流程---------------------------------------------------------------------------198.4附录4：所有起飞的飞机的数据--------------------------------------------------204一问题重述随着航空运输业的快速发展，空中交通流量管理的研究越来越受到国内外的普遍关注。由于航班安排气候机场设置等方面的影响，在一些繁忙的机场经常发生航班拥堵，甚至造成一些航空事故。就如题中所说上海虹桥机场，就险些发生严重的穿越事件。本题希望我们借助计算机建立一种航班智能调度模型，以解决由于航空运输业迅猛发展为机场带来的诸多问题，调度航班飞起降落时间以及航班飞起前和降落后地面路径规划，来保证机场的运行安全以及效率。假设所有航班都能按照安排的时间起飞和降落，地面飞机滑行速度恒定，忽略飞行人员注意力程度、疲倦程度、是否满载以及机场内外其他物体对飞机运动所造成的影响，地面请你根据相关信息，研究回答以下问题：1.设计一个跑道服务智能调度模型，调度内容包括空中飞机降落时间及降落后的运动规划，以及地面飞机起飞前的运动规划及起飞时间，安排所有航班的起飞和降落（包括次序、时间、地面滑行路径）。调度模型优先考虑跑道上飞机的安全，防止A类穿越事件发生，在此基础上考虑提高准点率和起降效率。2.对附件2所给出的起降航班时间进行重新编排，在保证安全的基础上，计算出起降完所有航班所需要的最短时间及相应的调度安排（包括次序、时间、地面滑行路径）。二问题分析这是有名的飞机调度问题。许多研究表明，现有算法很难寻找到调度问题的最优解，最有工程意义的求解方法是不再以寻找最优解为目标，而是试图在有限、合理的时间内找到一个有用的、近似的最优解。传统的调度是采用先来先服务（FCFS）的启发式调度方法，它基本上完全取决于管制员的经验和判断，缺乏科学性，经常会引起较大延误，已不能满足空中交通流量管理的需要。近年来，智能计算方法逐渐开始在调度问题上得到了应用，为解决大规模的调度问题提供了相对可行的方法。为此，我们希望通过研究带有时间窗的多跑道飞机着陆调度问5题，利用一些具有高度并行、自学习、自组织与自适应的特征的智能计算方法，通过模拟某一自然现象或过程对问题进行优化。针对方案优化问题，我们可以采用0-1整数规划和遗传算法建立相应的数学模型来求解。简单介绍遗传算法：根据高中生物所学知识与实际算法相结合，利用生物进化的原理，将实验数据与生物进化中的相匹配如下三线图。表2-1生物遗传进化的基本生物要素和遗传算法的基因要素定义对照表算法流程可以总结为以下几步：1规定一个初始化规模为n的群体，除了一个按照一个实际排序排成的染色体外，其余的染色体每个基因的值采用随机数产生器生成并满足问题定义的范围。记当前进化代数为Generation=0.生物遗传进化遗传算法群体种群染色体基因适应能力交配变异进化结束问题搜索空间的一组有效解经过选择产生的新群体问题有效解的编码串染色体的一个编码单元染色体的适应值两个染色体交换部分基因得到两个新的子代染色体染色体某些基因的数值发生改变算法满足终止条件时结束，输出全局最优解62确定针对于本解决问题所决定的适应度函数，采用适应度函数对群体中的每个染色体进行适应度评价，分别计算每个染色体的适应值，保存适应值最大的染色体A.3采用轮盘赌选择算法(附录里面有具体做法)对群体的染色体进行选择操作，产生规模同样为n的种群。4按照概率p从种群中选择染色体进行交叉，每两个进行交叉的父染色体，产生两个子代染色体，子代染色体取代父代染色体进入新种群。没有进行交叉的染色体直接复制进入新种群。5按照概率q对新种群中染色体的基因进行再变异操作，会导致发生变异的基因值发生改变，变异后的染色体取代原有的染色体形成一个新种群，未发生变异的染色体则直接进入新种群。6变异后的新种群取代原有群体，重新计算群体中各个染色体的适应值。如果群体的最大适应值A0大于A的适应值,则以A0取代A。7当前进化代数Generation加1，如果Generation超过规定的最大进化代数或A达到规定的误差要求，算法结束，否则返回。以下是我们查找构建的一个流程图如附录3所示。2.1问题1的分析根据地形图以及所提供的航班信息，并且保证跑到上飞机安全，防止穿越事件发生为重点需要解决两大问题。1.降落飞机与从T2航站楼将要起飞的在起飞跑道上的a类穿越事件。2.降落飞机与从T1航站楼将要起飞的在降落跑道上的a类穿越事件。因为T1、T2分居飞机场的两侧，所以这两类穿越问题可以是同一种数学模型的两次解出。针对多路线的规划问题，我们可以采用0-1整数规划和遗传算法建立相应的数学模型，之后将起飞飞机所用的时间窗作为限制条件求出此规划问题的最优7解。我们以0和1分别代表机场跑道和通道的被占用和可以通过，根据机场跑道自身的特点将跑道分支进行整理得到多条路线，将可以执行的轨道路径规划出来并以序号表示出来。2.2问题2的分析问题2相似于问题1，问题1是在保证安全、防止A类事件发生的基础上进行规划求最优。问题2中并没有向我们指明风速、风向等问题，并且要求我们将附件2中的表进行调整以达到求解最小时间的问题以及起降的效率问题。效率问题涉及的情况多而复杂，在使用0-1算法找出可行且安全的方案的基础之上。我们可以再次通过遗传算法，但是此次的双染色体中的飞机次序也由附件1中的随机数生成程序生成。在考虑到要达到最短时间的目的，我们也采用了lingo来解决最短路径的求解问题，以达到最短时间的优化。三模型假设1、假设所有航班都能按照附件2安排的时间起飞和降落。2、地面飞机滑行速度恒定。3、忽略飞行人员注意力程度、疲倦程度、是否满载以及机场内外其他物体对飞机运动所造成的影响。4、假设所有类型的飞机的最小尾流间隔均符合ICAO标准。5、假设乘客都能在指定时间之前登机完毕。6、忽略天气因素如雨雪天气的影响。7、假设横穿跑道只能够在Hi上通过。8、根据风速对起降的影响以及对飞机调度安全秩序的影响，A、B、C三条路上飞机的行驶方向与风速相反。89、假定岔路实际的距离是两个路口中点线的连线，其余路径尽可能的按照直线进行规划。四定义与符号