脚踏实地的解决方案：运用稳健的仿真优化方法解决航空问题

挑战

作者：Paolo Scala 和 Miguel Mujica（阿姆斯特丹应用科学大学）以及 Daniel Delahaye（法国国立民用航空学校）

在 2017 年冬季模拟大会上发表

本文论述了在解决冲突时如何提高受不确定性影响的航空系统启发式解决方案的稳健性。文中描述了一个包括使用优化和模拟的框架，该框架反过来会生成伪最优时间表。通过反复评估生成解决方案中的不确定性并根据目标函数进行校准，逐步改进初始解决方案。仿真用于测试优化算法生成的解决方案在不确定环境中的可行性。结果表明，该方法能够改进具有不确定性的场景的解决方案，从而使其成为在真实环境中实施的绝佳候选方案。

引言

机场系统被认为是促进连通性的重要基础设施，对区域具有重要价值，是促进不同国家、行业和人民之间全球互动的关键。因此，预期的增长对现有设施构成了威胁，不希望因设施的技术限制而限制增长。此外，机场是各种要素和流程的连接，需要适当的工具对其进行有效管理。机场运营可分为陆侧运营和空侧运营，其中陆侧运营发生在航站楼内，空侧运营发生在航站楼外。就陆侧业务而言，可以将乘客视为实体，将值机柜台、登机口甚至商店和咖啡馆等休闲场所视为资源。因此，从这一分类可以看出，在机场系统中，有两个子系统是完全不同的，它们受完全不同的动力和逻辑支配。此外，这两个不同的子系统相互影响、相互作用。因此，如前所述，机场系统的特征符合本节开头给出的复杂系统定义，因此在分析机场系统时应将其视为复杂系统。航空系统的另一个特点是随机性，航空系统本质上是随机的，因此模拟是获得所需的正确洞察力以提高可预测性的关键技术。此外，航空业高度依赖于时间表，这也使其问题容易通过使用优化技术得到改善。然而，从业人员已经认识到，仅使用优化技术来解决运力问题是不够的（Scala、Mujica 和 Delahaye，2016 年）。 在这种情况下，需要考虑的一个基本概念是优化模型解决方案的稳健性。由于系统的可变性，优化模型提供的解决方案可涵盖多种不确定情景，因此，如果解决方案可应用于更多不确定情景，而性能不会发生重大变化，则该解决方案被定义为稳健型。

文献中有许多与航空问题解决方案稳健性相关的著作，这些著作的成果是开发了许多工具和方法。Chandran 和 Balakrishnan（2007 年）提出了一种稳健跑道调度的动态编程算法。在他们的研究中，他们考虑了飞机到达时间的不确定性，以跑道吞吐量和违反跑道最小间隔概率之间的权衡作为目标。Kim 和 Feron（2011 年）研究了引入随机延迟时的稳健登机口分配问题。他们将稳健性定义为两架飞机停在同一登机口的间隔时间，因此间隔时间越大，解决方案越稳健。他们计算了受干扰分配的数量和水平，并使用线性混合 0-1 优化模型和塔布搜索元启发式解决了这一问题，结果显示，与原始时间表相比，受干扰分配的数量和水平分别提高了 92% 和 95%。Arias、Guimarans、Mujica 和 Boosten（2013 年）的研究结合仿真技术，采用约束编程范式解决了随机飞机恢复问题，并将仿真结果获得的标准偏差与用于产生随机延迟的概率分布变化及其因问题规模而产生的预期传播进行比较，评估了解决方案的鲁棒性。Lee 的博士论文（2014 年）探讨了机场地面拥堵问题，他在工作中采用了跑道和滑行道运行调度优化方法，然后采用随机模拟来处理不确定性。Narciso 和 Piera（2015 年）考虑了稳健登机口分配问题，提出了一个采用彩色 Petri 网（CPN）形式的因果模型，以获得吸收流量所需的最小登机口数量。

本文的重点是提高鲁棒性，正如之前所定义的，通过元启发式方法求解的优化模型所产生的解决方案的鲁棒性。 该方法是迭代式的，旨在找到最适合受不确定性影响的系统的解决方案。本文介绍了该方法在机场冲突检测和解决中的应用。结果证实，通过改变用于解决该问题的算法参数，经过两次迭代后，有可能改进初始解决方案。 本文的组织结构如下：第 2 部分介绍了本文所处理的问题，然后在第 3 部分介绍了该方法以及优化和仿真模型的说明。第 4 节展示了应用于机场冲突检测和解决的方法的实施，并在同一节中展示和讨论了结果。最后一节是结论和未来工作。

