电梯

# 电梯 来源：https://john.fun/elevators 所有人都经历过等电梯却迟迟不来的沮丧。“我按了按钮，为什么它不来？”你问道。对于电梯这种非常常见的东西，它们的复杂性远超你的想象。 在整篇文章中，我们将揭开电梯的奥秘：你按按钮的方式，以及它们“按”你的方式。 4321## 单台电梯 最简单的电梯算法叫作 SCAN，于 1961 年获得专利。电梯从大厅出发，一路到顶层，然后反向再下来。沿途接上或送下任何人。 大多数时候你实际并不需要去**顶层**。如果电梯只运行到被请求的最高楼层就折返，这种算法叫作 LOOK 算法。这也是大多数人知道并期待的算法。 4321## 多台电梯 这就是奥秘开始的地方。如果有多个电梯，轿厢如何协调谁去接谁？ 在最基本的系统中，有一个中央调度器告诉每台电梯应在哪些楼层停靠。当新请求进入时，会被分配给最近的电梯。然而，我们将很快看到，我们其实可以做得更好。 ## 漫长等待 你到底如何衡量一个电梯算法的好坏？最明显的指标是你等电梯到达要多久。 一个非常简单的衡量标准是“电梯在 30 秒内到达的频率是多少？”或者“电梯在 90 秒内到达的频率是多少？” - 等待 < 30s - 等待 < 90s 654321流量**14/min** ## 实际统计 更严格地说，我们要看的是等待时间的**分布**。如果我们将数千次乘梯的等待时间绘制出来，会得到下面的直方图。 654321010s p50—p90— 流量**14/min** p90 为 2 分钟意味着 90% 的情况下，乘客等待电梯不超过 2 分钟。p50 为 1 分钟意味着半数情况下电梯会在 1 分钟内到达。 人们通常不会记住等待的平均时间。他们念念不忘的是那些感觉电梯“永远”不来的时刻，也就是 p90 的情况。 ## 早高峰 并非所有的乘客流量都一样。想象一栋大型企业办公楼。早晨，几乎所有的客流都是从大厅到上层楼。 晚上则反过来，所有人都离开大楼。午餐高峰两者兼有，其余客流则往往是楼层到楼层。 - 等待 < 30s - 等待 < 90s 654321流量**14/min** 等待时间的分布会随着一天中的时段和电梯面对的客流模式而剧烈变化。早高峰的等待统计尤其糟糕是出了名的。 ## 更智能的电梯 在分析 LOOK 电梯算法时，我们“看了看”（哈哈）乘客是如何被分配给轿厢的。我们天真地把每个请求分配给最近的轿厢，但说我们可以做得更好。 如果最近的轿厢已经满了呢？我们可以用奥的斯（Otis）的 RSR（相对系统响应）算法来变得更聪明。RSR 会给每台轿厢的“接客适合度”打分。分数越低越好。 RSR 接客评分 评分 = 到达接客点的预计时间 + 轿厢内荷载惩罚 + 同向防聚集惩罚 - 方向匹配奖励 - 附近空闲奖励 - 低荷载奖励 - **防聚集**：如果另一台轿厢已经以相同方向前往同一楼层，则对该轿厢施加惩罚。 - **附近空闲**：奖励距离呼叫者两层以内的空闲轿厢。 RSR 还会每 5 秒重新优化一次。原本要由电梯 A 接走的乘客，如果电梯 A 出现延误，可以改派给电梯 B。事实证明，这种重新优化是疏通客流的关键。 在下图中，每当第 3 层的呼梯按钮恰好被按下时，最适合响应该呼叫的电梯会亮起。随着电梯移动，这个选择也在不断变化，展现出优化器的实时运行状态。 4321ABCDAScore1 ## LOOK vs RSR 有了我们的电梯分析工具包，我们可以对 LOOK 和 RSR 的性能进行基准测试，看看更聪明的电梯算法到底能改善多少等待时间。 LOOK - 等待 < 30s - 等待 < 90s 10987654321 RSR - 等待 < 30s - 等待 < 90s 10987654321 流量**8/min** 有趣的是，随着流量升高，LOOK 实际上开始胜过 RSR。当电梯总是满员并且每层都停时，额外的规则就不那么重要了。 LOOK 在电梯数量较少的较小楼宇中通常也优于 RSR。有时候把事情简单化反而更好。 你还可以跟踪另一个指标——行程时间，即你在电梯里实际等待到达目的楼层的时间。RSR 和 LOOK 在这方面也有不同特征，但这已超出本文范围。 ## 目的楼层派梯 并非所有电梯内部都有按钮。一些高端新电梯在每个楼层设有一个终端，让你在电梯到达前就指定要去的楼层。随后终端会指示你应该等哪部电梯。 这就是所谓的目的楼层派梯（Destination Dispatch）。乍一看它似乎很棒。电梯优化器现在完全知道谁要去哪里，我们肯定可以用它来减少等待时间，对吧？ RSR - 等待 < 30s - 等待 < 90s 87654321 目的楼层派梯 - 等待 < 30s - 等待 < 90s 876543217 流量**8/min** 事实证明，这些花哨的终端在等待时间上总体上**更差**，反而不如传统的老式上/下按钮。当然也有一些极端场景下终端会胜出（每个电梯组有 8 台以上电梯的超高楼），但在大多数情况下，简单的上/下按钮才是王者。 这个反直觉的结果完全归功于重新平衡步骤：每 5 秒系统就会重新优化每台电梯的路径。终端带来了僵化——你必须进入**指定的**电梯。 你呼梯后 30 秒的世界状态可能已经大为不同，但系统却无法调整。结果表明，对优化器来说，额外信息并不值得以失去灵活性为代价。 ## 完整模拟 这里有一个带有各种按钮和旋钮的模拟器，尽情玩耍吧！ - 等待 < 30s - 等待 < 90s 87654321楼层**8**电梯**4**流量**18/min** ## 结论 这篇文章只是触及了电梯算法的皮毛。下次你被困在等电梯的境地时，尽量不要觉得是针对自己。电梯确实听到了你的呼叫，只是它要考虑的事情太多。