Elevators / 电梯

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. 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.

在分析 LOOK 电梯算法时，我们“审视”（LOOKED）了乘客是如何被分配到轿厢的。我们最初简单地将每个请求分配给最近的轿厢，但我们说可以做得更好。如果最近的轿厢满了怎么办？我们可以利用奥的斯（Otis）的 RSR（相对系统响应）算法变得更聪明。RSR 为每台轿厢评分，以评估其接载乘客的适合程度，分数越低越好。

RSR pickup score = ETA to pickup + onboard load penalty + same-direction anti-bunching penalty - direction-match bonus - idle-nearby bonus - low-load bonus RSR 接载评分 = 到达接载点的预计时间 + 载客负荷惩罚 + 同向防拥堵惩罚 - 方向匹配奖励 - 空闲邻近奖励 - 低负荷奖励

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。事实证明，这种重新优化是简化交通流的关键。

LOOK vs 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 also tends to outperform RSR in small buildings with fewer elevators per bank. Sometimes it’s better to just keep things simple.

有趣的是，随着流量增加，LOOK 实际上开始优于 RSR。当电梯总是满载且每层都停时，额外的规则就不那么重要了。在电梯组较少的小型建筑中，LOOK 也往往优于 RSR。有时，保持简单反而更好。

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.

并非所有电梯内部都有按钮。一些高级的新型电梯在每个楼层都设有自助服务终端，让你在电梯到达之前就能指定要去哪一层。然后，终端会指引你前往应该等待的电梯。这被称为“目的楼层控制”（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? It turns out these fancy kiosks are in general worse for wait times compared to the traditional good ol’ up and down buttons.

乍一看，这似乎很棒。电梯优化器现在完全掌握了谁要去哪里，我们肯定可以用它来减少等待时间，对吧？事实证明，与传统的“上/下”按钮相比，这些高级终端在等待时间方面通常表现更差。

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. 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.

这种反直觉的结果归功于每 5 秒一次的重新平衡步骤，系统会重新优化每台电梯的路径。而终端强制执行了刚性分配，你必须乘坐指定的电梯。在你呼叫电梯 30 秒后，外部环境可能已经发生了很大变化，但系统却无法适应。事实证明，为了优化器多获取的那点信息而牺牲灵活性是不值得的。