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

发布时间：2017-04-07 07:14

  本文关键词：基于遗传模拟退火算法的航班着陆调度问题，由笔耕文化传播整理发布。

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

• 摘要5-7
• Abstract7-13
• 第一章 绪论13-23
• 1.1 研究背景及意义13-17
• 1.2 国内外研究现状17-19
• 1.2.1 国外研究现状17-18
• 1.2.2 国内研究现状18-19
• 1.3 主要工作及安排19-23
• 第二章 相关研究介绍23-27
• 2.1 空中交通流量管理概述23-24
• 2.2 终端区流量管理基础24-27
• 2.2.1 终端区的基本概念24-25
• 2.2.2 终端区航班飞行过程25
• 2.2.3 终端区航班排序描述25-27
• 第三章 航班调度数学规划模型27-34
• 3.1 数据信息27-28
• 3.2 模型建立28-31
• 3.2.1 假设条件28
• 3.2.2 符号说明28-29
• 3.2.3 目标函数与约束条件29-31
• 3.3 先到先服务算法31-34
• 3.3.1 先到先服务算法基本思想31-32
• 3.3.2 先到先服务模型仿真分析32-33
• 3.3.3 先到先服务模型评价33-34
• 第四章 遗传模拟退火算法简介34-39
• 4.1 遗传算法理论基础34-36
• 4.1.1 遗传算法概述34
• 4.1.2 遗传操作34-35
• 4.1.3 遗传算法的主要步骤35-36
• 4.2 模拟退火算法理论基础36-38
• 4.2.1 模拟退火算法概述36-37
• 4.2.2 Metropolis准则37
• 4.2.3 模拟退火算法主要步骤37-38
• 4.3 遗传模拟退火算法38-39
• 第五章 基于遗传模拟退火算法的航班调度模型39-53
• 5.1 遗传算法实现39-45
• 5.1.1 染色体编码39
• 5.1.2 初始种群生成39
• 5.1.3 染色体解码39-41
• 5.1.4 目标函数41
• 5.1.5 选择操作41-42
• 5.1.6 交叉操作42-44
• 5.1.7 变异操作44-45
• 5.2 模拟退火算法实现45-47
• 5.3 遗传模拟退火算法实现47-49
• 5.4 仿真分析49-52
• 5.5 模型评价52-53
• 第六章 结束语53-55
• 参考文献55-59
• 攻读学位期间发表的学术论文59-60
• 致谢60-61
• 附录61-69

【相似文献】

中国期刊全文数据库 前10条

1 刘琳;谷寒雨;席裕庚;;工件到达时间未知的动态车间滚动重调度[J];机械工程学报;2008年05期

2 郭艳东;黄敏;王庆;;锁定初始调度的紧急工作单机重调度问题[J];东北大学学报(自然科学版);2013年05期

3 姜洋;孙伟;丁秋雷;张旭;;考虑行为主体的单机调度干扰管理模型[J];机械工程学报;2013年14期

4 席裕庚,王长军;控制、规划和调度问题中的博弈论应用[J];中国计量学院学报;2005年01期

5 徐群岭;;基于免疫优化的公交驾驶员调度问题[J];计算机工程;2010年24期

6 喻道远;史登松;刘盛强;张三强;;带模糊排序的移动瓶颈法求解不确定调度问题[J];机械制造;2011年02期

7 刘鹏;周晓晔;衣娜;;带有减少线性恶化效应的双代理调度问题[J];系统工程学报;2011年03期

8 刘晓东;陈英武;龙运军;贺仁杰;李菊芳;;同型机在线调度问题研究进展[J];计算机集成制造系统;2012年03期

9 姚君遗，杨善林，左春荣;基于实例FMS的AGV调度数学模型与算法[J];合肥工业大学学报(自然科学版);1995年01期

10 董平;机器调度问题及求解方法[J];物流技术与应用;1997年01期

中国重要会议论文全文数据库 前10条

