遗传算法+神经网络：登机效率超越Steffen法9.6%

一个被反复研究的老问题：如何更快登机

飞机登机（boarding）看似简单，却是一个经典的组合优化难题。每当乘客在过道里为放置行李、寻找座位而停顿，整架飞机的登机进度就会被拖慢。对航空公司而言，缩短登机时间意味着更高的飞机周转率和更低的运营成本——飞机停在地面的每一分钟都是成本。

从学术角度来看，飞机登机问题在运筹学和计算机科学中被归类为NP-hard问题的变体。自1998年Van den Briel等人首次将其形式化建模以来，已有超过200篇学术论文探讨此问题。该问题的核心挑战在于：它既是一个排序问题（确定乘客登机顺序），又是一个动态系统模拟问题（乘客之间存在实时交互和阻塞）。这使得传统的线性规划等精确方法难以直接应用，因为目标函数无法写成封闭表达式，必须通过模拟来评估每种方案的效果。

根据航空业的经验数据，一架窄体客机（如波音737或空客A320）每在地面多停留一分钟，成本约在30到150美元之间，具体取决于机场停机费、机组人员工时、燃油APU消耗等因素。这里所说的APU（Auxiliary Power Unit，辅助动力装置）是飞机在地面时为客舱提供电力和空调的小型涡轮发动机，每小时消耗约200-400磅航油。除APU外，地面成本还包括机场按分钟计费的廊桥/停机位使用费、地勤人员的工时成本、以及因延误产生的连锁效应——一个航班的延误往往像多米诺骨牌一样影响后续航班。波音公司2019年的一份内部研究指出，全球航空业每年因低效登机损失的经济价值超过10亿美元。

美国航空咨询公司估算，如果一家大型航空公司能将每次登机时间缩短哪怕一分钟，年节省金额可达数千万美元。这也是为什么航空公司长期投入资源研究登机策略，尽管最终往往因旅客体验和执行复杂度而妥协于"分区登机"（zone boarding）等次优但易于管理的方案。

多年来，研究者提出了各种登机策略。其中最著名的当属Steffen 方法（Steffen Method）。这套方法由物理学家 Jason Steffen 在 2008 年通过优化算法提出，其核心思路是：让乘客按照特定的交错顺序登机，最大化同时放置行李的人数，从而减少过道拥堵。

具体来说，Steffen方法的操作方式是：乘客按照从窗户到过道（Window-Middle-Aisle）的顺序，同时在每一列中采用间隔交错的方式登机。例如，先让所有偶数排的窗户座位乘客登机，再让奇数排的窗户座位乘客登机，依次类推。这种设计的精妙之处在于，当多位乘客同时进入机舱时，他们的座位彼此间隔足够远，可以同时在不同行的头顶行李舱放置行李，互不干扰。

Jason Steffen本人是一位在费米实验室工作的粒子物理学家，他用蒙特卡洛优化方法（一种通过随机采样逐步逼近最优解的技术，广泛应用于统计物理和计算科学）得出了这一结论。他的创新之处在于将物理学中成熟的优化工具跨学科应用到运筹学问题上。2012年，电视节目《MythBusters》（流言终结者）邀请Steffen使用一架真实的波音757模型和72名志愿者进行对照实验，结果Steffen方法比从后往前登机快约2倍，比随机登机快约20-30%。不过该实验也暴露了一个问题：志愿者需要严格按照指定顺序排队，任何一人的位置偏差都会显著降低效率。

在多次实验和电视节目的实测中，Steffen 方法都被证明显著优于常见的"从后往前"或"随机登机"策略，成为学术界公认的效率标杆。

正因为 Steffen 方法长期被视为"接近最优"的基准，一位 Reddit 开发者最近的成果才显得格外引人注目。

用遗传算法"进化"出更优的登机顺序

据这位开发者在 Reddit 上的分享，他采用遗传算法（Genetic Algorithm）结合多层感知机（Multilayer Perceptron, MLP）的组合方案，对登机问题进行优化，最终在模拟中跑出了比 Steffen 方法快 9.6% 的结果。

