全球各地的航空公司都在探索多种策略，以履行国际民用航空组织(ICAO)设定的严格的二氧化碳减排承诺。欧洲特别重视这一举措，因为航空业占运输业碳排放量的13.9%。最大的推动力来自《欧洲绿色协议》，该协议旨在到 2051 年将交通运输碳排放量减少 90%。汉莎航空集团走得更远，承诺到 2030 年将排放量与 2019 年相比减少 50%，到 2050 年实现净零排放。
航空公司可以采用一种意想不到的方法来降低碳排放，即如何将飞机（通过涂在机尾的飞机注册号来识别）分配到各个航段，以尽量减少总运营成本，而燃料是其中的主要成本。飞机运行所需的燃料越多，意味着运营成本越高，排放到大气中的碳也越多。例如，典型的长途飞行（超过约 4,100 公里或约 2,500 英里）会排放约一吨二氧化碳。
出发地和目的地之间的飞行所需燃油量差异很大 — — 例如，飞机越大重量越大，因此需要的燃油也越多，而现代和较新的飞机由于使用了新技术，往往更省油。燃油本身的质量也很重要。飞机在飞行初期，当油箱满载时，其燃油效率低于飞行后期燃油量减少时。另一个影响尾部航班分配的重要因素是机上乘客人数；随着预订数量的变化，可能需要更小或更大的飞机。其他因素也会影响燃油消耗，既有负面因素（例如逆风或发动机年龄），也有正面因素（例如顺风、鲨鳍小翼、蒙皮）。
在过去的一年中，Google 的运营研究团队一直与汉莎航空集团合作，优化其尾部分配，以减少碳排放和航班运营成本。作为此次合作的一部分，我们开发并推出了一个数学尾部分配求解器，以优化瑞士国际航空公司（汉莎航空集团的子公司）的机队调度，我们估计这将显著减少碳排放。该求解器是瑞士国际航空公司启动的一个多阶段项目的第一步。
尾部分配的数学模型
我们将尾部分配优化任务构建为网络流问题，它本质上是一个有向图，以一组节点和一组弧为特征，并带有与当前问题相关的附加约束。节点可能对某种商品有供应或需求，而弧则具有流量容量和每单位流量的成本。目标是确定每个弧的流量，以最小化每种商品的总流量成本，同时保持网络中的流量平衡。
我们决定使用流量网络，因为它是文献中建模此问题的最常见方式，并且流量网络中的商品、弧线和节点与实际问题中的尾部、航段和机场具有简单的一一对应关系。在这种情况下，网络的弧线对应于航班时刻表的每个航段，每个单独的尾部都是沿网络“流动”的商品的单个实例。网络中的每个航段和尾部对都有相关的分配成本，模型的目标是选择有效的航段和尾部对，以使这些分配成本最小化。
尾部分配问题的一个简单示例。此计划中有四条航线，并且有四种可能的尾部可以分配给这些航线。每对尾部和航线都有相关的运营成本。例如，对于航线 1，将尾部 1 分配给它的成本为 50 美元，而将尾部 2 分配给它的成本为 100 美元。成本最低的最佳解决方案是将尾部 4 分配给航线 3 和航线 2，将尾部 1 分配给航线 1 和航线 4。
除了标准网络流量约束之外，该模型还考虑了其他特定于航空公司的约束，以便为汉莎航空集团的航空公司量身定制解决方案。例如，飞机周转时间（即飞机在两次连续飞行之间在地面上停留的时间）是特定于航空公司的，并且可能因多种原因而有所不同。餐饮可能在航空公司的枢纽装载，从而减少在外站所需的周转时间，或者一条航线可能有更多度假旅客，而这些旅客通常比商务旅客需要更长的时间登机和下机。另一个约束是，每架飞机都必须在地面上进行夜间检查，在指定机场的维护中心接受强制性维护工作或清洁。此外，每家航空公司都有自己的维护时间表，这可能要求飞机每隔几晚进行一次例行维护检查，部分原因是为了帮助保持飞机的燃油效率。
初步结果和后续步骤
瑞士国际航空公司使用我们的求解器优化其在欧洲的机队时刻表后，估计每年可节省 350 多万瑞士法郎，减少 6500 吨二氧化碳排放量。我们预计，当该模型推广到汉莎航空集团的其他航空公司，以及当客流量恢复到疫情前的水平时，这些节省将成倍增加。未来的工作将包括确保该模型可用于更大的数据集，并将机组人员和乘客分配添加到优化系统中，以改善乘客和机组人员的航班时刻表。
如果您有兴趣尝试自己的网络流模型，请查看我们的开源软件套件OR-Tools，它可用于构建与本文中介绍的求解器类似的优化解决方案。有关更多信息，请参阅 OR-Tools 相关文档。
致谢
感谢 Jon Orwant 和 Alejandra Estanislao 为本博文所做的大量合作以及与汉莎航空和瑞士国际航空建立合作伙伴关系。感谢运营研究团队和瑞士国际航空公司的员工，如果没有他们的辛勤工作和贡献，这项工作就不可能完成。
评论