困扰我们半个世纪的航班延误难题，就这么被AI解决了？

文/程一祥

如果有一天，你能用第一手航空实战数据，留下一个算法，带走一个世界级航空难题，顺便拿走几十万奖金，听起来是不是还蛮酷的？

听说你的航班又双叒叕延误了？

DT君曾经有一个梦想，就是成为一个“空中飞人”：坐着高端的航班，帅气地穿梭在蓝天白云间，日程满满地出席一个又一个高大上的活动，分享自己在成为数据网红道路上的微小经验。

如今，梦想常常只能实现一半，我本应是个“飞人”，却由于航班延误，经常呆在“地上”。尤其是遇到北京的冬天和上海的夏天，雾霾和梅雨常常让准点飞行都成了奢望。

当遇上航班大面积延误，作为乘客的DT君也只能干着急。

（图片说明：DT君今年的部分空中痕迹，横跨祖国南北，雾霾、梅雨什么的简直是DT君的航班克星。）

面对航班大面积延误恢复问题，航空公司其实比DT君更着急。极端的天气状况、运营的调配困难、飞机故障等问题，都有可能导致机场出现大面积航班延误。一旦出现这种问题，航空公司所承担的损失也非常巨大。比如地处东南沿海的厦门航空公司，就深受其扰。

厦航目前使用辅助人工决策的航班调整系统处理航班计划，但在台风等极端天气对多基地运行造成影响的情况下，仍需要6小时左右才能将航班计划梳理完毕。随着运力的增长以及运行环境的日益复杂化，后续航班大面积延误情况下，需要更长的时间梳理航班计划，这显然不能满足对运行的快速响应需求。

为了缩短航班计划恢复时间，必须有一套更智能、更科学的航班自动恢复系统算法，当遇到大规模延误时，能够自动对航班进行快速调整，快速恢复航班计划，并有效优化公司的运营成本。

要开发这样一套满足要求的人工智能算法可并不容易。航班延误恢复问题是一个真正的世界级难题，目前没有哪些航空公司能够有效解决它。

让更多的大数据人才参与进来或许是一个突破口。2017年6月，厦门航空联合阿里云举办智慧航空AI大赛，把这个“世界级难题”放在天池大赛的平台上，交给了众多数据侠来群策群力。

（图片说明：厦门航空总信息师王洪建在现场观看选手答辩）

厦门航空总信息师王洪建称，“这是大数据及人工智能在航空领域的一次重大尝试”。来自全球17个国家和地区的1664支团队参加了比赛，最终5支团队脱颖而出，进入最后的决赛。

条条算法通罗马，延误再多也不怕

在这次天池智慧航空AI大赛中，厦航提供了脱敏后的真实业务数据，考题的设置也是依托运营中出现的实际情况而来。这对于数据侠们来说是一次真刀真枪的“实战演练”。

归根结底，数据侠就是要在航班大面积延误后，提供一套“恢复算法”，能够自动指导相关航班进行调整，使得受影响的航班旅客尽快疏散，未受影响的航班运行受影响最小，且恢复的综合成本最低。

由同济大学经管学院梁哲教授带领的“同济经管优化”队，建立了基于列生成（column generation）框架求解的连接网络模型，创新地改进了行列生成算法（column-row generation），克服了传统时空网络只能采取离散延误策略的弊端。通过模型求解器结合遗传算法、禁忌搜索算法和标签算法，迅速求解该大规模整数规划问题，精确求解了航班延误时长以及签转大量航班取消的旅客。

数梦工场团队的解决方案则是大领域搜索（Large Neighborhood Search，LNS）与混合整数线性规划（Mixed Integer Linear Programming，MILP）。通过MILP模型可以精确地表达竞赛提出的问题，但由于数量大，工程上无法直接求解 。用LNS框架每次只取一部分飞机和航班计算，可以实现快速迭代，在合理时间内获得满意的结果。

（图片说明：数梦工场团队在答辩现场展示团队的算法过程）

来自新加坡的博士后夫妻组合“坡村坑U”，采用三阶段迭代优化法来解决问题，步步为营。第一个阶段主要优化飞机路径和航班时间；第二阶段固定飞机路径，在精确考虑乘客取消、乘客延误、普通乘客转签的前提下，优化航班时间和乘客安置；第三阶段固定飞机路径和航班时间，总体优化乘客成本。

（图片说明：“坡村坑U“团队在答辩现场展示团队的算法过程）

虽然各个团队使用的算法不尽相同，但是在解决实际问题方面都取得了非常好的预期效果，差别并不太大。

厦门航空运行指挥部副总经理林晴表示，如果将选手提出的算法方案应用在实际业务中，预期可以将航班大面积延误恢复的时间，降低一个数量级，从小时缩减到分钟。

以竞赛的方式解决社会问题，让数据落地

答辩时，同济大学的梁哲教授很是感慨。他从硕士时就开始研究航空优化问题，当时导师告诉他说，这些研究一定会有用的。结果一等就是15年，直到今天（天池大赛）才真正把研究应用到实际业务中。

（图片说明：梁教授和他的团队最终获得这次比赛的第一名）

这么说虽然有些夸张，但是至少可以看出，过去学界和业界之间的联系不太紧密。这次天池的参赛队伍绝大部分来自高校和科研单位，有72%具有硕士及以上学位。一直以来，学界往往有丰富的人才储备，和前沿的算法研究，却距离实际业务较远。

另一方面，诸如厦航等公司往往在实际业务中积累了大量的数据和问题，但没有时间和精力去优化业务。在大数据时代，双方合作的模式已经成为不可避免的大趋势。

马云在云栖大会上也说到，在数据时代，企业家和科学家的完美结合，才有利于社会的长远发展。阿里巴巴甚至投入了1000亿元成立“达摩院”，整合学界和业界资源。

回到这次智慧航空大赛，如果这些算法要应用到厦航真实的业务场景中，还需要添加更多的数据维度限制，也就是说还有很大距离。但林晴副总经理告诉DT君，这些人工智能算法未来若跟厦航业务相结合，将极大提升大面积延误情况下航班恢复效率。

（图片说明：所有决赛团队在云栖大会合影）

将企业问题放到天池平台上，用实战数据邀请社会范围内的数据侠群策群力，以竞赛的方式解决社会问题，DT君认为这是一个让数据落地的积极尝试。

最终，梁哲教授带领的“同济经管组合优化队”取得了本届大赛的冠军。想知道这套算法最后是否真的能够应用到厦航的系统中，等下次再当“空中飞人”的时候，不妨亲自感受一下厦航的航班吧。

加入数据侠

数据侠计划是由第一财经旗下DT财经发起的数据社群，包含数据侠专栏、数据侠实验室系列活动和数据侠联盟，旨在聚集大数据领域精英，共同挖掘数据价值，投稿、合作请联系[email protected]。