这套方法背后的思路值得拆解：

遗传算法：模拟自然选择的策略搜索

遗传算法是一类受生物进化启发的优化算法。它将每一种可能的登机顺序编码为一个"个体"（染色体），通过选择、交叉、变异等操作，在一代代"繁衍"中筛选出表现更好的方案。适应度函数（fitness function）通常设定为登机总耗时——耗时越短，个体越"优秀"，越有机会将自己的"基因"遗传给下一代。

这三个核心操作各有其技术含义：选择（Selection）是根据适应度从当前种群中挑选优秀个体作为"父代"，常用的方法有轮盘赌选择和锦标赛选择；交叉（Crossover）是将两个父代个体的基因片段重新组合生成子代，对于排列编码问题通常使用顺序交叉（OX）或部分匹配交叉（PMX）以避免重复元素；变异（Mutation）则是以小概率随机改变个体中的某些基因位，如交换两个位置的值，以维持种群多样性、避免陷入局部最优。对于登机问题这种排列优化场景，编码方式本身就是一个挑战——每个乘客只能出现一次，这使得标准的二进制编码不再适用，必须采用排列编码并配合专门的交叉算子。

在登机问题的具体实现中，遗传算法的种群规模通常设定为数百到数千个个体，每个个体代表一种完整的登机排列。典型的进化过程会运行数百代到数千代。一个关键的技术决策是精英保留策略（elitism）——将每一代中最优秀的若干个体直接复制到下一代，确保最佳解不会因随机操作而丢失。此外，自适应变异率也很重要：在进化早期使用较高变异率促进探索，后期降低变异率促进收敛。

登机顺序的搜索空间极其庞大：对于一架上百座的飞机，可能的排列组合是天文数字（例如180个座位的排列数为180!，约为10^325），穷举根本不现实。遗传算法的优势恰恰在于能在这种巨大空间中高效地逼近优质解，而不必遍历所有可能。尽管搜索空间达到10^325，但由于适应度景观中存在大量结构性规律（如窗户优先、间隔登机等模式），遗传算法通常能在合理时间内收敛到高质量解。

多层感知机：为策略提供决策能力

单纯的遗传算法搜索的是固定的登机序列，而作者引入多层感知机后，相当于让神经网络参与决策——网络可以根据乘客的座位、行李等特征输出登机优先级，遗传算法则负责优化这个网络的参数。

多层感知机（MLP）是最经典的前馈神经网络结构，由输入层、一个或多个隐藏层和输出层组成，每层之间全连接。在本项目中，MLP的作用是作为一个"策略函数"：输入乘客的特征（如行号、列号、是否携带大件行李等），输出一个优先级分数，所有乘客按分数排序即得到登机顺序。这意味着网络学习到的不是某一种固定排列，而是一套通用的优先级规则——例如，它可能学会"行号较大且靠窗的乘客应获得更高优先级"这类抽象策略，并能将此逻辑泛化到不同的乘客配置中。

这种"进化神经网络"（neuroevolution）的思路，让策略具备了更强的泛化与适应能力，而不只是死记硬背一个固定顺序。神经进化是指用进化算法代替梯度下降来优化神经网络的权重或结构。这种方法的优势在于不需要可微分的损失函数——登机时间这类离散的、通过模拟得出的、难以求导的目标正适合这种方式。

神经进化方法有着丰富的技术谱系。最早可追溯到1980年代末，但真正引起广泛关注是2002年Kenneth Stanley提出的NEAT算法（NeuroEvolution of Augmenting Topologies），该算法不仅进化网络权重，还能进化网络拓扑结构。2017年OpenAI发表的论文证明，简单的进化策略（Evolution Strategies）在Atari游戏和MuJoCo控制任务中能达到与深度强化学习相当的性能，且具有更好的并行化特性。Uber AI Lab同期的工作则证明遗传算法在某些强化学习任务中甚至能超越梯度方法。在本登机项目中，使用进化而非梯度下降来优化MLP的合理性正在于：登机时间是通过离散事件模拟得出的标量值，无法对网络参数求梯度，而进化算法只需要能评估每个方案的好坏即可。