问题描述

如今，许多欧洲机场都处于容量限制的边缘，这可归因于近年来航空交通量的快速增长。此外，预计未来几年航空交通量还会增长（空中客车公司，2016 年），因此，在未来可能出现拥堵的情况下，需要提供解决方案来解决这一问题。机场拥堵问题主要出现在空域航站楼机动区（TMA）内和跑道入口附近的地面上。TMA 是机场周围空域的一部分，在这里降落的飞机流向机场空侧汇聚。空中交通管制员对到达和起飞率的良好管理可以缓解机场、空域和地面潜在的拥堵情况，同时提高跑道吞吐量（Frankovich，2012 年）。本文所考虑的机场冲突检测和解决问题是指飞机着陆流的排序和地面容量管理。在这一具体问题中，空域中的冲突是由于最小分离限制而被检测到的，而地面上的冲突则是由于容量超载而被检测到的。接下来将详细介绍空域、跑道和地面部分的冲突。解决这一问题的目的是确保空域内飞机流动的安全，将空域冲突降至零，并减少地面容量过载。有关该问题的更多详细信息，请参阅 Ma, Delahaye, and Sbihi (2016)。

空域与跑道冲突

关于空域，给定一些在一个最终点（初始进近固定点-IAF）汇合的着陆航线（见图 1）和一组着陆飞机，主要目标是确定飞机的顺序，使其在 IAF 汇合，而不会造成最小分离度违规。在跑道方面，当两架连续穿越跑道的飞机之间的间隔小于所需的最小间隔值时，就会检测到冲突。最小间隔值是根据不同的跑道运行情况设定的，可以是到达（跑道内）或离开（跑道外），并基于前方和后方飞机的尾流类别。空域的最小间隔由国际民航组织标准（ICAO 2007）提供，跑道的最小间隔取自 Frankovich（2012）。

地面冲突

关于地面运行，所开发的模型是一个高层次模型，这意味着没有对地面运行进行详细建模。因此，首先要确定地面的主要组成部分，然后为每个组成部分分配容量。确定的主要地面组成部分是滑行道和航站楼。容量定义为同时使用其中一个部件的飞机数量。飞机降落并离开跑道后，穿过滑行道，直到停在登机口。如前所述，地面模型是一个高层次的模型，这意味着滑行道路线没有被详细考虑，因此，滑行道的运行采用平均旅行时间建模。 转弯时间是基于真实的时间表，从登机口到离开跑道进入滑行道的旅行时间采用平均旅行时间进行考虑。目标是不超过这些组件的容量，在这种情况下，冲突由最大容量超载和平均容量超载之和表示。表 1 显示了与本工作中所考虑的示例相关的主要地面部件的容量。

表 1：主要地面组件的容量。

解决方案

框架

本节将介绍的框架是将基于滑动窗口的优化模型与基于离散事件模拟的模型相结合，以实现上述范围。本节其余部分将介绍该方法的结构，然后对优化过程和仿真环境进行详细说明。

方法说明

如图 2 所示，本文提出的方法可分为两个主要步骤。第一步，对所研究的系统进行优化，目的是根据特定目标获得最优或次优解。本文将这一方法应用于机场冲突检测和解决难题，研究目标是实现零冲突场景。考虑到优化过程会产生一个精确的解决方案，其中大部分运行参数都是确定的，因此该解决方案在实际环境中进行测试时，很可能会对由于系统可变性而产生的细微变化非常敏感。在该方法的第二步中，采用模拟来引入系统的可变性，并测试优化过程所提供的解决方案的稳健性。在仿真环境中，允许一些影响现实解决方案的相关参数具有不确定值。这种方法是迭代式的，也就是说，只要鲁棒性能在一定程度上得到改善，这两个步骤就会一直进行下去，而这一程度就是迭代过程的停止条件。在这项工作中，稳健性是以模拟解决方案的性能与理想方案的偏差来衡量的，其中性能是以冲突数量来评估的，而理想方案则是冲突为零的解决方案。在这种情况下，当偏差最小时，稳健性就会提高。

