GRASP算法在停机位优化问题的应用研究

发布时间：2017-08-20 13:01

  本文关键词：GRASP算法在停机位优化问题的应用研究

  更多相关文章： GRASP 停机位分配 机场 遗传算法 适应度地形

【摘要】：中国民航业正经历着高速发展的腾飞期,在中国整体宏观经济发展迅猛的大背景下,民用机场的资源正逐渐显得捉襟见肘。而在众多的稀缺资源中,机场停机位供需矛盾是一个绕不开的难题。给进场航班分配一个适合的停机位,是停机位分配工作的主要任务。对停机位进行最大可能的优化分配调度,可以使旅客的平均行走距离大幅减少,令旅客产生更高的满意度,毫无疑问这对于对客户服务水平要求越来越高、竞争越来越激烈的民航领域,有着重大意义。本文参考了大量国内外学者对停机位分配问题研究的相关资料,并在此基础上,进一步研究了GRASP算法在此问题中的应用,主要研究工作包括以下几个方面:(1)分析了国内外的对停机位分配优化调度的相关算法,在总结前人研究的优势与劣势的基础上,深入分析了影响停机位分配最终效果的几种主要因素。(2)建立了相关的数学模型,对转机模型与不可转机模型加以分别讨论。针对两种模型,研究采用了随机算法分别生成的转机的、不可转机的两种模型的测试数据集。利用随机生成算法生成的多套加大了对实验效果的可信度,并为分析研究相关多种算法,在不同数据规模大小的停机位分配问题的应用效果特点做出了数据准备。本文的算法应用实验方法亦可为其它机场优化调度问题提供参考。(3)详细分析与讨论了GRASP算法在国内外优化问题的研究应用,并在前人的研究基础上,提出了GRASP算法的简化算法:GSP及GRSP,并在理论与实验上详细分析了这些算法及遗传算法、穷举算法及回溯算法等一系列经典算法,还有GSP算法、GRSP算法、GRASP算法嵌入遗传算法的混合应用算法在停机位分配的应用。对各算法在相关实验的应用效果特点做了研究分析。(4)对停机位分配问题,研究应用适应度地形分析(Fitness landscape analysis)技术,不仅从实际效果上,而且从理论上印证GRASP相比传统遗传算法的优越性。
【关键词】：GRASP 停机位分配 机场 遗传算法 适应度地形
【学位授予单位】：天津大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：F562;TP301.6
【目录】：

• 摘要4-5
• ABSTRACT5-9
• 第一章 绪论9-14
• 1.1 研究意义及背景9-10
• 1.2 本论文研究内容和方法10-12
• 1.3 论文写作框架12-14
• 第二章 停机位分配问题研究现状综述14-19
• 2.1 国外研究现状15-17
• 2.2 国内研究现状17-18
• 2.3 国内外研究存在的不足18
• 2.4 本章小结18-19
• 第三章 机场停机位分配的问题描述与公式表示19-25
• 3.1 机场停机位分配问题19
• 3.2 机场停机位分配问题的约束条件和优化目标19-20
• 3.2.1 机场停机位分配问题的约束条件19-20
• 3.2.2 机场停机位分配问题的优化目标20
• 3.3 机场停机位分配问题的数学模型构建20-24
• 3.3.1 模型符号的说明21
• 3.3.2 模型A21-22
• 3.3.3 模型B22-23
• 3.3.4 模型C23-24
• 3.4 本章小结24-25
• 第四章 解决停机位分配问题的GRASP类算法25-34
• 4.1 GRASP算法简介25-27
• 4.1.1 GRASP算法相关应用梗概25-26
• 4.1.2 对GRASP算法思想的分析26-27
• 4.2 解决停机位分配问题的GSP算法27-28
• 4.3 解决停机位分配问题的GRSP算法28-31
• 4.4 解决停机位分配问题的GRASP算法31-33
• 4.5 本章小结33-34
• 第五章 解决停机位分配问题的遗传算法混合算法34-40
• 5.1 遗传算法简介34-35
• 5.2 停机位分配的遗传算法混合算法设计35-39
• 5.2.1 停机位分配的遗传算法设计思想35-38
• 5.2.2 停机位分配的遗传算法的具体设计38-39
• 5.3 本章小结39-40
• 第六章 各算法实验结果及分析40-51
• 6.1 生成测试用问题的数据40
• 6.2 GRASP类算法在实验中的显示的一些特征40-44
• 6.3 对比实验44-50
• 6.3.1 小规模输入和大规模输入在模型A没有转机乘客的情况下的实验效果44-47
• 6.3.2 小规模输入和大规模输入在带转机乘客情况下的对模型C的实验研究47-50
• 6.4 本章小结50-51
• 第七章 对停机位分配问题解决算法的适应度地形分析51-56
• 7.1 适应度地形分析简介和相关研究工作介绍51-52
• 7.1.1 对适应度地形分析的简述51-52
• 7.1.2 对应用适应度地形分析相关工作的介绍52
• 7.2 对停机位分配问题应用适应度地形分析的实验及结果对比分析52-56
• 7.2.1 对停机位分配问题的遗传算法的适应度地形分析实验52-54
• 7.2.2 遗传算法与GRASP算法的适应度地形实验比较54-56
• 第八章 总结与展望56-58
• 8.1 全文总结56
• 8.2 工作展望56-58
• 参考文献58-62
• 发表论文和参加科研情况说明62-63
• 致谢63-64

