Google与汉莎航空合作，借优化机队调度降低碳排

在过去一年中，Google与汉莎航空集团合作，以解决机尾分配（Tail Assignment）优化问题，Google开发了一个机尾分配求解器，帮汉莎航空集团旗下的子公司瑞士国际航空，优化机队调度，而Google预期这将明显减少该航空公司的碳排。所谓的机尾分配问题，是指派特定飞行器，飞行特定航班的问题，而每台飞行器是以机尾编号为作为识别，因此称为机尾分配。

世界各地的航空公司都正以各种策略，探索满足国际民用航空组织（ICAO）所制定二氧化碳排放政策的方法，这方面更是欧洲的执行重点，尤其是航空业占运输业排放量的13.9%，主要的推行动力来自欧盟《欧洲绿色政纲》，该政纲要求2051年前，交通运输碳排量要减少90%。

而汉莎航空集团则更进一步设置目标，承诺要在2030年将碳排放量，降低到2019年的50%，并且在2050年时达到净零排放。航空公司可以降低碳排放的其中一种手段，便是优化飞机调度，也就是以最小化总运营成本来分配飞机。

燃料占总运营成本的一大部分，当运营飞机需要更多的燃料，就意味着需要更高的运营成本，而这也会产生更多排放到大气中的二氧化碳，超过4,100公里的典型长途飞行，约会产生一吨的碳排放量。

Google提到，用于飞行两地的燃料量差异很大，例如较大的飞机需要更多的燃料，而较新的飞机因为使用新技术，往往更省油，而且燃料本身的重量也很重要，飞机在飞行初期油箱满负荷，燃油效率较低，在经过一段时间后燃油量减少，效率才会恢复正常。

另外，机队调度一大重要因素是飞机上的乘客数量，由于预订数量的变化，可能需要改变飞机的大小。其他影响燃料消耗的因素，还包括风向和发动机年龄，或是不同的机身设计等。

Google利用网络流（Network flow）来解决这个机尾分配优化的问题，网络流本身是一个有向图，其特征是拥有一组节点（Node）和一组弧（Arc），并且可以对节点进出的流量设置限制。网络流通常被用来模拟道路系统的交通量、管中液体或是电路中的电流等事物。

Google研究人员决定使用网络流，是因为网络流的物体（Commodity）、弧和节点，与机尾分配中的飞行器、航段和机场有简单的对应关系，网络中的弧对应航班时刻的每个航段，每台飞行器是沿着网络流动的物体，网络中每个飞行器与航段的配对都有其关联的分配成本，而模型的目标是选择有效的飞行器与航段配对，来最小化分配成本。

除了标准的网络流量限制之外，Google所设计的模型，还考虑了航空公司特定的限制，来针对汉莎航空量身订做解决方案，像是考量飞机周转时间、餐饮装载等这类因航空公司不同的因素，而且当航线有更多的度假旅客，就需要考量这些旅客，可能需要比商务旅客更长的登机和下机时间。

另一个限制是，每架飞机都必需要在指定的机场维修中心，进行夜间检查，以接受规定的维修或是清洁工作，每家航空公司也都有各自的维护计划，诸如飞机每隔几晚就要进行一次例行性维护检查，而这也能帮助飞机保持燃油效率。

在瑞士国际航空开始使用求解优化机队调度后，该航空公司有望每年节省瑞士法郎350万元，相当于新台币一千万元，并减少6,500吨的二氧化碳排放。Google预估，当这个运算模型扩展到汉莎航空集团其他航空公司，且客流量恢复到新冠肺炎疫情之前的水准时，节省的成本将会以倍数增长。

这项研究接下来的工作，还需要收集更大的可用资料集，并将机组人员和乘客也考量进去优化系统中，来改善乘客和机组人员的航班时刻表。现在Google提供开源软件OR-Tools，使其他用户也能够以网络流来构建类似的解决方案。