关于本文

译文，原文是 john.fun/elevators（作者 John Herrick）。原文是一篇带可交互演示的网页文章。

原文没有公开源码，但它的前端 bundle 没有做混淆，只是被压平了。我把模拟引擎和全部派梯算法还原了出来，并逐帧验证与原站一致。文中所有可交互演示都是从原站移植过来的真实引擎在跑，不是重画的示意图。

译者注是我加的，用引用块标出，与原文正文明确区分。

电梯调度

每个人都体会过等一部迟迟不来的电梯。「我按了按钮，它怎么还不来？」你会这么问。电梯看起来再普通不过，实际比表面上复杂得多。

这篇文章会拆开电梯的运作方式——你怎么按它的按钮，它又怎么按你的。

一、单梯

最简单的电梯算法叫 SCAN，1961 年申请了专利。电梯从大堂出发，一路开到顶层，然后掉头往回走，沿途接人和放人。

大多数时候你并不需要去顶层。如果电梯只开到被请求的最高层就掉头，这个算法叫 LOOK——大多数人熟悉并期待的就是它。

二、多梯

从这里开始变得有意思了。如果有好几部电梯，它们怎么协调谁去接谁？

最基本的系统里有一个中央调度器，告诉每部电梯该停哪些楼层。新请求进来时，分配给最近的那部。但后面会看到，我们可以做得更好。

三、漫长的等待

那要怎么衡量一个电梯算法的好坏？最直观的指标是你等电梯到的时间。

一个很简单的度量是「电梯在 30 秒内到达的频率」，或者「90 秒内到达的频率」。

四、应用统计

更严格地说，我们要看等待时间的分布。如果把几千次乘梯的等待时间画出来，就得到下面这张直方图。

p90 是 2 分钟，意思是 90% 的情况下乘客等待不超过 2 分钟。p50 是 1 分钟，意味着有一半时候电梯在 1 分钟内就到了。

人们通常记不住自己平均等了多久。他们记住的是电梯等了好久好久的那些时刻——也就是 p90 那一档。

译者注：原文这里有个可以直接验证的点。上面这个演示跑了 8 层 4 车、每分钟 18 人到达的配置，等它积累到几百个样本再观察——p50 会很快稳定在 20 秒左右，但 p90 要跑很久才收敛（我实测从 62 秒一路降到 53 秒还没停）。这解释了为什么小样本下的 p90 完全不可信：它衡量的恰恰是稀有的坏情况，而稀有事件需要更多样本才出现。

五、早高峰

不是所有客流都是一样的。想象一栋大型写字楼：早上几乎所有出行都是从大堂上楼。

到了傍晚就反过来了，所有人都往外走。午间的流量两者兼有，剩下的一些是楼层之间的往来。

等待时间的分布随一天中的时段和电梯面对的客流模式而剧烈变化。早高峰的等待统计是出了名的差。

六、更聪明的电梯

分析 LOOK 算法时，我们看（原文在这里玩了个双关：LOOK）了乘客是怎么分配给各部的。我们当时天真地按「最近的车」分配，并说可以做得更好。

如果最近的那部车已经满了呢？可以用 Otis 的 RSR（Relative System Response，相对系统响应） 算法做得更聪明。RSR 给每部车打分，衡量它有多适合去接某位乘客，分数越低越好。

RSR 接送评分

分数 = 预计接到时间
     + 车内载客惩罚
     + 同向防扎堆惩罚
     − 方向匹配奖励
     − 空闲就近奖励
     − 低载奖励

防扎堆：如果另一部车已经朝同一个楼层的同一方向去了，惩罚这部车。

空闲就近：呼叫者两层以内的空闲车获得奖励。

RSR 还每 5 秒重新优化一次。原本由 A 车接的乘客，如果 A 车遇到延误，可以被重新分配给 B 车。这个重新优化被证明是理顺客流的关键。

七、LOOK vs RSR

有了分析电梯的工具，就可以对比 LOOK 和 RSR 的表现，看看更聪明的算法究竟能把等待时间改善多少。

有意思的是，流量越高，LOOK 反而开始胜过 RSR。当电梯总是满载、每层都停时，那些额外规则就不再重要了。

在电梯数量少的小楼里，LOOK 也倾向于胜过 RSR。有时候，保持简单就是更好。

另一个可以追踪的指标是乘梯时长，也就是你进了电梯之后多久才到自己的楼层。RSR 和 LOOK 在这方面也有不同的特性，但超出了本文的范围。

译者注：原文把原因归结为「额外规则不再重要」。我读了源码后认为实际机制要更强一点——在高流量下，RSR 的额外项从信号退化成了噪声。

