电梯为什么不马上来：从 LOOK 到群控调度算法

发表于 阅读次数： 本文字数： 2.2k 阅读时长 ≈ 8 分钟

按下电梯按钮后，系统要解决的并不只是“让最近的电梯过来”。它还要考虑电梯当前的运行方向、沿途停靠、轿厢负载、其他乘客的等待时间，以及早晚高峰完全不同的客流。看似普通的一次候梯，背后其实是一个不断接收新任务的实时调度问题。

本文参考 John 的交互文章 Elevators，从单部电梯的 LOOK 算法开始，逐步理解多梯群控、RSR 评分、等待时间分布和目的层派梯。

问题是如何变复杂的

先把一部电梯抽象成几个状态：

  • 当前楼层；
  • 运行方向：上行、下行或空闲；
  • 轿厢内已经登记的目标楼层；
  • 各楼层发出的上行、下行呼叫；
  • 当前载重和额定容量。

如果所有请求一开始就全部已知，规划一条短路线并不困难。现实中，请求却会随时到达：电梯执行旧计划时，新乘客可能在任意楼层按键。因此，调度器必须在响应速度、运行距离、公平性和系统吞吐量之间不断取舍。

单部电梯：SCAN 与 LOOK

最容易想到的策略是始终服务距离最近的请求。但这种贪心策略可能让电梯在局部反复移动，使远处楼层长期得不到服务。

更常见的思路类似扫描：电梯选定一个方向后，依次处理沿途请求，到达边界后再反向。它与操作系统磁盘调度中的 SCAN（Elevator Algorithm） 很相似。

SCAN 会一直运行到服务范围的边界。LOOK 则在继续前进前先“向前看”：如果当前方向已经没有待处理请求，就在最远请求处反向，不必空跑到顶层或底层。

例如，电梯位于 6 楼并正在上行，当前请求为 2↓、8↑、11↓、15↓。LOOK 会先处理 8、11、15 楼，再反向去 2 楼，而不是每次选择当前距离最近的楼层。

一个简化实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
loop:
    收集新请求

    if 当前方向 == 上行:
        处理当前位置以上、方向兼容的请求
        if 上方不再有请求:
            切换为下行

    else if 当前方向 == 下行:
        处理当前位置以下、方向兼容的请求
        if 下方不再有请求:
            切换为上行

    else:
        根据待处理请求选择初始方向

实际控制器还需要处理开关门时间、制动距离、消防模式、超载和请求取消等约束，不能把上面的伪代码直接用于真实设备。

多部电梯：最近的不一定最快

当一组电梯共享呼叫按钮时，系统还要决定由哪部电梯响应。最简单的规则是分配给距离呼叫楼层最近的电梯，但物理距离并不等于到达时间。

假设乘客在 8 楼向下呼叫：

  • A 梯位于 7 楼，但正在上行，轿厢内还有多个目标楼层；
  • B 梯位于 11 楼，正在下行，负载很低；
  • C 梯位于 5 楼，处于空闲状态。

A 梯虽然最近，却可能最后才到。调度器至少要估计每部电梯的预计到达时间（ETA），并考虑方向、计划停站和容量。

RSR：把派梯变成评分问题

Otis 的 Relative System Response（RSR）方法会为每部候选电梯计算相对响应分数，再将厅外呼叫分配给更合适的轿厢。相关专利将其描述为一组可加权的“奖励”和“惩罚”，而不只是比较绝对距离（参见 Otis RSR 专利 US5146053）。

可以把简化后的评分理解为：

1
2
3
4
5
6
7
8
score(car, call) =
    预计到达时间
  + 轿厢负载惩罚
  + 反向运行惩罚
  + 重复派梯惩罚
  + 额外停站成本
  - 同向奖励
  - 附近空闲奖励

分数越低，通常表示越适合响应这次呼叫。评分项和权重不是固定真理，而是控制策略：办公楼、住宅、医院和酒店的目标可能完全不同。

