基于遗传模拟退火算法的航班着陆调度问题

摘要

随着国民经济的持续发展和中国在世界上受欢迎程度持续增加，我国民航飞行量快速增长，导致空中交通拥挤现象越来越严重。尤其在一些较繁忙的大型机场，航班延误现象时有发生。这不仅给航空公司带来了巨大的经济损失和信誉损失，也给旅客的出行安全带来了隐患。为了解决日益严重的空中交通拥挤现象，加大乘坐航班的安全系数，减少航空公司的延误损失，本文对航班调度问题进行了数学建模，建立了基于遗传模拟退火算法的数学模型，对单跑道的航班调度问题进行了充分的研究分析。
　　本文在参照国内外相关研究的基础上，主要对单跑道的航班调度问题进行分析研究。本文首先介绍了空中交通流量管理的相关内容，着重介绍了终端区流量管理的相关知识，包括终端区基本概念，航班飞行过程，航班排序等基础知识。其次，在考虑航班延误损失最小的基础上，建立了航班调度的数学规划模型，并利用先到先服务算法进行仿真分析，并对其进行了模型上的评价。最后，建立了基于遗传模拟退火算法的航班调度模型。主要设计思路有以下几个方面:
　　(1)遗传算法中采用整数序号的编码方式，以航班的实际降落顺序作为染色体的基因值，然后对染色体进行解码，生成航班的实际到达时间。其中解码操作的主要思想是:对于任意的染色体chrom=(x1，x2,…，xN)，为了保证总损失最小，首先考虑第一个降落的航班x1，令其实际到达时间即为其目标到达时间;然后对于第二个降落的航班x2，从最早到达和最晚到达的时间集合中，删去与航班x1不满足时间间隔的时间，从剩下的时间集合中选择距离x2的目标到达时间最小的时间作为航班的实际到达时间;其次，对于航班x3，同样从其最早达到和最晚达到的时间集合中，删去与航班x1和航班x2都不满足时间间隔的时间，从剩下的时间集合中选择距离x3的目标到达时间最小的时间作为航班的实际到达时间;以此类推可以得到各个航班的实际到达时间，进而完成染色体chrom的解码工作。对解码后的个体reach求解目标函数值objv。
　　(2)对初始种群中染色体进行选择，交叉，变异等操作。其中选择操作采用随机遍历抽样算法SUS。设子代的染色体的个数为Nsel，SUS具体方法为:随机排列种群适应度，在[0,SUM/Nsel]范围内随机产生一随机数作为指针，然后生成相隔SUM/Nsel的Nsel个指针，选择适应度范围在指针上的个体。相对于轮盘赌选择操作来说，SUS算法不仅具有更低的时间复杂度，而且具有最优零偏差、最小个体扩展。
　　(3)交叉操作采用两点交叉的方法。首先利用两两配对的原则对子代中的染色体进行两两配对，然后判断它们是否进行交叉操作。对通过交叉概率Pc的染色体进行交叉，首先产生两个随机整数作为交叉位置，交换两个染色体在交叉位置间的基因;然后利用部分映射的方法，消除染色体中的重复基因，最终得到可行的染色体。
　　(4)变异操作采用单点变异的方法。对通过变异概率Pm的染色体进行变异，对个体的某两个位置的基因值进行交换。
　　(5)对经过选择、交叉、变异得到的新个体Selch进行解码，对解码后的个体newreach求解目标函数值newobjv，然后调整解码后的个体并计算新的目标函数值。
　　(6)通过采用以上的遗传操作，再将模拟退火算法加入其中，对产生的新解进行Metropolis准则的判断:设reachi为问题的当前解，newreachi为新解，T为当前温度。objv, newobjv分别为解的目标函数值，增量df=newobjvi-objvi。则Metropolis准则为P={1, df＞0exp(-df/T)， df≤0如果df＞0,则以概率1接受新解;否则，以概率exp（-df/T）接受新解，舍弃旧解。
　　基于上面的设计和考虑，建立了基于遗传模拟退火算法的航班着陆调度模型。通过对单跑道航班调度问题的仿真分析，证明了遗传模拟退火算法的有效性。与先到先服务算法相比，遗传模拟退火算法能够更好地减少航班的延误成本。而且算法的适应性更广，能够适合不同目标函数、不同约束条件等情况。

目录

声明

摘要

第一章 绪论

1．1 研究背景及意义

1．2 国内外研究现状

1．2．1 国外研究现状

1．2．2 国内研究现状

1．3 主要工作及安排

第二章 相关研究介绍

2．1 空中交通流量管理概述

2．2 终端区流量管理基础

2．2．1 终端区的基本概念

2．2．2 终端区航班飞行过程

2．2．3 终端区航班排序描述

第三章 航班调度数学规划模型

3．1 数据信息

3．2 模型建立

3．2．1 假设条件

3．2．2 符号说明

3．2．3 目标函数与约束条件

3．3 先到先服务算法

3．3．1 先到先服务算法基本思想

3．3．2 先到先服务模型仿真分析

3．3．3 先到先服务模型评价

第四章 遗传模拟退火算法简介

4．1 遗传算法理论基础

4．1．1 遗传算法概述

4．1．2 遗传操作

4．1．3 遗传算法的主要步骤

4．2 模拟退火算法理论基础

4．2．1 模拟退火算法概述

4．2．2 Metropolis准则

4．2．3 模拟退火算法主要步骤

4．3 遗传模拟退火算法

第五章 基于遗传模拟退火算法的航班调度模型

5．1 遗传算法实现

5．1．1 染色体编码

5．1．2 初始种群生成

5．1．3 染色体解码

5．1．4 目标函数

5．1．5 选择操作

5．1．6 交叉操作

5．1．7 变异操作

5．2 模拟退火算法实现

5．3 遗传模拟退火算法实现

5．4 仿真分析

5．5 模型评价

第六章 结束语

参考文献

攻读学位期间发表的学术论文

致谢

附录