原因在第七节的对比里：LOOK 那一侧是纯 ETA，一行代码（score: (sim, car, call) => sim.estimateBoardingETA(...)），连容量检查都没有；而 RSR 那一侧带了五项调整。流量高时所有车都在往各个方向跑、都载得满，方向匹配奖励和低载奖励失去了区分度——它们不再区分好坏，却仍然在给评分加抖动，让派梯偏离真正最优的 ETA。

所以不是「规则不重要」，而是「这些规则在这里有害」。这也意味着原文的对比里混着两个变量：算法思想，和实现完整度。

八、目的楼层派梯

不是所有电梯里都有按钮。一些新的高级电梯在每层放一个终端，让你在电梯到达之前就指定要去哪层，然后终端告诉你该等哪部电梯。

这叫目的楼层派梯（Destination Dispatch）。乍看很棒：优化器现在完全知道谁要去哪里，当然可以用它来降低等待时间，对吧？

结果是，这些花哨的终端在大多数情况下比传统上下按钮更差。确实有例外（每组的电梯数 ≥ 8 的超高层建筑），但在大多数场合，朴素的上下按钮更胜一筹。

这个反直觉的结果，全都要归功于每隔 5 秒重新优化每部电梯路径的那个重平衡步骤。终端强制了刚性——你必须上被指派的那部车。

你按下按钮 30 秒后的世界状态可能已经很不一样了，但系统无法适应。灵活性上的损失，超过了多出来的信息给优化器带来的好处。

译者注：源码把原因交代得比原文更干净——它是一个布尔值造成的。目的楼层派梯的配置里写着 pinAssignment: true（乘客被钉死在被指派的车，只在满载弹回时重新分派）；而传统派梯的指派只是建议，任何同向的车到了都能接走人。

关键在于：这个「承诺可被抢占」的设计，恰恰是每 5 秒全局重优化能够成立的前提。传统系统之所以敢把所有人的承诺作废重来，正是因为那个承诺本来就不硬。kiosk 把这个机制的地基抽掉了。

九、完整模拟

这里有一个完整的模拟器，所有按钮和旋钮都能调。

十、结论

这篇文章只触及了电梯算法的表面。下次你卡在等电梯的时候，别太往心里去。电梯确实听见你了，它只是有很多事要想。

附：这份还原是怎么做的

译者注——这一节是我加的。

原文没有公开源码。但它的前端 bundle 没有做混淆，只是被打包器压平了（变量名被改成 e/t/i，控制流和字面量完整保留）。npx prettier 一过就是可读代码。

还原出来的东西包括：模拟引擎（1399 行）、8 个派梯策略（含 3 个原站隐藏的诊断变体）、SVG 渲染器，以及完整的物理参数。

正确性不是自称的，是对拍出来的。 我把还原版和从 bundle 里原样抠出的原函数放在一起跑同样的输入：

函数级对拍：111000 通过，0 失败
整机对拍：72000 帧一致，0 个场景出现偏差

整机对拍是让两个引擎在同一配置、同一种子下各跑 12000 帧（600 秒模拟时间），逐帧比对完整快照（车位置、速度、状态、候梯人归属、等待时间序列）。6 套配置覆盖了 LOOK / RSR / Traditional / 目的楼层派梯，单梯与多梯都有。

对拍抓到了四个我自认为写对了、实际写错了的地方，其中一个是把源码里两个不同的函数当成了同一个（一个返回秒、一个返回速度），会导致 ETA 全是 NaN——动画照跑，但行为完全不对，肉眼很难发现。

复跑验证：

node research/elevators/verify-all.mjs

引擎的几个行为特征

读源码时有两件事值得单独说，因为它们和「交互式演示应该是什么样」有关：

改布局会重置整个模拟。 楼层数或车数一变，引擎调用 reset()——统计清零、所有人重新生成。所以那句「所有按钮和旋钮都能调」的准确含义是「改参数 → 重新跑」，不是拖滑块看实时反应。
步长必须是 0.05 秒。 开关门动画的进度由 doorTime 直接驱动，放大 dt 会让动画失步。所谓「100x 加速」是在一帧里跑约 34 个子步实现的，不是把时间轴拉快。

参考资料

John Herrick. Elevators. john.fun/elevators
Barney, G.C. Elevator Traffic Handbook（SCAN / LOOK / 群控调度的标准参考）
Smith, R. & Peters, R. ETD and System Degradation Factor. ELEVCON 2002, ThyssenKrupp（目的楼层派梯的目标函数）

电梯调度：LOOK、RSR 与目的楼层派梯

目录