优化过程

本方法的优化过程，特别是针对机场冲突检测和解决的优化过程，是基于滑动窗口法。这种方法根据窗口大小将整个问题划分为较小的子问题，然后沿时间跨度移动窗口。 这种方法的主要优点是，子问题更容易解决，所需的计算时间更少，此外，它以动态方式处理问题，在窗口沿时间跨度滑动时更新决策变量，从而提高了解决方案的质量。这种方法已被用于类似问题，并取得了良好的效果（Hu 和 Chen，2005 年；Zhan、Zhang、Li、Liu、Kwok、Ip 和 Kaynak，2010 年；Furini、Kidd、Persani 和 Toth，2015 年；Toratani、Ueno 和 Higuchi，2015 年；Man、Delahaye 和 Xiao-hao，2015 年；Ma、Delahaye、Sbihi 和 Mongeau，2016 年）。在这种方法中，每个实体（飞机）都会根据其相对于当前窗口的位置与某种状态相关联。因此，如果实体位于当前窗口外，则其状态为 "已完成"；如果实体位于上一个窗口和当前窗口之间，则其状态为 "进行中"；如果实体位于当前窗口内，则其状态为 "活动中"；如果实体位于下一个窗口内，则其状态为 "计划中"。在当前窗口中，将只对处于进行中和活动状态的实体做出决定，而对已完成的实体已经做出决定。对于计划中的实体，将在下一个窗口做出决定（见图 3）。

滑动窗口法的主要参数是窗口大小和移位大小，它们会在计算时间和解决方案质量方面影响优化过程的性能，因此，为了获得良好的解决方案，设置这两个参数的适当值至关重要。窗口越小，求解的子问题越小，但有些飞行信息可能不会被考虑在内。窗口越大，解决的问题越大，但同时一些飞行信息可能会被过早考虑。在这两种情况下，解决方案的有效性都会受到影响。每次窗口移动时，如果移动幅度较小，就会更新很多决策变量；如果移动幅度较大，就会固定更多的决策变量，而每次窗口移动时更新的决策变量较少，从而影响算法的性能。

该问题的求解空间被认为是 NP-Hard（Beasley、Krishnamoorthy、Sharaiha 和 Abramson，2000 年），因此需要使用元启发式来解决该问题并获得（次）最优解。为此，我们采用模拟退火元启发式（Kirkpatrick、Gelatt 和 Vecchi，1983 年）来解决滑动窗口法定义的每个子问题。事实证明，这种元启发式在处理类似问题时非常有效（Man、Delahaye 和 Xiao-hao 2015；Ma、Delahaye、Sbihi 和 Mongeau 2016）。关于滑动窗口法和元启发式的定义和详细解释不在本文讨论范围之内，如需了解更多详细信息，并更好地理解应用于这一特定类型问题的优化过程，请参阅 Ma, Delahaye, and Sbihi (2016)。

仿真环境

离散事件仿真（DES）已被纳入评估优化算法提出的解决方案中的不确定性影响的循环中，本节将介绍为此目的使用仿真的优势。使用 DES 可以将不确定性纳入方案中，而使用其他技术则不可能或非常复杂。在这种情况下，通过模拟引入不确定性，使情况更接近现实，并通过鲁棒性的定义，有可能获得一个在数学上可能不是最优的解决方案，但对真实系统中的干扰更有弹性。过去几十年来，DES 已被广泛应用于从制造到运输等多个领域，并被证明可用于假设分析、情景测试和决策支持工具（Banks，1998 年；Brunner、Cross、McGhee、Levis 和 Whitney，1998 年；Negahban 和 Smith，2014 年）。在 DES 中，时间是根据特定事件的发生而流逝的，实体的行动顺序是事先已知的。这种建模方法优于其他建模方法，如基于代理的建模方法或系统动力学建模方法，因为所建模的过程遵循顺序过程，可以在此范例下正确建模。而使用其他建模方法，例如基于代理的建模方法，则更适用于所建模的实体有更多自由度的情况，而且有必要实现实体所经历的决策过程背后的逻辑。而在本作品所模拟的系统中，则不需要这样做，因此，与使用其他技术相比，我们的框架更加灵活、易于维护且速度更快。

