基于随机规划与学习驱动到达时间预测的多跑道飞机着陆问题优化的稳定化分支与检查方法

《TRANSPORTATION RESEARCH PART E-LOGISTICS AND TRANSPORTATION REVIEW》：Stabilised branch-and-check method for optimising multi-runway aircraft landing problem modelled through stochastic programming with learning-driven arrival time predictions

　　

航空交通需求的持续增长对许多枢纽机场的容量造成了压力。有效的跑道运营对于优化现有跑道的利用至关重要，其中一项关键任务是在不确定性下管理跑道运营。本论文研究了枢纽机场多跑道系统中到达时间不确定性下的多跑道飞机着陆问题（MALP），旨在设计高效且环境友好的飞机着陆运营。研究人员使用随机规划（SP）并采用两阶段决策框架对该问题建模。在先进航空技术的支持下，空中交通管制通常可以根据精确预测的到达时间做出飞机排序决策。因此，研究人员将飞机排序决策纳入SP模型的第二阶段。在第一阶段，研究人员将飞机分配给跑道。在第二阶段，研究人员在到达时间揭示后做出飞机排序和调度决策。鉴于第二阶段问题包含整数变量和连续变量，该模型被称为具有混合整数补偿的SP模型（SP-MIR）。研究人员提出了一种优化增强的学习驱动情景生成（OLSG）方法，该方法采用机器学习技术估计未知参数的分布、构建情景，并利用p-中位问题（p-median problem）抽样代表性情景以输入SP-MIR模型。为了高效求解SP-MIR模型，研究人员提出了一种新颖的精确分解方法，称为稳定化分支与检查（SBAC）方法。该方法将原问题分解为稳定化主问题（stabilised master problem）和子问题，其中主问题围绕指定的稳定中心进行稳定化，以促进强Benders割（Benders cuts）的生成。所引入的算法增强进一步提高了求解稳定化主问题和子问题的计算性能。数值实验结果表明，所提出的SP-MIR模型和OLSG方法可以在实际场景和现实实施中提高多跑道运营的效率并减少环境影响。可扩展性分析结果表明，与文献中知名的基准方法相比，SBAC方法和算法增强在CPU时间方面实现了显著改进。

**论文解读文章**

**研究背景**
近年来，航空交通需求的持续增长导致许多枢纽机场的跑道容量日趋紧张。优化跑道运营（而非遵循先到先服务规则）可以减少飞机在等待航线中的数量，从而提升跑道容量和运营效率，并带来显著的经济和环境效益。然而，恶劣天气、延误传播、技术挑战和安全因素导致飞机到达和离开时间存在不确定性，这使得跑道调度问题（RSP）的输入数据具有随机性。现有不确定性下的RSP研究主要集中于单跑道或双跑道系统，且通常将飞机排序和调度决策置于同一阶段。然而，许多大型国际机场采用平行多跑道系统并实施隔离运行（特定跑道专用于进近或起飞），这要求空中交通管制（ATC）同时确定飞机-跑道分配、排序和调度决策，增加了问题复杂性。为此，本研究聚焦于多跑道系统中到达时间不确定性下的多跑道飞机着陆问题（MALP），旨在设计高效且环境友好的着陆运营方案。论文发表在《TRANSPORTATION RESEARCH PART E-LOGISTICS AND TRANSPORTATION REVIEW》。

**主要关键技术方法**
研究人员采用随机规划（SP）两阶段决策框架对MALP建模：第一阶段进行飞机-跑道分配，第二阶段在到达时间揭示后联合优化飞机排序和调度。为处理不确定性，提出优化增强的学习驱动情景生成（OLSG）方法，该方法利用随机森林（RF）算法估计到达时间分布，通过笛卡尔积构建初始情景集，并利用p-中位问题最小化抽样情景与原始情景之间的类型-1 Wasserstein距离，从而选择代表性情景输入SP模型。为高效求解具有混合整数补偿的SP模型（SP-MIR），提出稳定化分支与检查（SBAC）方法，将原问题分解为稳定化主问题和若干子问题，通过加入信任域约束和反向局部分支约束使主问题围绕稳定中心搜索，生成强Benders割。算法增强包括下界提升不等式（LBLIs）和有效不等式（VIs），分别收紧主问题和子问题的下界。数值实验基于香港国际机场（HKG）和亚特兰大哈兹菲尔德-杰克逊国际机场（ATL）的实际运营数据。

