东航最新算法分析运筹调度、收益管理到智能服务的底层逻辑每年春运、暑运高峰期航空公司的运行控制中心几乎就是一个大型实时算法实验室。航班计划怎么编排、飞机怎么排班、机组怎么搭配、票价怎么浮动、值机怎么选座这些看起来是业务决策的问题背后全是算法在支撑。东航这类大型航司算法体系横跨运筹优化、机器学习、数据挖掘和实时计算好几个领域。这篇文章不聊空泛的概念直接拆解航空公司尤其是东航这类体量下“算法”到底在哪些环节起作用、用的是什么类型的算法、为什么这么选以及实际落地时会踩哪些坑。适合对算法感兴趣的技术人、航司信息化从业者以及想理解“机票背后逻辑”的行业观察者。很多人以为算法只存在于互联网大厂的推荐系统和搜索引擎里其实航空业才是算法应用最密集的行业之一。一次航班从计划到执行涉及机型分配、机组排班、飞行路径规划、地面滑行调度、旅客需求预测、动态定价、超售计算、延误恢复等多个环节每一个环节都有明确的算法模型。东航机队规模大、航线网络密、运行链条长算法价值尤其突出。下面我按业务链路逐个拆。1. 航班调度与运筹优化算法先把骨架搭出来1.1 航班编排排序、时间窗和冲突消解航班计划是航空公司的骨架。什么时候飞、用什么机型飞、在哪个机场过夜这些都要提前排好。排航班计划看起来只是“列个表”实际上是一个带大量约束的组合优化问题。最简单的约束包括同一架飞机相邻两个航班之间必须有足够的过站时间机场跑道有容量限制热门时刻有航班时刻限制即时刻资源机组有执勤期和休息期限制。把这些约束写进模型后航班编排本质上变成了一种带时间窗的路径规划问题。日常看航班计划时排序算法是最直觉的底层工具。做过运维的同学都接触过快速排序、归并排序、堆排序在航班编排的预处理阶段排序同样是最常用的操作。比如把某个机场一天的所有起降事件按时间排成序列快速排序轻松搞定复杂度O(n log n)足够用。但真正难的不是排序本身而是排序之后的冲突消解。两个航班同时想用一条跑道机场容量只有那么多谁先谁后、后移多久这就不是单靠排序能解决的需要引入约束规划或整数规划。再往深走一步航班编排里经常用到贪心算法的思想但真正的“最优解”几乎不可能靠纯贪心拿到。贪心算法在每步都选当前最优比如先安排收益最高的航班、把最紧俏的时段给宽体机但局部最优加在一起常常不是全局最优。这里的主流做法是把问题建模成混合整数线性规划国内很多航司的信息部门在航班计划阶段直接采购商业求解器东航在这类场景下也有大量自研系统配合商业引擎做二次开发。混合整数线性规划听上去很高大上拆开理解就是一部分变量必须是整数比如一架飞机只能分给一条航线、一部分变量是连续值比如起飞的精确分钟数目标函数是最大化收益或最小化成本。1.2 飞机排班与机组排班组合优化的真实战场飞机排班业内叫 aircraft routing核心目标是给每一架飞机指定一条由若干个航班首尾相接的路径保证飞机既能完成所有计划航班又要满足定检维修的时间窗口同时尽量少地引入延误。这个问题的规模非常大东航几百架飞机对应几千个航班段解空间是指数级的暴力枚举根本不现实。主流解法是把它拆成多个阶段先用启发式方法生成候选路径再用集合划分模型选出最优组合。初学者最容易在这个地方想到“动态规划”。动态规划确实能解决很多序列决策问题比如一个机组一周内怎么排班最合理、飞行时间怎么分配这类带有状态转移特征的子问题用动态规划很顺手。但真实场景里约束实在太多机长和副驾驶的资质搭配、每月的飞行小时上限、特殊机场的资质要求、机场过夜资源限制。动态规划的状态维度会被这些约束撑爆所以实际工程中更多是分支定界法配合列的生成。机组排班是另一个被当作“行业密码”的难题。它和飞机排班在数学上很相似却多了大量和“人”有关的规则约束。空勤人员排班要考虑连续执勤时间、跨时区休息、特殊机场资质、培训复训、休假申请。这类问题在运筹学里叫人员排班问题常用的做法是构造一个带时间线的网络图把每个飞行任务当作网络中的一段弧然后在这个网络上跑最短路径算法来生成候选值勤再通过集合覆盖模型选最优。弗洛伊德算法、Dijkstra算法这类最短路径算法在这里是基础工具但不是单独用而是嵌入在更复杂的框架里。如果你自己动手做一个小型的飞机排班模拟我的建议是先从匈牙利算法入手。匈牙利算法解决的是任务分配问题假设有N个航班段和N架飞机每架飞机执行每个航班段的成本已知怎么让总成本最小这个问题的标准解法就是匈牙利算法复杂度O(n^3)几百个节点以内的场景跑得非常快。东航这种规模当然不会是简单的N对N但理解匈牙利算法能帮你建立一个“分配问题”的心智模型后续再看分支定界、列生成就不会云里雾里。1.3 为什么不是“一个万能算法”搞定一切很多人好奇东航这么大一个系统为什么不训练一个万能模型把排班、定价、调度全做了答案很现实因为算法各有边界。排班问题是标准的离散组合优化求解器最擅长需求预测是连续值回归问题机器学习模型更合适定价是带约束的最优化问题又得回到运筹优化。没有任何一个算法能同时在离散、连续、不确定三类问题上做到最优。这里有一个重要的经验工程上从来不追求“理论上绝对最优”因为模型的假设永远赶不上现实变化。比如航班编排时使用了混合整数线性规划理论上能解到全局最优但实际中求解时间可能长达几小时等它算完航班都要起飞了。所以工程上普遍的做法是设置一个时间上限比如求解10分钟如果还达不到最优就给一个“可接受次优解”。这个“次优解”质量好不好取决于启发式策略和求解器的参数调节非常吃经验。2. 收益管理与定价算法决定同一架飞机卖多少钱2.1 需求预测机器学习算法在前面开路机票价格不是成本加成定出来的而是根据需求预测动态调出来的。同一架飞机同一个舱位提前一年买和当天买价格完全不同这里面靠的就是收益管理系统。收益管理的第一步是需求预测需要预测每个航班在未来每个时间点可能卖出多少张票。时间序列模型、回归模型、随机森林这类经典机器学习算法都会派上用场。东航的航线覆盖国内外每一条航线都有几十年积累的历史销售数据这种大样本数据非常适合跑随机森林回归、梯度提升决策树这类成熟的监督学习算法。随机森林回归的思维很好理解从历史数据中抽很多组样本分别训练多棵决策树每棵树给出一个预测值最后取平均。相比单个决策树它大幅减少了过拟合。航班需求预测中特征通常是提前购票天数、星期几、是否节假日、有无重大活动、历史同期的销售曲线、竞争对手票价等。数据清洗比算法本身更费时间尤其是每年换季后的数据标签要重新对齐。说句大实话这类预测模型只要特征工程做扎实、历史数据干净哪怕用最朴素的线性回归也能拿到七成以上的效果用了随机森林更多是提升对非线性关系的拟合能力。需求预测做完还要做“无约束需求还原”也就是把因为航班售罄而损失的潜在需求估算出来。这一步在很多资料里不提但它直接影响后续定价的准确性。常用的做法是期望最大化算法EM算法结合概率分布假设把被截断的销售数据恢复到真实需求分布。这个过程比较偏统计很多人第一次接触会觉得绕但它确实是收益管理从“拍脑袋”走向“算法化”的关键一步。2.2 动态定价与舱位控制增量式PID和模拟退火的组合玩法有了需求预测曲线下一步就是决定每个舱位价格和剩余座位数量。传统做法是预先划分若干个舱位等级比如Y舱全价、B舱九折、M舱八折系统按照每个舱位的库存上限来控制销售。这个库存控制本身就是一个动态规划问题剩余座位还剩多少、距离起飞还有多少天、当前卖出速度如何这三个变量共同决定要不要开放更低折扣的舱位。很有意思的一点是日常工程师都很熟悉的PID控制算法在仓位控制里能找到影子。增量式PID的核心思想是根据偏差的变化量来调整输出让系统平稳逼近目标。收益管理系统每隔一段时间检查一次当前销售速度与预测速度的偏差如果销售快于预期就减少低价舱位放量等价于调整输出的增量而不是直接调到目标值。这样做的好处是避免价格大幅波动吓跑旅客也让票价曲线更平滑。虽然航司内部不会直接说自己用的是PID但这个控制逻辑确实高度相似。当市场环境变化剧烈比如某个热门航线突然出现大量搜索需求或者竞争对手大幅降价固定舱位控制就不够了。这个时候需要用更灵活的动态定价用算法直接算出当前时刻的最优价格。这类问题常被建模成一个带约束的最优化问题求解手段五花八门模拟退火算法就是一个典型代表。模拟退火的核心是允许以一定概率接受“更差”的临时解从而跳出局部最优。放到定价里就是哪怕当前价格已经是观测到的较好价格算法也会尝试向上下两个方向试探通过不断迭代逼近全局最优。东航这类大航司在定价策略上的调参经验非常关键温度系数、迭代次数、邻域搜索步长都会直接影响最终价格建议的质量。2.3 超售模型增量收益和概率风险的对赌超售是航空业算法应用里最经典也最敏感的一块。道理很简单一定比例的人会退票或改签如果按座位数卖票就得空着飞不如多卖几张赌一把实际成行人数不超过座位数。这里面的数学基础是概率论和统计学。最朴素的做法是假设每个旅客的成行概率独立且相等用二项分布计算多卖1张、2张、3张票时的超售成本和溢出收益。当然实际情况复杂得多退改签概率和票价水平、旅客类型、天气、日期类型都有关系一个成熟的超售模型往往用随机森林或梯度提升树来预测每个订单的取消概率再做蒙特卡洛模拟算出不同超售数量下的收益分布。在做超售模拟时蒙特卡洛方法的思路就是把“未来不确定性”变成上万个随机场景每个场景里随机决定哪些旅客会取消然后统计收益分布。这个方法的计算量比较大但胜在直观可信。东航这类超大规模航司每天要处理的航班量很大超售模型不能太复杂否则运行时间不可控所以工程上常见的是“离线训练一个取消概率模型 在线用期望值公式快速计算”。这里不需要盲目追求深度学习等复杂模型反而要控制模型复杂度和线上性能的平衡。3. 运行控制与延误恢复算法飞机和旅客都要“重新排”3.1 最短路径算法与机场地面滑行优化航班在空中飞行的路径属于空管管理航司自身能优化的是机场内的滑行路线。但滑行路线优化在行业内是有的。以前飞机落地后塔台给出滑行指令飞行员照着滑就行现在很多枢纽机场运行控制会用算法推荐最优滑行路径减少滑行时间和燃油消耗。这类算法很经典本质上就是在一个有向图上找最短路径。机场的滑行道、跑道、停机坪构成图结构节点是滑行交叉口边是滑行道的长度或预计滑行时间然后跑Dijkstra算法或弗洛伊德算法。东航在浦东、大兴这类大枢纽的场内调度飞机多、廊桥资源紧张滑行路径的优化能实打实地节省燃油成本、降低延误。不过真实环境下的滑行优化比教材里的最短路复杂得多。机场同一时间有几十架飞机在滑行两条滑行道可能交汇如果所有飞机都走各自的最短路径就可能造成新的冲突。因此实际的滑行优化通常要叠加时间维度和冲突检测变成一个动态路径规划问题。这也是为什么很多系统里直接用A算法而不是单纯的Dijkstra因为A加入启发式函数后能在带约束的图上更快找到可行路径。启发式函数的选择是算法工程师真正花时间调的地方太乐观的启发式会搜索过慢太保守的启发式又可能错过最优路径。3.2 航班延误恢复匈牙利算法、网络流和近似解航班延误是任何一个大型航司都躲不开的难题。如果某个枢纽机场因为极端天气关闭一小时几十架飞机滞留在原地几百个后续航班全乱套。这时候只有两个选择要么全部往后顺延后续全是连锁延误要么做一次“航班重新分配”的运算让跑到一半落不了地的飞机和旅客尽量按原计划走。这个重新分配的过程在运筹学里叫“航班恢复问题”是典型的组合优化模型约束比日常排班更多而且必须在几分钟内算出可用方案。航班恢复的常见建模方式是构建一个时空网络横轴是时间、纵轴是机场每个机场在每个时间段形成一个节点。飞机从一个节点飞到另一个节点就是一条边。在这个网络里找一组路径让尽可能多的航班按原时间执行就是核心目标。求解时先做延误传播分析这个可以用拓扑排序再用匈牙利算法处理飞机和航班的匹配问题最后用混合整数规划做全局寻优。你可能注意到我又提到了匈牙利算法没错它确实是航班恢复中的“高频工具”。当一组飞机因为延误困在几个不同机场而另一头正好有对应的航班任务需要匹配时这就是典型的任务分配问题。匈牙利算法在几百架的规模下解起来很快能给出一个不错的初始解。后续需要在这个初始解上做局部优化比如交换两架飞机的后续任务或者整体平移某个航班链这些操作可以用模拟退火或遗传算法做邻域搜索。核心思路是先用确定性的组合优化算法拼一个“不差”的解再用启发式算法慢慢打磨。3.3 大面积延误下的飞机重新分配算法大面积延误是任何一个大型航司都躲不开的难题。如果北京、上海这种核心枢纽因为极端天气关闭几个小时几十架飞机滞留原地连续引发几百个后续航班乱套。这时候不可能靠人工慢慢排延误恢复算法必须在几分钟内输出一套可执行的调整方案。我在实际项目中遇到过类似场景第一版方案就是直接把飞机和航班当作二分图跑匈牙利算法速度快但解质量很糙经常出现一架飞机刚飞完一个航班就要立刻跨机场接下一个航班过站时间根本不够。后来加了一步约束预处理把所有不满足最小过站时间的候选对提前删除再跑匈牙利算法解的质量立刻上了一个台阶。这个经验特别适合刚接触航班恢复的工程师不要着急上复杂求解器先把约束条件梳理清楚、把候选集合缩小很多问题用经典算法就能解掉。再往深一层大面积延误时飞机的机型和维修要求也会掺进来。宽体机不能随便替换窄体机有些机场不允许某种机型夜宿这些硬约束让那些在“裸模型”下跑出的解直接废掉。东航这类大航司的解法通常是建立多梯队方案第一梯队用启发式规则快速生成可行解第二梯队用混合整数规划在可行解基础上优化第三梯队再由人工专家做微调。为什么需要人工微调因为算法不知道某个机场今天的地勤人手特别紧张也不知道某条航线有重要政务客人在等这类隐性信息很难全部编码进模型里。4. 数据算法与智能服务从值机选座到会员运营4.1 值机选座背包算法与旅客偏好的平衡值机选座看起来是个小功能背后也有算法逻辑。经济舱座位分配要满足旅客偏好比如靠窗、靠过道、靠前、紧急出口旁还要平衡飞机配载确保重心在安全范围内。这里头有两个算法思路值得说一是把座位分配当多目标优化旅客满意度尽量高配载偏离尽量小二是把紧急出口座位特殊处理因为这类座位有安全要求不是谁想坐就能坐。从算法实现上看座位分配可以建模成背包问题。飞机上有200个座位旅客有200个需求每个旅客分配到不同座位会产生不同的满意度分数同时每个座位对飞机重心有不同影响在重心约束下最大化总满意度就是带约束的背包问题。动态规划是求背包问题精确解的经典方法但机上座位数量达到两三百旅客数量相同且偏好多维时动态规划状态数爆炸实际工程里更多是写贪心局部交换的启发式算法先把最敏感的需求比如残疾人旅客、婴儿旅客固定下来再按紧急出口、前排、靠窗等优先级一层层往里填。这个过程中还要考虑实时计算性能。开放值机后旅客随时在选座算法不能每次都对全舱重新跑一遍优化那样数据库和计算资源都扛不住。常见做法是把“可分配座位区间”预计算好旅客选座时只在他所属的区间内做快速判断。这个预计算和实时计算的配合是值机系统架构里比较考验人的地方。“预计算能用离线任务解决就绝不放线上跑”这是我做了多次实时推荐类系统后最深的感触。4.2 会员画像与推荐算法从协同过滤到深度模型东航有自己的会员体系“东方万里行”会员几千万这些用户每天都在产生行为数据搜索过哪些航线、买过什么舱位、常去哪些城市、是否有升舱偏好。这些数据汇集起来可以做用户画像和个性化推荐。传统做法用的是协同过滤算法核心逻辑是“和你类似的人还买了什么”。用户A和用户B的历史行为相似度可以用余弦相似度算出来然后给A推荐B买过但A没买的航线产品。协同过滤实现简单、效果稳在很多场景里是首选基线模型。但协同过滤在航空场景有个天然短板数据稀疏。一个人一年可能只飞几次行为数据远远没有电商平台的点击数据稠密。这时候可以引入聚类算法和分类算法。聚类算法比如K-Means能把用户按出行频次、舱位等级、航线偏好分成若干群体同一群体共享画像特征分类算法比如逻辑回归或梯度提升树可以预测某个用户未来三个月是不是有出行需求、更可能飞国内还是国外。近几年深度学习算法也在慢慢进入航司的推荐系统。这里有个认知误区不要因为深度学习效果好就哪儿都用。航空用户的行为序列短很多人的历史记录只有短短几行深度学习模型很容易欠拟合或过拟合。我自己踩过坑后总结的经验是先用经典的机器学习算法随机森林、逻辑回归、协同过滤建基线只有当基线的离线指标到了瓶颈且样本量足够大时才值得尝试深度模型。否则就是花了更多算力效果却更差。4.3 智能客服与语义算法从检索到生成的进化东航的客服体系每天要处理大量旅客咨询退改签政策、行李限额、航班动态是最高频的问题。早期智能客服依赖规则匹配和关键词检索准确率和用户体验都比较差。后来引入基于向量检索的语义匹配把用户问题转换成向量再和知识库里的标准问题做相似度计算相关度高的答案直接推给用户。这个思路的本质是文本语义相似度算法常用的有BM25、Sentence-BERT等底层用的是自然语言处理领域的词向量和注意力机制。再往后就是大模型和生成式AI。这两年大家都在讨论大模型能不能落地航空公司场景我的观点是确实能但要选对切入点。比如让大模型直接回答机票退改政策风险很高因为政策更新非常频繁大模型的生成结果不可控容易一本正经地胡说八道。更稳妥的落地方式是RAG框架检索增强生成先从权威知识库检索出相关政策片段再把片段塞给大模型做总结归纳这样生成内容有据可循。东航这类大航司如果要在智能客服场景用大模型十有八九会走这个技术路线而不是直接微调一个行业大模型。4.4 数据结构与算法基础仍然是地基聊完这么多复杂的应用算法我还是想强调一点所有高级算法都建立在数据结构的基础上。KMP算法解决的是字符串匹配问题用在用户搜索航线号、订单号等场景归并排序和堆排序用在海量日志排序、Top K统计二分查找用在有序价格列表快速查询剪枝算法用在搜索范围缩小。这些都是最基础的数据结构与算法内容看起来不起眼实际每天都在航司的各个系统里跑着。所以我经常给团队的初中级工程师一个建议不要因为业务系统里有大模型、有求解器就觉得基础算法没用了。恰恰相反基础不牢后面学任何高级算法都容易飘。比如做延误恢复时先生成几千个候选航班链每个航班链后续要排序、过滤、拼接这里头每一步都在用排序算法、查找算法和树形结构。一旦数据量上来选择合适的数据结构可能比选择高级算法策略带来的性能提升还明显。哈希表把O(n)查找变成O(1)线段树把区间查询从O(n)变成O(logn)这些提升在日常系统里是秒级和毫秒级的差别。5. 实操心得从“看得懂”到“能落地”的三个建议把气象预测、用户行为数据和运行限制结合起来做一个延误概率模型提前把可能延误的航班关联的飞机、机场、机组都标记出来。这里推荐用强化学习来持续优化恢复方案。PPO、DQN这类强化学习算法近几年在调度场景有了不少真实落地。传统优化算法是一次性给出方案强化学习则是不断和环境交互、根据反馈调整策略。放到航空场景里就是算法每次给出一个调整方案仿真环境模拟执行结果计算延误成本算法根据这个奖励信号不断改进自己的策略。东航这类大航司如果未来在航班恢复上实现“有自我优化能力的算法”大概率会沿着这个方向走。如果你现在刚开始接触航空算法我给你三个实操建议第一先把数据结构和经典算法吃透。洗数据、写预处理、做特征工程这些工作里全是基础算法的影子。之前我做过一个航班准点率分析任务原始数据有几千万条第一版用Python列表加双重循环去重、统计跑了一个小时后来改成哈希表归并排序的思路两分钟就跑完。同样是一个指标数据量上来后算法设计的差距是几十倍。第二遇到一个业务问题先试最简单的方法。很多人在做收益管理时一上来就想上深度强化学习结果连稳定的销售数据都没有聚合好模型训练出来完全不可用。更好的路径是先用线性回归或随机森林这类成熟算法建立基线跑通全链路后再逐步升级。这就像搭房子先把毛坯房搭好住进去再精装修而不是先买一堆昂贵材料堆在空地上。第三不要忽略约束条件和人工经验。航空公司运行场景有大量隐性规则比如某些特殊旅客不能安排在高风险座位、某些航线不能使用某类机型夜航这类约束很难在教科书模型里找到。务必让业务专家深度参与模型设计把他们的经验转化为规则项或约束项。算法真正发挥作用的部分往往是那些“人工处理太慢”的场景而模型是否可用的底线永远由业务约束决定。忽视这一点再精妙的算法也只能停留在PPT演示阶段。算法在航空业不是单点突破的应用而是一整套互相咬合的系统工程。从运筹优化到机器学习从经典数据结构到大模型每一个环节都在为同一个目标服务让航班飞得安全、让旅客走得更顺、让航空公司运行得更高效。把这一点想清楚再回头去研究具体算法你会有完全不同的理解。