1 李建更;涂凍生;马海涛;;单机拖后时间总和问题交付期扰动时最优调度不变范围的一种求法[A];第十九届中国控制会议论文集（一）[C];2000年

2 刘海龙;黄小原;;总的未完工费用最小的多机调度问题[A];1995中国控制与决策学术年会论文集[C];1995年

3 沈吟东;曾西洋;;公共交通驾驶员调度的复杂性及解决方法[A];’2004计算机应用技术交流会议论文集[C];2004年

4 李兵;蒋慰孙;;Job shop问题的建模及调度[A];1996中国控制与决策学术年会论文集[C];1996年

5 王海星;申金升;;智能蚁群算法解决公交区域调度问题研究[A];2006年首届ICT大会信息、知识、智能及其转换理论第一次高峰论坛会议论文集[C];2006年

6 王成尧;汪定伟;;模糊加工时间的单机调度问题[A];1996中国控制与决策学术年会论文集[C];1996年

7 齐向彤;涂奉生;;双交付期E／T调度问题[A];1997年中国控制会议论文集[C];1997年

8 吴斌;方叶祥;崔志勇;;基于人工蜂群算法的越库调度问题研究[A];第25届中国控制与决策会议论文集[C];2013年

9 方涛;吴受章;;FMS的自适应调度:结构与算法研究[A];1992年中国控制与决策学术年会论文集[C];1992年

10 刘兴初;赵千川;郑大钟;;具有不同准备时间和交付期的单机E／T调度问题研究[A];1998年中国控制会议论文集[C];1998年

中国重要报纸全文数据库 前2条

1 本报记者 贾科华;火电机组叫苦调度不合理[N];中国能源报;2012年

2 本报记者 高芳;牵住“牛鼻子” 巧解“推进难”[N];湖南经济报;2008年

中国博士学位论文全文数据库 前10条

1 郭鹏;具有分段恶化效应生产过程的智能优化调度研究[D];西南交通大学;2014年

2 元野;基于图着色模型的零担物流调度优化问题研究[D];哈尔滨工业大学;2015年

3 左燕;大规模复杂生产调度问题瓶颈分解方法研究[D];上海交通大学;2007年

4 王磊;OKP企业分散式项目计划与调度优化方法研究[D];哈尔滨工业大学;2013年

5 李小林;平行机环境下批处理机调度问题研究[D];中国科学技术大学;2012年

6 金毅;模糊集合论在生产计划和调度中的应用研究[D];东南大学;1994年

7 李玉庆;动态不确定环境下航天器观测调度问题研究[D];哈尔滨工业大学;2008年

8 刘志雄;调度问题中的粒子群优化方法及其应用研究[D];武汉理工大学;2005年

9 汤健超;基于混合进化算法的若干调度问题研究[D];华南理工大学;2012年

10 江维;任务关键实时系统的可信感知调度研究[D];电子科技大学;2009年

中国硕士学位论文全文数据库 前10条

1 张亮;云计算环境下的资源调度技术的研究[D];江南大学;2015年

2 冯卓鹏;重载运输卸车组织优化研究[D];西南交通大学;2015年

3 崔雪源;基于遗传模拟退火算法的航班着陆调度问题[D];华中师范大学;2015年

4 王翠;基于超图模型和相继干扰消除的链路调度问题的研究[D];曲阜师范大学;2015年

5 张勇;带拒绝和释放时间的单机批调度问题[D];山东大学;2015年

6 吴凡;基于粒子群优化算法的风电-火电机组组合调度研究[D];华北电力大学;2015年

7 赵虎;MTO模式下的制造企业稳健型调度问题研究[D];重庆理工大学;2015年

8 鲍和映;航空公司不正常航班调度研究[D];南京航空航天大学;2013年

9 羊晓飞;基于场景和模糊描述的不确定Job Shop鲁棒调度[D];山东大学;2009年

10 王建波;基于综合利益最优的集成调度优化模型应用研究[D];大连交通大学;2010年

  本文关键词：基于遗传模拟退火算法的航班着陆调度问题，，由笔耕文化传播整理发布。

本文编号：289914