**研究结果**
**6.2 实际样本分析（Actual sample analysis）**：通过将不同情景生成方法支持的SP-MIR模型所获第一阶段决策代入实际到达时间情景进行测试。结果表明，基于机器学习（ML）的方法（LSG和OLSG）随着情景数量增加，其实际样本分析表现趋于更优；而历史数据驱动的情景生成（HDSG）方法表现未随情景数增加而改善。所有SP-MIR模型均优于确定性模型。OLSG₁₀方法（γ=10）在100情景时表现最佳，但OLSG₅方法（γ=5）在100情景下综合性能接近且所需CPU时间更短（26.08秒 vs 593.43秒），更适合近实时优化。
**6.3 现实实施（Real-world implementation）**：采用滚动时间窗方法（HKG：20分钟间隔，ATL：10分钟间隔）评估不同方法在2023年10月31日实际运营中的表现。结果显示，所有SP-MIR模型在环境成本方面均优于确定性模型。OLSG₅和OLSG₁₀方法表现最优，其中在ATL，OLSG₁₀将总目标值降低26.6%，环境成本降低45.9%。OLSG₅与OLSG₁₀结果接近，但情景采样时间更短，故更具实用价值。
**6.4 SP-MIR与SP-CR模型比较（Comparison of SP-MIR and SP-CR models）**：使用OLSG₅生成的100个情景比较两种模型。结果表明，SP-MIR模型在所有指标上均优于SP-CR模型：在HKG，总目标值降低3.06%，环境成本降低22.04%；在ATL，总目标值降低25.33%，环境成本降低44.91%。SP-MIR模型在第二阶段处理排序决策，能更灵活应对不确定性。
**6.5 决策者偏好水平的影响（Impact of decision-maker preference levels）**：通过调整目标函数中完工时间权重W₁和环境成本权重W₂（W₁+W₂=1）进行灵敏度分析。结果表明，当偏好从完工时间主导（0.99,0.01）转向环境主导（0.01,0.99）时，环境成本降低约25.0%，而完工时间几乎不变（变化小于0.005%）。平衡偏好（0.50,0.50）提供了实用折中方案。
**7. 可扩展性分析（Scalability analysis）**：测试SBAC方法及其增强变体在135个测试实例上的性能。7.1节比较不同信任域半径更新方案，方案3（逐步扩展：初始κ=?0.2×nc?，递增序列?0.4×nc?、?0.6×nc?、?0.8×nc?、nc）表现最佳，平均最优性间隙1.57%，平均CPU时间148.94秒。7.2节比较SBAC与三种基准方法（LBBD、SLBBD、BAC），SBAC在所有指标上最优：平均间隙1.57% vs 10.27%、16.44%、6.55%；CPU时间148.94秒 vs 290.95秒、268.10秒、181.13秒；非最优实例数17 vs 53、49、25。7.3节评估算法增强效果：同时加入LBLIs和VIs的增强SBAC将平均间隙降至0.12%，CPU时间降至54.23秒（降低63.59%），非最优实例数降至6个。与商用求解器GUROBI相比，增强SBAC的平均间隙为0.12%（GUROBI:5.90%），CPU时间54.23秒（GUROBI:231.81秒），非最优实例数6（GUROBI:35）。

**总结讨论**
论文结论部分翻译如下：
本论文研究了飞机到达时间不确定性下的多跑道飞机着陆问题（MALP）的SP-MIR模型。该模型采用两阶段决策过程：第一阶段将到达飞机分配给跑道，第二阶段安排着陆序列和时间。SP-MIR模型的目标是确保着陆运营的效率和环境可持续性。研究人员采用机器学习驱动的情景生成方法创建可能较小的有限情景集，并进一步提出优化增强版本，基于估计分布生成紧密反映实际情景的情景，从而避免极端情景影响SP-MIR模型导致次优决策。数值结果表明，将LSG和OLSG等高级机器学习支持的情景生成方法集成到SP-MIR模型中，可以有效支持在实际应用中制定运营高效且环境可持续的多跑道飞机着陆计划。此外，与以往研究使用的SP-CR模型相比，所提出的SP-MIR模型在保持运营效率的同时显著降低了燃油消耗和废气排放，从而增强了其在实践中的性能。数值研究还表明，跑道效率目标可能与环境目标存在冲突。由于SP-MIR模型是NP-hard问题，研究人员提出了带有算法增强的新型SBAC方法。该方法将原问题分解为分配主问题和多个排序与调度子问题；主问题中加入信任域约束和反向局部分支约束，使其围绕良好的稳定中心进行稳定化，从而生成强Benders割。研究人员使用HKG和ATL的真实数据进行了广泛的可扩展性分析。结果表明，带有算法增强的SBAC方法在计算性能上显著优于商用求解器和文献中知名的基准方法。