英语原文共 7 页，剩余内容已隐藏，支付完成后下载完整资料
用遗传算法求解机场停机位分配问题
摘要：由于航空运输量的快速增长，为了提高机场的运力，使机场的资源更好地与接收到的航空运输量相匹配，优化机场管理显得十分必要。在本文中，我们根据在固定的日程航班安排研究了可用停机位对到达的航空器的分配。停机位分配问题（GAP）解决了最大限度地利用配备有航空桥的停机位的问题。本文提出了一种基于遗传算法（GA）的新方法来解决这一问题。编码策略在于用整数向量来表示染色体。每个基因的索引代表航班号，其值代表航班将被分配到的停机位的编号。生成初始种群的方法是基于三种不同的启发式算法和停机位的随机排序。选择方法是“适应度比例选择”称为“比例选择算子”。除了单点交叉和两点交叉算子，我们设计了贪婪过程交叉算子（GPX）。实验的基础是根据突尼斯迦太基机场的物理特性，采用不同的航班时刻表，生成虚拟场景。通过对确定性算法、简单启发式算法和遗传算法的比较，证明了最后一种算法在解决大规模问题时，在解的质量上是有效的。为了确定遗传算法的最优配置，我们比较了不同的交叉算子，发现贪婪过程交叉算子的使用提高了算法向更好解的收敛速度。
关键词：地面优化；停机位分配；元启发式；贪婪分割交叉（GPX）
- 绪论
为了确保机场的有效管理，管理者必须确定关键的资源并优化其利用率。考虑到保证飞机安全、降低成本以及最小化延误的目标，机场管理者应当将停机位分配问题（GAP）的优化作为主要问题之一。为了最大限度地利用安装有航空桥的停机位，本文我们拟对间隙进行研究。在介绍了文献综述之后，我们提出了基于遗传算法的方法。为了验证该方法的有效性和确定遗传算法的最佳配置，我们使用概率规则模拟了不同的测试用例，并将该方法与以往的工作进行了比较。
- 文献综述
停机位分配问题是为了优化机场收入，为每架飞机提供所需要的最大服务而研究的首要地面问题之一。自1979年以来，它被证明是NP-hard问题[1]。根据所研究的问题的复杂性和简化假设，文献中使用的求解方法从确定性算法到元启发式算法各不相同。在这一节中，我们试图涵盖大多数用来解决停机位分配问题的算法。
- 数学规划技术：根据目标函数、约束条件和考虑的假设，文献中采用了不同的数学公式。最常见的目标函数之一是最小化乘客步行距离。R、 A.Bihr[2]提出了乘客步行总距离的最小化问题，并引入了一种基于0,1线性规划模型的概念解，在此种模型中，他只处理单一的分配约束，而不考虑操作约束。G、 vanderstraeten[3]处理了最大化分配到服务区的飞机数量的目标，同时还考虑到操作的限制。作者介绍了一种基于隐枚举法的启发式算法求解数学模型。解决方法不考虑延误或航班取消。文献[4]研究了一个类似的目标，即最小化航站楼内部的行程，其主要贡献在于考虑了延误的成本。最近也有一些研究处理实时停机位重新分配问题，如[5]中提出的网络模型，该模型旨在按类型最小化飞机滑行的燃料消耗成本，并期望乘客对“紧密”连接的不适感与停机位的间距和连接时间成函数关系。文献[6]中介绍了另一个多目标规划数学模型，该模型旨在最小化未分配飞机的数量和最大化分配给配备有航空桥的停机位的航班数量。尽管数学模型多种多样，但确定性算法的缺点是不能有效地解决大规模问题。
在[7]中，作者描述了用于解决停机位分配问题的数学规划算法。他们选择描述两种具体的算法。第一种是基于二次分配模型，第二种是多模式调度公式。
- 启发式和元启发式：由于确定性方法在处理大规模问题时效率低下，许多启发式算法被开发出来。文献[8]中提出的启发式算法是将载客量较大的飞机分配给平均步行距离较小的停机位，以最小化总的载客步行距离。利用文献[9]提出的求解静态和实时停机位分配文题的启发式算法，研究了航班延误对Cplex求解器求解初始解的影响。它包括迭代重新分配航班的过程和修改惩罚值以获得可行的解决方案。[6]中描述的两种启发式算法是基于机场停机位的排序方式。第一种启发式方法FUGA是将第一架到达的飞机分配给第一个未使用的停机位，以便有利于使用特定数量的停机位，特别是因为它们提供的服务。第二个称为MUGA的方法是将第一架到达的飞机分配给最不使用的停机位，以平衡不同停机位的使用。启发式算法的共同缺点是，它们通常是为停机位分配文题的特定实例而设计的，而没有给出一般的方法。在文献[10]的假设下，开发了许多元启发式算法，并比较了基于遗传算法、模拟退火法、禁忌搜索和基于禁忌搜索的混合方法的四种启发式算法，模拟退火显示混合方法在解的质量和计算时间方面是最有效的。其次，禁忌搜索是三种元启发式算法中性能最好的一种。文[11]中还实现了禁忌搜索的混合模拟退火算法。作者处理了一个多目标问题，在这个问题中，他们将分配给停机位的飞行次数和总步行距离最小化。其他方法，如专家系统[12][13]和基于知识的系统[14]，被用来制定和解决停机位分配文题。
- 问题表述：确定性方法
在本节中，我们将参考[6]并对所提出的数学公式进行一些修改。主要的修改是我们不处理多目标问题。目标函数是最大化分配给配备有航空桥的停机位的航班数量。这一选择在[7]中也是合理的。事实上，作者认为，如果我们的目标是最小化乘客的总步行距离和连接时间，那么使用中转巴士将乘客从分配到停机坪的航班转移到航站楼可能会增加连接时间，并且很难认为是可取的。
考虑到这些修改，得到的数学模型如下：
： 分配给机场停机位的航班数；
：最初分配的航班数；
：机场停机位数；
：配备有航空桥的停机位数；
：第i号航班到达停机位的时间；
：第i号航班离开停机位的时间；
：如果执行航班号i的飞机最初被分配到登机门号k，否则等于0；
：已预先指定停机位的i号航班到达时间；
：已预先指定停机位的i号航班的预定起飞时间；
：航班号i要求的停机位类型（如果执行航班号的飞机可以使用登机桥停机位，则为1，否则为0）；
：i号停机位类型（如果停机位配有航空桥，则为1。否则为0）；
：如果我们不能同时使用停机位i和j，则为0。这种约束很常见，尤其是在使用航空桥时。事实上，对于每一个位置的航空桥。定义了一个新的停机位，但桥一次只能在一个位置使用
：执行i号航班的飞机翼展；
：停机位k的宽度（对应于为其创建停机位k的最大飞机的翼展）；
Safe_dist：停机位之间的安全距离。它给了飞机在停机位进出的空间；
如果执行航班号i的飞机被分配到登机门号k，则决策变量 ，否则为0,；
我们提出要求解的数学模型由以下优化公式表示：
Maximize (1)
约束条件：
(2)
(3)
(4)
(5)
(6)
(7)
(8)
(9)
(10)
- 遗传算法
- 一般遗传算法
遗传算法（GA）是进化算法的一部分，在John Holland[15]的工作中变得流行，John Holland在囚徒困境中使用了这种方法。遗传算法的原理是基于自然进化的技术。基本遗传算法可以用下图表示：
结束
图1：基本遗传算法
通常，初始化是使用基于简单技术的随机生成器生成初始总体
为了从一代传递到下一代，需要重复以下操作：
-通过适应度挑选亲本P1和P2；
-交叉算子用于从P1和P2生成一对后代C1和C2，它与概率Pc一起使用；
-其他的个体根据他们的适应度来选择。突变算子用于从具有概率Pm的选定个体中产生染色体，并且可以产生新的突变个体
-然后评估新后代和变异个体的适合性，以决定是否将他们引入新一代
- 编码方法
为了介绍用于表示可能的解决方案或染色体的数据结构，并且为了最小化其大小，我们使用了两个简单的规则来格式化数据。第一种是按航班到达时间的升序对所有航班进行排序，并为每个航班分配一个序列号；第二种是为每个停机位分配一个序列号。
因此，染色体由N个整数（N是航班次数）的向量表示。每个基因的索引代表航班号，其值代表航班将分配到的停机位号。
为了解释我们的编码方法，我们使用下面的例子（表1），其中包括将6个航班分配给5个停机位，其中3个停机位配备有航空桥（停机位1、2和3）。该表示法被简化，仅说明了最重要的特性（表2和表3）
|
5 |
1 |
2 |
3 |
4 |
2 |
表1：染色体示例
|
1 |
2 |
3 |
4 |
5 |
||||||||||
|
编号 |
宽度 |
航空桥 |
编号 |
宽度 |
航空桥 |
编号 |
宽度 |
航空桥 |
编号 |
宽度 |
航空桥 |
编号 |
宽度 |
航空桥 |
|
P1 |
100 |
Y |
P2 |
100 |
Y |
P3 |
100 |
Y |
L1 |
100 |
N |
L2 |
100 |
N |
表2：停机位表
|
1 |
2 |
3 |
4 |
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[236071]，资料为PDF文档或Word文档，PDF文档可免费转换为Word |
||||||||
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
