电梯

每个人都曾有过等待电梯却迟迟不来的挫败感。“我已经按了按钮，为什么它还不来？”你可能会这样问。对于电梯这样司空见惯的事物，其复杂程度远超表面所见。

在本文中，我们将揭开电梯的神秘面纱。看看你如何按下它们的按钮，它们又如何牵动你的心情。

4321

1x5x25x

单轿厢

最简单的电梯算法叫做 SCAN，于1961年获得专利。电梯从大厅启动，一路直达顶层，然后折返下行，途中接载和送下所有乘客。

但大多数时候，你实际上并不需要去顶层。如果电梯只上升到有请求的最高层就折返，这种算法就称为 LOOK 算法。这是大多数人熟知并期待的算法。

4321

1x5x25x 增加五次呼叫

多轿厢

谜题从这里开始。如果有多部电梯，轿厢之间如何协调由谁接谁？

在最基本的系统中，有一个中央调度器，它告诉每部电梯停靠哪些楼层。当新请求进来时，它会被分配给最近的电梯。然而，正如我们即将看到的，我们可以做得更好。

4321

1x5x25x

长等待

实际上，你如何衡量一个电梯算法的好坏？一个显而易见的指标是等待电梯到达的时间。

一个非常简单的衡量标准是“电梯在30秒内到达的频率是多少？”或者“电梯在90秒内到达的频率是多少？”

等待时间 < 30秒

等待时间 < 90秒

654321

1x5x25x 流量14/分钟重置

应用统计

更严谨地说，我们希望观察等待时间的分布。如果我们将数千次乘坐的等待时间绘制成图表，就会得到下面的直方图。

654321

010秒

p50—p90—

25x100x500x 流量14/分钟重置

p90为2分钟意味着90%的情况下，乘客等待电梯的时间不超过2分钟。p50为1分钟意味着一半情况下电梯在1分钟内到达。

人们通常不记得他们等待的平均时间。他们更在意那些电梯仿佛“永远”不来的情况，也就是p90所反映的情形。

早高峰

并非所有的客流都是一样的。想象一栋大型企业办公楼。早上，几乎所有的交通都是从大厅到上层楼层的单向流动。

晚上情况则相反，所有人都离开大楼。午餐高峰则两者兼有，而其余的交通通常是楼层间的往返。

早晨 午餐 晚上 楼层间

等待时间 < 30秒

等待时间 < 90秒

654321

5x25x100x 流量14/分钟重置

等待时间的分布会根据一天中的时间和电梯面临的客流模式发生巨大变化。早高峰的等待统计数据通常是最差的。

更智能的电梯

在分析LOOK电梯算法时，我们“观察”（哈哈）了乘客如何被分配到轿厢。我们天真地将每个请求分配给最近的轿厢，但也提到可以做得更好。

如果最近的轿厢满了呢？我们可以采用Otis的 RSR（相对系统响应）算法来使分配更智能。RSR为每部轿厢评分，评估其接载乘客的适合程度。分数越低越好。

RSR 接载评分

分数=预计接载时间+轿厢负载惩罚+同向防聚集惩罚-方向匹配奖励-附近空闲奖励-低负载奖励

防聚集惩罚：如果另一部电梯已经正朝相同方向前往同一楼层，则惩罚当前轿厢。

附近空闲奖励：奖励位于呼叫者所在楼层上下两层内的空闲轿厢。

RSR还会每5秒重新优化一次。原本计划由电梯A接载的乘客，如果在电梯A遇到延误时，可以被重新分配给电梯B。这种重新优化对于疏通交通流至关重要。

在下面的图示中，如果楼层3的按钮恰好在那一刻被按下，每部电梯会在它是最佳选择时亮起。随着电梯移动，最佳选择不断变化，展示了优化器在动态运行。

4321ABCD 评分 1

LOOK vs RSR

有了我们的电梯分析工具，我们可以对比 LOOK 和 RSR 的性能基准，看看更智能的电梯算法实际上能将等待时间改善多少。

LOOK

**-**等待时间 < 30秒

**-**等待时间 < 90秒

10987654321

RSR

**-**等待时间 < 30秒

**-**等待时间 < 90秒

10987654321

1x25x250x 流量8/分钟重置

有趣的是，随着流量增加，LOOK的表现实际上开始优于RSR。当电梯总是满员并在每层都停靠时，那些额外的规则就不那么重要了。

LOOK在每组电梯数量较少的小型建筑中也往往优于RSR。有时，保持简单反而是更好的选择。

另一个可以追踪的指标是行程时间，即你实际在电梯内等待到达目的楼层的时间。RSR和LOOK在此方面也有不同的特性，但这已超出本文的讨论范围。

目的楼层调度

并非所有电梯内部都有按钮。一些先进的新式电梯在每层楼都设有一个服务台，允许你指定你所要前往的楼层。