更重要的是，分配不一定要一锤定音。只要乘客还未上车，系统就可以周期性重新计算：如果原本分配的电梯突然变满或新增多个停站，就把呼叫改派给另一部电梯。动态重分配提高了适应性，但也要避免显示信息反复变化，让乘客不知道该等哪一部。

不能只看平均等待时间

评价调度算法时，“平均等待 25 秒”可能掩盖少量非常糟糕的体验。更实用的做法是观察完整分布，例如：

  • p50：一半乘客的等待时间不超过该值；
  • p90：90% 的乘客不超过该值，能反映较差情况下的体验；
  • 超过 30 秒或 90 秒的请求比例；
  • 乘客从呼叫到到达目的楼层的总时间；
  • 单位时间运送人数、停站次数和能耗；
  • 最长等待时间，用于检查是否有请求“饿死”。

平均值较低但 p90 很高的策略，会让大多数人感觉尚可，却让少数乘客等待很久。工程上往往需要多目标优化，而不是追求一个漂亮的平均数。

客流模式会改变最优策略

电梯调度没有对所有时段都最优的固定参数。办公楼常见的流量模式包括：

  • 早高峰：乘客集中从大堂前往各楼层；
  • 午间高峰：大堂与楼层间、楼层与楼层间的流量混合；
  • 晚高峰：乘客集中从办公楼层返回大堂；
  • 普通时段：请求较稀疏，方向和起点更分散。

早高峰时，可以提前让空闲电梯返回大堂并分批上行；晚高峰则可以把电梯预置到高需求楼层。现代算法还会使用历史数据预测客流，但预测错误时必须能够快速回退到实时调度。

目的层派梯：更多信息与更少自由

传统电梯只在厅外提供上、下按钮，乘客进入轿厢后再选择目的楼层。目的层派梯（Destination Dispatch）要求乘客在候梯厅先输入目标楼层，系统随后指定应乘坐的电梯。

它的优势是调度器提前知道完整行程，可以把目的楼层相近的乘客分到同一轿厢，减少中途停站。不过，被明确分配后，乘客和系统都失去了一部分临时改派的自由；多人同行却只输入一次目的层，也可能让系统低估实际人数。

参考文章中的模拟显示，在其特定楼层数、梯数、客流和重平衡规则下，目的层派梯并不总能缩短候梯时间；但这不能推广为现实系统的统一结论。学术研究通常把它建模为带容量约束、持续有新请求到达的动态分配问题，并使用滚动时域反复优化（参见论文 Assignment formulation for the Elevator Dispatching Problem with destination control）。评价时也应同时比较候梯时间、乘梯时间、容量利用率和总行程时间。

一个可实验的调度器框架

如果要自己实现电梯模拟器，可以将系统拆成事件模拟与调度策略两层：

1
2
3
4
5
6
7
8
9
10
11
12
事件层：
    passenger_arrived
    car_reached_floor
    door_opened / door_closed
    passenger_boarded / passenger_exited

调度层：
    1. 根据当前状态生成每部电梯的候选路线
    2. 估算新请求加入各路线后的成本
    3. 过滤超载、方向冲突等不可行方案
    4. 选择综合成本最低的电梯
    5. 在新事件发生后重新评估尚未完成的分配

测试时不要只随机生成均匀请求，而应分别模拟早高峰、晚高峰、层间流量、突发大客流和某部电梯停运。只有在相同客流种子下对比各项分位数，才能比较两个策略的真实差异。

总结

单部电梯可以用 LOOK 的“同向扫完再反向”获得简单且可预期的行为；多梯系统则需要根据 ETA、方向、负载和重复派梯等因素进行评分，并随状态变化动态重算。目的层派梯提供了更多信息，但也引入容量估计、乘客行为和改派灵活性等新约束。

电梯算法真正有趣的地方，不是找到一个永远正确的公式，而是在持续变化的请求中，让大多数人更快到达，同时不让少数人被遗忘。

参考资料