电梯
Hacker News 摘要原标题：Elevators
每个人都经历过等电梯时的焦虑，明明按了按钮，电梯却迟迟不来。电梯虽然司空见惯，但其背后的逻辑远比看上去复杂。这篇文章揭示了电梯运行的奥秘，以及算法是如何影响你的等待体验的。
单台电梯的运作逻辑
最简单的电梯算法被称为 SCAN，于 1961 年获得专利。在这种模式下，电梯从底层大厅开始，一直运行到顶层，然后掉头返回底层，沿途接送所有人。
但在现实中，电梯通常不需要每次都运行到顶层。如果电梯只运行到请求所在的最高楼层就掉头，这种算法被称为 LOOK 算法。这也是大多数人熟悉并期待的电梯运作方式。
多台电梯的协作
当一个建筑内有多台电梯时，核心挑战在于如何协调它们。在基础系统中，有一个中央调度器负责分配任务。每当有新的请求时，系统会将其分配给距离最近的电梯。然而，这种简单的分配方式还有很大的优化空间。
衡量电梯表现的指标
评价一个电梯算法的好坏，最直观的指标是等待时间。简单的衡量标准包括“电梯在 30 秒内到达的频率”或“在 90 秒内到达的频率”。
更严谨的方法是观察等待时间的分布情况。通过分析成千上万次运行数据，可以得出以下关键指标：
• p90：意味着 90% 的乘客等待时间少于某个值（例如 2 分钟）。人们通常不会记住平均等待时间，而是对那些等了“一辈子”才来的极端情况（即 p90 情况）记忆深刻。
• p50：代表中位数，即一半的乘客在此时限内能等到电梯。
不同时段的交通模式
电梯面临的压力取决于时间段：
• 早高峰：交通流主要是从大厅前往各个高楼层。这是电梯统计数据表现最差的时期。
• 晚高峰：情况相反，人们集中离开建筑前往大厅。
• 午餐高峰：混合了上下行流量以及楼层间的往返。
更智能的 RSR 算法
LOOK 算法只是简单地将请求分配给最近的电梯，但如果这台电梯已经满员了呢？奥的斯（Otis）公司开发了 **RSR（相对系统响应）**算法。
RSR 会为每台电梯打分，分数越低代表该电梯越适合接送该乘客。其计算公式考虑了多个因素：
RSR 接送评分 = 预计到达时间 + 车内负载惩罚 + 同向防聚集惩罚 - 方向匹配奖励 - 附近空闲奖励 - 低负载奖励
其中有两个关键概念：
1. 防聚集（Anti-Bunching）：如果另一台电梯已经前往同一楼层的同一方向，则会对当前电梯施加惩罚，防止电梯堆叠。
2. 附近空闲：奖励那些停在呼叫楼层两层以内的空闲电梯。
RSR 算法每 5 秒进行一次重新优化。原本分配给 A 电梯的乘客，如果 A 遇到延迟，可能会被重新分配给 B 电梯。这种动态调整是优化交通流的关键。
LOOK 算法与 RSR 算法的对比
通过对比发现，RSR 并不总是优于 LOOK。当交通流量非常大、电梯几乎满载且每层都停时，简单的 LOOK 算法表现反而更好。此外，在电梯数量较少的小型建筑中，简单的逻辑往往更有效。
除了等待时间，另一个指标是乘梯时间（即进入电梯到抵达目的地的时长）。RSR 和 LOOK 在这方面也有不同的特性。
目的地调度系统（Destination Dispatch）
现在很多高级办公楼使用一种没有内部按钮的电梯。乘客在楼层的亭子（Kiosk）上输入要去的目标楼层，系统会直接告知应该去等哪一台电梯。
虽然这看起来很先进，因为系统提前知道了所有人的目的地，但研究表明，目的地调度系统在减少等待时间方面通常表现更差。
这种系统虽然在极少数情况下（如超过 8 台电梯的摩天大楼）有优势，但在大多数场景下，传统的上下按钮更有优势。原因是目的地调度系统缺乏灵活性：
• 在传统系统中，系统每 5 秒可以重新优化一次。
• 在目的地调度系统中，一旦亭子指定了电梯，你就必须坐那一台。
• 即使 30 秒后环境发生了变化，系统也无法重新调整你的分配方案。
总结
电梯算法是一个深奥的领域。下次当你觉得等电梯太久时，请记住：电梯并不是没听到你的呼唤，它只是在复杂的计算中权衡各种可能性。