9.6% 的提升意味着什么

作者坦言，他"原本并没有预期能击败 Steffen 方法"，但进化出的策略最终实现了 9.6% 的提速。这个数字在工程上并非微不足道。

以一次典型登机 25 分钟为例，9.6% 的提升意味着节省约 2.4 分钟。放大到一家大型航空公司每天成千上万个航班的规模，累计节省的地面时间足以转化为可观的经济价值和更高的准点率。

有意思的是，作者提到模拟中设置了一条约束规则：禁止乘客在座位之间相互穿越（no crossing between seats），这一约束同样适用于随机基准。这一点很关键——现实中乘客确实无法凭空穿越彼此，加入这类物理约束能让模拟更贴近真实场景，也让 9.6% 这个结果更有说服力。

"Vibecoded" 项目的启示与局限

作者形容整个项目"基本上是 vibecoded 出来的"——即凭借直觉和实验性的、较为随性的编码方式完成，而非严格的学术流程。这恰恰反映了当下 AI 工具普及带来的一个趋势：个人开发者借助现成的算法框架和 AI 辅助编程，也能在经典优化问题上做出有意义的探索。

不过，我们也应理性看待这一成果：

• 模拟 ≠ 现实：9.6% 的提升来自作者自建的模拟环境，其参数设定（行李放置时间、乘客移动速度、约束条件等）会直接影响结果。不同的模拟假设可能得出不同结论。学术界对登机问题的模拟通常采用离散事件仿真或元胞自动机模型，最常用的框架将机舱过道建模为一维网格，每个格子对应一行座位。乘客按顺序进入过道，每个时间步可以前进一格（如果前方无阻塞）或保持静止。当乘客到达自己所在行时，需要花费一定时间放置行李（通常为Uniform(5,25)秒或类似分布）。座位干扰（seat interference）是另一个重要因素：如果乘客需要到达靠窗座位，而同排的过道座位已有人就座，那么已就座乘客需要起身让路，额外消耗约10秒时间。这些参数的微小变化都可能显著改变不同策略之间的相对排名。
• 缺乏同行评审：作为一个 Reddit 分享的个人项目，尚未经过学术界的严格复现与验证。Steffen 方法本身也是在特定模型假设下最优，两者的比较需要建立在一致的基准上才公平。
• 落地可行性存疑：Steffen 方法虽然理论优秀，但因要求乘客严格按复杂顺序登机，在现实中难以推行。学术研究表明，当乘客遵从率降至70%以下时，几乎所有精心设计的登机策略都会退化为接近随机登机的效果。任何进化出的新策略若比 Steffen 更复杂，同样会面临"乘客不配合"的落地难题。此外，现实中还有大量学术模型难以涵盖的因素：优先登机是常旅客计划和信用卡合作的核心权益，头等舱和商务舱旅客必须先登机；带小孩的家庭通常被允许提前登机；随着航空公司开始对托运行李收费，乘客携带更大手提行李的趋势加剧了对头顶行李舱空间的争夺，导致部分乘客试图尽早登机以确保存放空间。这些商业和人为因素使得任何"最优"策略在实际部署时都必须大幅妥协。这也是为什么大多数航空公司至今仍采用简单的分区登机或随机登机方式，而Southwest Airlines采用的开放式选座加分组登机被业界认为是效率和体验的良好折中。

结语：AI 优化经典难题的又一个样本

无论最终结论如何，这个项目都是一个生动的案例，展示了进化计算 + 神经网络在组合优化问题上的潜力。它提醒我们，即便是被研究多年、被认为"接近最优"的经典方法，在新的算法工具面前也可能还有改进空间。

对于希望入门优化算法的开发者来说，登机问题是一个绝佳的练手场景：问题定义清晰、有公认基准可对标、结果直观易懂。而 AI 辅助编程的普及，正在让这类探索的门槛越来越低。或许下一个打破基准的方案，就来自某个业余爱好者的周末项目。