【相似文献】

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

1 文军,孙宏,徐杰,梁志杰;基于排序算法的机场停机位分配问题研究[J];系统工程;2004年07期

2 文军,李冰,王清蓉,杜文;机场停机位分配问题的图着色模型及其算法[J];系统工程理论方法应用;2005年02期

3 常钢;魏生民;;停机位分配问题优化技术[J];中国民航学院学报;2006年02期

4 常钢;魏生民;;基于组合优化的停机位分配模型研究[J];中国民航学院学报;2006年03期

5 陈欣;陆迅;朱金福;;机场停机位指派模型及算法[J];交通运输工程学报;2006年04期

6 罗荣武;谢如鹤;张得志;;停机位分配问题的顶点着色模型及算法[J];系统工程理论与实践;2007年11期

7 卫东选;刘长有;;机场停机位再分配问题[J];南京航空航天大学学报;2009年02期

8 卫东选;刘长有;;机场停机位分配问题研究[J];交通运输工程与信息学报;2009年01期

9 杨文东;朱金福;许俐;;基于航班连结树的机场停机位指派问题研究[J];山东大学学报(工学版);2010年02期

10 尹嘉男;胡明华;赵征;;多跑道机场停机位分配仿真模型及算法[J];交通运输工程学报;2010年05期

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

1 张景杰;陈秋双;孙国华;张倩;;基于禁忌搜索算法的停机位应急调度研究[A];第二十六届中国控制会议论文集[C];2007年

2 刘长有;翟乃钧;;避免航班推出冲突的多目标停机位优化[A];第二十九届中国控制会议论文集[C];2010年

3 鞠姝妹;许俐;;基于GSAA的停机位指派优化问题的研究[A];2007第三届中国智能交通年会论文集[C];2007年

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

1 记者 贺鹏　通讯员 程旭日 林中涛;福州空港投资1亿扩建12个停机位[N];福州日报;2010年

2 记者 凌育增　通讯员 丁校书;深圳机场停机位增至94个[N];中国民航报;2009年

3 YMG记者 耿晶　通讯员 田南阳 李伟 丁玉峰;停机位增至十九个[N];烟台日报;2009年

4 封葑　李依枚;老航站楼“变脸新生” 停机位增建13个[N];沈阳日报;2007年

5 本报记者 高志广　通讯员 窦志鹏;新扩建八个停机位将投入使用[N];沈阳日报;2011年

6 陈滟　黄鹂 戴俊;紧急任务 紧急行动[N];中国国门时报;2009年

7 冯志宏邋林萍萍;吹响抗灾救灾集结号 边防官兵风雨赴一线[N];法治快报;2008年

8 记者 陈嘉佳 通讯员 张鹏 梅和帮;青海省德令哈机场试飞成功[N];中国民航报;2014年

9 记者 陈果;绿色新机场 市民抢先看[N];昆明日报;2008年

10 本报记者 郭瑛;南航空客A380运行保障准备进入倒计时[N];中国民航报;2011年

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

1 郑攀;民用机场停机位分配问题优化模型与算法的研究[D];北京交通大学;2012年

2 常钢;民航机场停机位分配与优化技术研究[D];西北工业大学;2006年

3 卫东选;基于运行安全的机场停机位分配问题研究[D];南京航空航天大学;2010年

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

1 卫瑷宇;基于多目标智能优化算法的停机位分配研究[D];中国民用航空飞行学院;2016年

2 王笑天;机场停机位分配优化技术研究[D];南京航空航天大学;2015年

3 皮亚杰;GRASP算法在停机位优化问题的应用研究[D];天津大学;2014年

4 刘文华;资源有限下的机场近停机位综合调度问题及其算法研究[D];清华大学;2010年

5 李峰;民用机场停机位资源分配方法优化研究[D];中国民用航空飞行学院;2011年

6 高菁;资源分配研究与应用[D];北京邮电大学;2013年

7 蒋延军;机场停机位分配优化问题的研究[D];天津大学;2010年

8 朱世群;大型机场机位实时调配问题的研究[D];南京航空航天大学;2007年

9 王宁;大型机场机位分配策略优化研究[D];华南理工大学;2013年

10 于翠玲;基于改进SWO算法的机场停机位分配优化问题的研究[D];天津大学;2012年

，

本文编号：706728