摘要：近年来，随着航空事业的高速发展，越来越多的机场被建立。与此同时，关于机场管理的复杂性也显著增加，其中，关于机场停机位分配问题（AGAP）一直都是各个机场需要解决的主要问题之一。如果操作处理不当，可能会发生轻微的航班延误或者事故，由此诞生的多米诺骨牌效应可能会影响机场的整体运营。机场停机位分配问题是运营经理每天面临的最重要问题之一。到目前为止已经有很多的研究者对这个问题提出过解决方案并且想方设法降低它的复杂性。该任务的目标是将每个航班（飞机）分配到可用的停机位，同时最大限度地提高乘客的便利性和机场的运营效率。这需要一种能够实时更改和更新停机位分配数据的解决方案。它还应提供强大而有效的中断管理，同时保持安全性，安全性和成本效率。

有关于停机位分配问题的的解决方案，早在1971年，国外研究者Braaksma 和 Shortreed，就以旅客在机场内行走距离最短为目标建立了停机位分配问题的优化模型，这是世界上首次有人就这个问题进行研究。时至今日，关于停机位分配问题的解决方案已有几十种，但是由于停机位分配问题是一个NP-hard问题（非确定性多项式困难问题），所以关于它的解决方案也是多种多样的。这些解决方案中的大多数可以大致分为“精确式”算法或“启发式”算法，精确算法是那些产生最优解的算法，启发式算法是基于经验的构造算法。自2005年以来，由于AGAP问题具有NP-hrad的特点，且现有工具仍未解决时间问题，大多数人开始考虑使用启发式/元启发式作为工具来解决AGAP问题。利用启发式/元启发式确定算法模型，并在有限时间内得出相对较优的解。

关键词：NP-hard；机场停机位分配问题；精确算法；启发式；元启发式；最优解。

 

目录

摘要

Abstract

一 前言-IV

1.1 机场停机位分配问题的来源及背景-IV

1.2 停机位分配问题国内外研究现状-IV

1.2.1国外研究现状及历史-V

1.2.2国内研究现状及历史-V

1.3 目前研究趋势-VI

1.4 论文主要研究内容及框架-VII

二 机场停机位问题概述-VII

2.1 机场停机位分配问题定义-VII

2.2 机场停机位问题的解决方案（数学模型）-VIII

2.2.1整数线性规划公式（IP）-VIII

2.2.2 二进制整数规划-IX

2.2.3 混合整数线性规划（MILP）-X

2.2.4 多目标AGAP方法-X

2.3 机场停机位问题（数学模型）归类-XI

2.3.1 二次分配模型-XI

2.3.2 调度模型-XI

2.3.3 集团划分模型（CPP）-XI

2.3.4 网络表示法模型-XII

三 常见启发式算法的理论剖析-XIV

3.1遗传算法（GA）-XIV

3.1.1遗传算法简介-XIV

3.1.2遗传算法思想和流程-XV

3.2模拟退火算法（SA）-XVI

3.2.1模拟退火算法简介-XVI

3.2.2模拟退火算法基本思想-XVI

四 具体案例研究-XVII

4.1背景介绍-XVII

4.2问题描述-XVIII

4.2.1机场布局-XVIII

4.2.2登机口分配-XVIII

4.2.3数据展示-XIX

4.3数学建模-XX

4.3.1问题分析-XX

4.3.2变量说明-XX

4.3.3目标函数的建立-XXI

4.3.4约束条件-XXI

4.3.5模型建立-XXII

4.4模型求解-XXII

4.4.3数据分类-XXII

4.4.4停机位分配-XXIII

4.4.5寻找最优解-XXIII

4.5主要结果-XXIII

五 论文总结-XXV

参 考 文 献-XXV

致 谢-XXVI