实施

3.1 节中介绍的方法已应用于机场冲突检测和解决。接下来将介绍模拟和优化模型的主要参数，以及方法的两次迭代和相关结果。

方法学参数

该方法涉及的参数可分为三类：可控参数、边界参数和随机参数。第一类参数是指与所研究问题相关的参数，因此是针对具体问题的。边界参数与优化过程本身有关，因此取决于所使用的优化类型。 可控参数是优化模型的一部分，因为它们代表了问题的决策变量。随机参数代表系统的随机性来源，因此取决于所研究的系统。下文将对这些参数进行介绍和讨论。可控参数和边界参数非常重要，因为它们是方法论实施的驱动力。仿真模型中的随机参数是影响仿真方法优劣的关键因素。正确选择和校准这些参数非常重要，在这项工作中，我们对这些参数进行了初步估算。

可控参数和边界参数

本研究中考虑的机场冲突探测与解决的可控参数包括

• 进入空域的速度：增加或减少飞机进入空域最后进近的速度。
• 进入空域时间：延迟或提前飞机进入空域进行最后进近。
• 后推时间：在飞机起飞前，延迟其在登机口的时间。

边界参数是指滑动窗口参数：

• 窗口大小：定义算法求解的每个子问题的大小。
• 移位大小：定义窗口移位的大小，因此也定义了每个子问题的决策变量更新量。

表 2 汇总了可控参数和边界参数，以及用于初始优化解的各自数值。需要注意的是，参数值中进入空域时间和推回时间的间隔为 5 秒，而进入空域速度的间隔为 1%。优化参数是连续的。

随机参数

本研究中考虑的机场冲突探测与解决的随机参数为

表 2：可控参数和边界参数。

• 进入空域时间偏差
• 滑行道飞行时间偏差
• 推回时间偏差

表 3 汇总了随机参数及其在模拟模型中使用的各自数值。请注意，随机参数是连续的。
表 3：随机参数。

实验

本文提出的方法已被应用于机场冲突检测和解决的问题。首先给出一个代表原始时间表的解决方案，然后给出另一个解决方案，这次是实施优化过程的解决方案，并对这两个解决方案进行比较。通过优化算法找到优化方案后，通过模拟模型引入不确定性，每次运行完成 50 次重复。然后对模拟结果进行分析，以检验优化方案的稳健性。以同样的方式进行第二次迭代，通过改变 4.1.1 中介绍的一些方法参数来运行优化模型，然后用仿真模型测试新生成的解决方案。由于优化模型和仿真模型都模拟了巴黎戴高乐机场一天的实际交通数据（2016 年 2 月 7 日），因此最初的时间表是基于该机场的运行情况。以下图表说明了初始时间表的结果，显示了空域、跑道的许多冲突，以及滑行道网络和航站楼的严重容量超载。

空域和跑道冲突是按小时计算的，因此可以看出冲突主要集中在一天中的哪个时段。图 4（a）显示，空域冲突的高峰时段出现在 8、9、12、13 和 20 点钟左右，冲突次数在 80 至 90 次之间。关于跑道（进场和出场）上的冲突，图 4（b）和 4（c）显示其冲突较多。在跑道内冲突趋势中，8 点至 10 点和 20 点之间出现高峰；在跑道外冲突趋势中，11 点至 12 点和 14 点之间出现高峰。

关于滑出冲突，从图 5（a）中可以看出，在 9 点至 14 点和 19 点至 21 点期间，容量设定为 18，出现了过载现象，在 21 点左右达到最大峰值 25。图 5(b)显示了三个候机楼的占用情况，尤其是 1 号候机楼（容量为 11），从 6 点到 21 点一直处于超负荷状态。

第一次迭代

根据该方法的程序，每次迭代的第一步都要运行优化模型，并从中获得优化解。在本例中，运行优化模型后，发现空域和地面部分的冲突均为零。图 6(a) 和 6(b) 显示

图 6：滑行道网络和航站楼白天的占用率趋势，可以看出并未出现容量超载的情况。

在仿真模型中运行优化方案后，第一次迭代结束，图 7 显示了空域和跑道的小时冲突趋势。

