电梯调度算法：LOOK、RSR 与目的分派

电梯等待时间在很大程度上取决于用于将轿厢分配给厅层呼叫的调度算法。较简单的算法（如 LOOK）在典型的办公楼中，其表现往往优于或等同于更复杂的方案，例如 Otis 的 RSR 或目的分派（Destination Dispatch）。

单台电梯：SCAN 与 LOOK

LOOK 算法是 SCAN 算法的一种变体，是电梯运行的基准预期。它从大堂开始，仅向上运行到最高待处理请求所在的楼层，然后掉头并处理向下请求，在此过程中接送乘客。这与原始的 SCAN（或“电梯”）专利不同，后者在掉头前总是会运行到顶层。

多台电梯与基础协同

在拥有多台电梯的情况下，中央调度器会将每个厅层呼叫分配给最近的空闲电梯。这种“最近轿厢”规则忽略了车内已有多少乘客，以及轿厢是在向呼叫者移动还是远离呼叫者，这在最近的轿厢已满或正向错误方向行驶时，可能会导致次优的分配。

性能衡量：等待时间分布

工程师使用等待时间的百分位数而非平均值来评估算法，因为乘客对长时间等待记忆深刻。p50 为 1 分钟意味着一半的行程等待时间在 1 分钟或以下；p90 为 2 分钟意味着 90% 的行程等待时间在 2 分钟或以下。本文的直方图展示了在各种流量下的这些指标——例如，在每分钟 14 次请求时，LOOK 算法的 p90 约为 2 分钟，而在每分钟 8 次请求时，p90 会有所改善。

早高峰与交通模式

在高峰时段，交通具有高度的方向性。在大型企业办公楼中，早高峰的特征是大量从大堂前往高层的行程，晚高峰则相反，而午餐时间则混合了两个方向。这种不对称性使得早高峰成为等待时间统计中最糟糕的情况，因为电梯大部分运行时间都在服务单向流量。

更智能的电梯：Otis 的 RSR

RSR 在基础的 ETA（预计到达时间）接送评分中加入了细微的惩罚和奖励机制：

  • ETA to pickup – 轿厢到达厅层呼叫处所需的时间。
  • Onboard load penalty – 随当前乘客数量增加而增加。
  • Same-direction anti-bunching penalty – 避免将轿厢派往另一台同向行驶的轿厢已经前往的楼层。
  • Direction-match bonus – 奖励已经在目标方向行驶的轿厢。
  • Idle-nearby bonus – 倾向于选择在呼叫者两层楼范围内的空闲轿厢。
  • Low-load bonus – 优先选择乘客较少的轿厢。 该系统每五秒重新计算一次这些分数，如果发生延迟，最初分配给电梯 A 的乘客可能会被重新路由到电梯 B。

LOOK vs RSR：基准测试结果

本文中的模拟结果比较了 LOOK 和 RSR 在不同流量下的表现：

  • 在每分钟 14 次请求时，LOOK 和 RSR 的等待时间 < 30s 和 < 90s 的百分比相当。
  • 在每分钟 8 次请求时，RSR 的等待时间 < 30s 和 < 90s 的数值略好。
  • 随着流量增加，LOOK 开始超越 RSR，因为当轿厢持续满载并在每一层停靠时，额外的 RSR 规则提供的益处微乎其微。
  • 在每组电梯数量较少的建筑中，LOOK 也往往优于 RSR，因为简单性降低了开销。 这些发现呼应了“简单往往胜过复杂”这一观点【@heironimus】。

目的分派：权衡

目的分派用楼层终端取代了厅层呼叫按钮，告知乘客应该搭乘哪台特定的电梯。虽然这为调度器提供了完整的目的地信息，但它引入了僵化性：一旦分配了轿厢，即使情况发生变化，乘客也无法切换到另一台电梯。文章指出，这种灵活性的缺失通常使得目的分派在等待时间方面不如传统的上下按钮，除非是在每组有八台或更多电梯的超高层建筑中。 这种反直觉的结果源于五秒钟的重新优化循环：“终端强制了僵化性，你必须进入分配的电梯。在你呼叫电梯 30 秒后的世界状态可能会非常不同，但系统无法做出调整”【@JoshTriplett】。 然而，当交通流量由前往同一楼层的庞大群体组成时，目的分派可以表现出色，因为它可以将这些乘客批量处理在一起【@omoikane】。

全模拟洞察

交互式模拟器允许用户改变楼层数、轿厢数和请求流量。调整这些参数可以显示 LOOK、RSR 和目的分派之间的平衡是如何变化的——例如，在 8 层、4 台电梯和每分钟 18 次请求的情况下，模拟器显示了每种算法的等待时间百分比。这进一步证实了最优算法取决于特定建筑的交通模式和电梯容量。

人为因素与实际考量

现实世界的电梯性能受纯调度逻辑之外的更多因素影响：

  • 用户行为：许多乘客会同时按下上行和下行按钮，误以为这能加快到达速度，这实际上会导致不必要的停靠和混乱【@olex】。
  • 容量感应：如果没有可靠的满载检测器，电梯即使在满载的情况下也可能在每一层停靠，造成人群在满载电梯外等待的挫败场景【@vova_hn2】。
  • 磨损：为了减少等待时间而进行的激进重新定位会增加机械磨损，这表明乘客延迟与维护成本之间存在权衡【@taftster】。
  • 心理等待：在等待期间提供消遣或感知的进度可以提高满意度，即使实际等待时间保持不变【@psadri】。
  • 预取策略：一些设施（如 Apple Park）在接到呼叫后会将空闲电梯移向底层，以缩短未来的响应时间【@ladberg】。 这些因素说明了为什么模拟中的“最佳”算法可能与乘客在实践中感觉最好的算法有所不同。

Sources