Everyone has shared the frustration of waiting for an elevator that never seems to arrive. "I pressed the button, why isn't it coming?" you ask. For something as commonplace as elevators, they are far more complex than meets the eye.每个人都经历过等待电梯迟迟不来的沮丧。“我明明按了按钮，为什么还不来？”你可能会这样问。电梯这种司空见惯的事物，其复杂程度远超你的想象。
Over the course of this article, we'll unravel the mysteries of elevators. The way you push their buttons, and how they push yours.在本文中，我们将揭开电梯的奥秘。了解你是如何按下它们的按钮，以及它们又是如何“按”下你的耐心的。
One Car单轿厢
The simplest elevator algorithm is called SCAN and was patented in 1961. The elevator starts at the lobby and goes all the way to the top floor before reversing and coming back down. It picks up and drops off anybody on the way.最简单的电梯算法称为 SCAN（扫描算法），于 1961 年获得专利。电梯从大厅出发，一直运行到最高层，然后掉头向下。在此过程中，它会接送所有途中的乘客。
Most of the time you don't actually need to go to the TOP floor. If the elevator goes only as high as requested before reversing, the algorithm is called the LOOK algorithm. This is the algorithm most people know and expect.大多数时候，你其实并不需要去到最高层。如果电梯只运行到请求的最高楼层就掉头，这种算法被称为 LOOK 算法。这是大多数人所熟知并期待的算法。
Multiple Cars多轿厢
Here's where the mystery begins. If there are multiple elevators, how do the cars coordinate who picks up who?奥秘就在这里。如果有多个电梯，轿厢之间是如何协调谁去接谁的呢？
In the most basic system, there's a central scheduler that tells each elevator which floors to stop on. When a new request comes in, it's assigned to the closest elevator. As we'll soon see however, we can do better.在最基础的系统中，有一个中央调度器负责告诉每部电梯在哪些楼层停靠。当有新请求时，它会被分配给距离最近的电梯。然而，正如我们稍后将看到的，我们其实可以做得更好。
Long Waits漫长的等待
How do you actually measure how good an elevator algorithm is? The obvious metric is how long you wait for the elevator to arrive.如何衡量电梯算法的好坏？最直观的指标就是你等待电梯到达的时间。
A very simple measure is "how often does the elevator arrive within 30 seconds?" Or "how often does the elevator arrive within 90 seconds?"一个非常简单的衡量标准是：“电梯在 30 秒内到达的频率是多少？”或者“在 90 秒内到达的频率是多少？”
Applied Stats应用统计学
More rigorously, we want to look at the DISTRIBUTION of wait times. If we plot the wait time across thousands of rides, we get the histogram below.更严谨地说，我们需要观察等待时间的分布情况。如果我们绘制出数千次乘梯的等待时间，就会得到下面的直方图。
A p90 of 2m means 90% of the time, riders wait 2m or less for the elevator. A p50 of 1m means half the time the elevator arrives within 1m.p90 为 2 分钟意味着 90% 的情况下，乘客等待时间在 2 分钟或以内。p50 为 1 分钟意味着有一半的时间，电梯会在 1 分钟内到达。
People don't usually remember the average amount of time they wait. They fixate on those times when the elevator took FOREVER, the p90 case.人们通常不会记住平均等待时间。他们只会对那些电梯“慢得要命”的情况印象深刻，也就是 p90 的情况。
Morning Rush早高峰
Not all passenger traffic is created equal. Imagine a large corporate office building. In the mornings, nearly all traffic is dominated by trips from the lobby to the upper levels.并非所有的客流都是一样的。想象一栋大型办公楼，早晨几乎所有的客流都是从大厅前往高层。
In the evening this flips as everyone leaves the building. The lunch rush is a bit of both, and the remaining traffic is often from floor to floor.到了傍晚，情况正好相反，因为所有人都要离开大楼。午餐高峰则是两者兼有，而其余的流量通常是楼层之间的往返。
The distribution of wait times varies drastically depending on the time of day and the traffic patterns the elevators are facing. Morning rush notoriously has the worst wait statistics.等待时间的分布会根据一天中的时间和电梯所面临的交通模式而发生剧烈变化。早高峰的等待统计数据通常是最糟糕的。
Smarter Elevators更智能的电梯
When analyzing the LOOK elevator algorithm, we LOOKED (ha ha) at how riders are assigned to cars. We naively assigned each request to the nearest car but said we could do better.在分析 LOOK 电梯算法时，我们“观察”（LOOKED）了乘客是如何被分配到轿厢的。我们简单地将每个请求分配给最近的轿厢，但我们说过可以做得更好。
What if the nearest car is full? We can get smarter with Otis' RSR (Relative System Response) algorithm. RSR scores each car for how well suited it is to pick up a passenger. Lower scores being better.如果最近的轿厢满了怎么办？我们可以通过奥的斯（Otis）的 RSR（相对系统响应）算法变得更聪明。RSR 会为每部轿厢评分，以确定它接载乘客的合适程度。分数越低越好。
- Anti-Bunching
- Penalize a car if another car is already headed to the same floor in the same direction.如果另一部电梯已经在同方向前往同一楼层，则对该轿厢进行惩罚。
- Idle Nearby
- Reward idle cars within two floors of the caller.奖励呼叫者所在楼层附近两层内的空闲轿厢。
RSR also re-optimizes every 5 seconds. A passenger that's going to be picked up by elevator A can be re-routed to elevator B if elevator A encounters delays. This re-optimization turns out to be key for streamlining traffic flow.RSR 每 5 秒还会进行一次重新优化。原本由 A 电梯接载的乘客，如果 A 电梯遇到延误，可以被重新分配给 B 电梯。事实证明，这种重新优化是优化交通流的关键。
In the graphic below, each elevator lights up when it's the best choice to service a call from floor 3 if the button happened to be pressed at that exact moment. This constantly changes as the elevators move, showing the optimizer in motion.在下图中，每部电梯在被选为服务 3 楼呼叫的最佳选择时会亮起。随着电梯的移动，这个选择会不断变化，展示了优化器的工作过程。
LOOK vs RSRLOOK 与 RSR 对比
Armed with our elevator analysis toolkit, we can benchmark the performance of LOOK vs RSR to see how much a smarter elevator algorithm actually improves wait time.有了我们的电梯分析工具包，我们可以对 LOOK 和 RSR 的性能进行基准测试，看看更智能的算法究竟能改善多少等待时间。
Interestingly as the flow rate gets higher, LOOK actually starts to outperform RSR. When the elevators are always full and stopping on every floor, the extra rules don't matter as much.有趣的是，随着流量增加，LOOK 的表现反而开始超过 RSR。当电梯总是满载并在每一层都停靠时，额外的规则就不那么重要了。
LOOK also tends to outperform RSR in small buildings with fewer elevators per bank. Sometimes it's better to just keep things simple.在电梯组较少的小型建筑中，LOOK 的表现也往往优于 RSR。有时，保持简单反而更好。
Another metric you can track is journey time, how long you're actually waiting in the elevator before getting to your floor. RSR and LOOK have different characteristics here as well but that's beyond the scope of this article.你可以追踪的另一个指标是行程时间，即你在电梯里实际等待到达目标楼层的时间。RSR 和 LOOK 在这方面也有不同的特性，但这超出了本文的讨论范围。
Destination Dispatch目的层调度
Not all elevators have buttons in them. Some of the fancy new elevators have a kiosk on each floor that allows you to specify what floor you're heading to before the elevator even arrives. The kiosk then points you to which elevator you should wait for.并非所有电梯内部都有按钮。一些新式电梯在每个楼层都有一个触控屏，允许你在电梯到达之前指定要去的目标楼层。然后，系统会指引你前往应该等待的电梯。
This is called Destination Dispatch. At first glance, it seems great. The elevator optimizer now has full knowledge of who is going where, certainly we can use this to reduce wait times right?这被称为目的层调度（Destination Dispatch）。乍一看，这似乎很棒。电梯优化器现在完全了解每个人要去哪里，我们当然可以利用这一点来减少等待时间，对吧？
It turns out these fancy kiosks are in general worse for wait times compared to the traditional good ol' up and down buttons. There are certainly edge cases when the kiosks can win out (extremely tall buildings with 8+ cars per elevator bank) but for the majority of cases, simple up down buttons reign supreme.事实证明，与传统的上下按钮相比，这些花哨的触控屏在等待时间上通常表现更差。虽然在极端情况下（例如每组电梯有 8 部以上轿厢的超高层建筑），这种系统有其优势，但在大多数情况下，简单的上下按钮依然是王者。
This counterintuitive result is all thanks to the rebalancing step where every 5 seconds, the system re-optimizes each elevator's path. The kiosk enforces rigidity, you must get in the assigned elevator.这种反直觉的结果完全归功于每 5 秒一次的重新平衡步骤，系统会重新优化每部电梯的路径。而触控屏系统强制执行了僵化的调度，你必须进入指定的电梯。
The state of the world 30sec after you called your elevator might be very different but the system is unable to adapt. Turns out the loss in flexibility is not worth the extra information for the optimizer.在你呼叫电梯 30 秒后，世界状态可能已经发生了很大变化，但系统却无法适应。事实证明，对于优化器来说，失去灵活性所带来的损失，并不能被获取额外信息所抵消。
Full Sim完整模拟
Here's a simulation with all the buttons and knobs to play with. Go crazy!这是一个可以调节各种参数的模拟演示。尽情尝试吧！
Conclusion结论
This article just scratches the surface of elevator algorithms. Next time you're stuck waiting for an elevator, try not to take it personally. The elevator did hear you, it just has a lot to think about.本文仅仅触及了电梯算法的皮毛。下次当你被困在等待电梯时，试着不要往心里去。电梯听到了你的呼唤，只是它需要考虑的事情实在太多了。