如果将不确定性考虑在内，可以看出，尽管优化方案给出了一个没有冲突的方案，但还是出现了新的冲突。特别是在空域方面，9 点钟出现了平均每小时 5 起冲突的高峰，其他一些冲突分布在白天（见图 7(a)）。至于跑道内，可以看出它受不确定性的影响不大，因为平均每小时冲突峰值几乎为 2（见图 7（b））。相反，出跑道受不确定性的影响较大，在这种情况下，白天平均每小时冲突峰值较多，11 时至 12 时有 10 个，14 时至 15 时有 12 个，22 时有 9 个（见图 7(c)）。至于地面部分的超载，航站楼不受不确定性的影响，因为它们没有容量超载，滑行道平均最大容量超载为 2.05。

第二次迭代

由于第一次迭代的结果表明加入不确定性后存在冲突，因此进行了第二次迭代。在第二次迭代中，运行了优化模型，调整了一些可控参数或边界参数，以便有一个新的解决方案与模拟模型一起进行测试。在这种情况下，通过运行优化模型，将滑动窗口优化方法的窗口大小从 3 小时改为 2 小时，从而获得了新的解决方案。这种选择的理由是，当窗口尺寸过长时，算法往往会过早地考虑到一些在计划中遥遥领先的航班信息，这可能会导致动态信息的丢失。

这种方法的优势会影响解决方案的质量。因此，测试较小的窗口尺寸可能会得到更稳健的解决方案。新解决方案的结果如表 4 所示。

表 4：优化结果，第二次迭代。

可以看出，该方案几乎没有冲突，因为跑道和航站楼都存在一些冲突。因此，从优化的角度来看，该方案不是最优方案，而是次优方案。图 8(a)、图 8(b)和图 8(c)是通过模拟模型对该方案进行测试后得出的结果。从图 8(a)中可以看出，在 6 点、10 点和 12 点分别出现了 4、5 和 7 个空域平均每小时冲突的峰值。至于跑道内平均每小时冲突次数，从图 8（b）中可以看出，在 8 点和 12 点分别出现了 1.6 和 2.1 次高峰。跑道外的结果只在 14 点钟出现了一个平均每小时 14 起冲突的高峰。

表 5 汇总了两次迭代的结果。从第二列和第三列可以看出，相对于第一次和第二次迭代，第二次迭代将跑道外的平均冲突次数从 89.9 次减少到 85.32 次，但并没有改善空域的平均冲突次数。跑道内、滑行道和航站楼等其他部分的数值在第一次和第二次迭代之间保持稳定。

该方法的预期结果应该是每次迭代后冲突数量逐渐减少，同时获得一个平衡所有冲突的解 决方案。

表 5：两次迭代结果的比较。

各组成部分。在这种情况下，经过两次迭代，可以看出系统的某些部分，特别是跑道外的部分有了一些改进，而空域方面，该方法却没有改进。关于地面部分，结果证实它们受可变性的影响不大，这意味着它们可以很好地预测。不过，在考虑机场系统整体性能时，对两次迭代后结果的解释表明，第二次迭代的解决方案比第一次迭代的解决方案更加平衡，在稳健性方面有所改进。如果进一步迭代这种方法，预计解决方案的稳健性会有更大的改善。

业务影响

结论和进一步措施

本文提出了一个改进优化解决方案稳健性的框架，适用于机场冲突检测和解决问 题。结果表明，将两种方法相结合以提供更稳健的解决方案这一概念是可行的。当应用于优化解决方案时，不确定性被证实是一个高干扰因素。将不确定性纳入系统后，空域和跑道冲突受到的影响最大，而地面部分对不确定性的敏感度较低。反复实施的方法能够降低跑道外的冲突，但对空域冲突的影响不大。总的来说，经过两次迭代后，该方法获得了一个更加平衡的解决方案。进一步的讨论将是如何实施循环方法，以便我们能够微调两种方法相结合所获得的解决方案的稳健性。还可以进一步研究如何选择每次迭代时需要调整的参数，以使其更加有效和高效。作为该方法的未来发展，还可以研究的另一个方面是随机参数值的选择，例如，可以通过处理历史数据来实现。

致谢

作者感谢阿姆斯特丹应用科学大学航空学院、荷兰比荷卢模拟协会和 EUROSIM 对本研究成果的传播。