电梯算法漫谈：一台电梯是如何学会调度的？
目录
不知道你有没有遇到过这样的情况。
明明只是等一台电梯，却发现它迟迟不肯下来。好不容易看着显示屏上的数字逐渐接近自己所在的楼层，它却突然停住，甚至转头去了另一个方向。
有时候难免让人有些焦躁：这台电梯到底在干什么？
其实，我一直对电梯背后的运行逻辑非常好奇。每当站在电梯门口，看着楼层数字不断变化时，我总会忍不住思考：它究竟是如何决定下一站的？为什么有时会在中途停靠，有时却对某一层的呼叫视而不见？
看似简单的上下移动，背后其实隐藏着一个很有意思的问题：调度。
不妨尝试从零开始设计一套电梯调度算法，看看我们能否从最朴素的规则出发，一步步推导出更合理的运行方式。
这篇文章计划分为上下两篇：
- 上篇：只考虑一台电梯，探讨最基础的调度问题。
- 下篇：当多台电梯同时运行时，它们又该如何协作？
本篇先从最简单的单台电梯开始。
一、先来先服务，真的公平吗？
假设有一栋六层楼的建筑，只有一台电梯，运行范围为 1～6 楼。
为了让问题尽可能简单，我们暂时忽略载重、开关门耗时、加减速等因素，只关注电梯应该如何决定自己的运行顺序。
现在，电梯停在 1 楼。
3 楼的乘客先按下了上行按钮，紧接着，2 楼的乘客也按下了上行按钮。假设两位乘客最终都准备前往 6 楼，而且两个请求都在电梯出发前产生。
那么，电梯应该先去哪里？
最符合直觉的答案可能是：既然 3 楼先按下按钮，那就先服务 3 楼的乘客。
这实际上是一种很常见的调度思想，叫作先来先服务（First Come, First Served，简称 FCFS）。
如果严格遵循这条规则，并且每次都先完成一位乘客的行程，电梯就会这样运行：
先来先服务（FCFS）
1 → 3 → 6 → 2 → 6
└─ ① ─┘
└─ ② ─┘
① 接 3 楼乘客，送往 6 楼
② 返回 2 楼，接人后再次前往 6 楼
累计运行距离：13 层乍看之下，这套规则并没有什么问题。
毕竟先按按钮的人先得到服务，似乎十分公平。
但仔细观察这条路线，就会发现一个明显的问题。
电梯从 1 楼前往 3 楼时，明明会经过 2 楼，却因为 2 楼的乘客稍晚按下按钮，就直接忽略了他的请求。
随后，电梯又不得不从 6 楼返回 2 楼，最后重新上行至 6 楼。
如果只是为了遵守请求的时间顺序，让电梯反复往返，显然不是一个高效的方案。
那么，我们能不能稍微改变一下规则？
既然电梯本来就需要上行，而且两位乘客都准备前往 6 楼，为什么不顺路把他们一起接上呢？
于是，路线变成了：
顺路接人
1 → 2 → 3 → 6
↑ ↑
接人 接人
累计运行距离：5 层原本需要经过 13 层的运行距离，现在只需要经过 5 层。
当然，这不代表真实的乘梯时间也会按照同样的比例缩短。毕竟每次停靠还需要减速、开门和关门，但至少我们避免了大量不必要的移动。
有意思的是，新方案打破了最初的规则。
3 楼的乘客虽然先按下按钮，电梯却先接到了 2 楼的乘客。
为了提高整体效率，我们允许服务顺序发生变化。
这也引出了电梯调度中的第一个问题：
能不能在兼顾公平的同时，让电梯运行得更加高效？
二、电梯究竟知道些什么？
在继续优化之前，我们需要先弄清楚一件事情：电梯究竟能够获得哪些信息？
仔细观察就会发现，传统电梯通常有两类按钮。
一类位于电梯外部，也就是我们经常使用的上行和下行按钮；另一类位于电梯内部，用来选择具体的目的楼层。
两者看起来都只是按钮，但传递给调度系统的信息却不一样。
我们可以简单画出它们的关系：
电梯调度器
│
┌──────────┴──────────┐
│ │
厅外呼叫 轿内指令
│ │
↑ / ↓ 1～6 楼
│ │
想往哪个方向？ 想去几楼？
│ │
└──────────┬──────────┘
│
决定运行与停靠例如，3 楼有人按下上行按钮。
此时，电梯只知道这位乘客想往上走，却不知道他准备前往 4 楼、5 楼还是 6 楼。
只有当乘客进入轿厢，按下具体的楼层按钮后，电梯才能知道他的目的地。
因此，我们可以把请求分成两类：
- 厅外呼叫：由所在楼层和期望方向组成，例如「3 楼，上行」。
- 轿内指令：表示乘客的目的楼层，例如「前往 6 楼」。
除此之外，电梯还需要知道自己的当前位置、当前运行方向，以及有哪些请求尚未处理。
如果用一种类似程序状态的方式来描述，大概是这样：
电梯状态
当前位置：1 楼
运行方向：待机
厅外上行请求：[2]
厅外下行请求：[3]
轿内目的楼层：[]这里有个容易忽略的细节：同一楼层可能同时有人想上楼，也有人想下楼。因此，不能只用一个楼层数字来代表所有厅外呼叫。
而对于轿内的楼层按钮，我们只需要知道有哪些目的楼层需要停靠。
至此，最基础的调度信息就已经齐全了。
接下来，我们可以尝试让电梯根据这些信息，做出更加合理的决策。
三、顺路接人，但不是见人就停
回到最初的六层楼。
这一次，我们换一个场景：
- 电梯停在 1 楼。
- 2 楼有人按下上行按钮，准备前往 6 楼。
- 3 楼有人按下下行按钮，准备前往 1 楼。
按照前面得出的经验，我们应该尽量顺路接人。
那么，当电梯从 2 楼前往 6 楼时，经过 3 楼是不是也应该停下来？
答案并没有那么简单。
因为 3 楼的乘客想要下楼，而电梯当前正在上行。
如果立即接上这位乘客，就可能出现两种情况。
第一种是电梯直接掉头，先将 3 楼的乘客送回 1 楼。但这样一来，已经进入电梯、准备前往 6 楼的乘客就不得不跟着返回。
第二种是先让这位乘客跟着电梯前往 6 楼，再一起下行。虽然电梯没有立即改变方向，但这位乘客反而多走了一段完全没有必要的路。
两种方式都不够理想。
这时，我们就可以尝试引入一条新的规则：
电梯沿某个方向运行时，优先处理该方向上的请求，尽量避免中途反复掉头。
也就是说，当电梯正在上行时：
- 遇到轿内乘客选择的目的楼层，可以停靠。
- 遇到同样希望上行的厅外乘客，可以顺路接人。
- 遇到希望下行的厅外乘客，通常先记录请求，等待返程时处理。
于是，整个运行过程就变成了：
6 楼 ● 乘客下电梯，准备返程
│
5 楼 │
│
4 楼 │
│
3 楼 ○ 有人想下楼，先不接
│
2 楼 ● 接上行乘客
│
1 楼 ● 电梯出发
上行：1 → 2 → 6
下行：6 → 3 → 1
● 当前行程的停靠楼层
○ 等待反方向服务的楼层这样一来，电梯就不需要因为每一个新请求而频繁改变方向。
当然，这里还存在一种特殊情况。
假设电梯停在 1 楼，而整栋楼只有 3 楼的一位乘客按下了下行按钮。
难道电梯就不去接他了吗？
显然不是。
它仍然可以从 1 楼上行至 3 楼，然后改变方向，接上这位准备下行的乘客。
换句话说，方向优先并不意味着拒绝反方向请求，而是尽可能将同方向的服务组织在一起。
实际上，这已经非常接近现实电梯中常见的选择性集选控制（Selective Collective Control）思想。
它的核心不是严格按照按钮按下的时间顺序处理请求，而是结合运行方向和楼层位置，决定停靠的先后次序。
四、电梯一定要运行到最高层吗？
到这里，我们已经解决了一个明显的问题：电梯不再因为新的请求而频繁折返。
但新的问题又出现了。
假设电梯正在向上运行，它是不是一定要到达 6 楼，才能改变方向？
我们继续调整刚才的例子。
现在，2 楼的乘客不再前往 6 楼，而是准备去 4 楼。
3 楼依然有人等待下行，准备返回 1 楼。
如果电梯坚持运行到建筑物的最高层，路线就会变成：
1 → 2 → 4 → 6 → 3 → 1
↑
没有必要的移动显然，5 楼和 6 楼根本没有需要处理的请求。
既然如此，电梯为什么还要继续上行？
更合理的路线应该是：
1 → 2 → 4 → 3 → 1
↑
上行任务完成
开始返程这样，我们又得出了一条新的规则：
当当前方向已经没有更远的待处理请求时，电梯就可以考虑改变方向，而不必每次都到达建筑物的最高层或最低层。
不过，这里的「待处理请求」并不只是轿内按钮。
比如，在刚才的例子中，如果 5 楼还有一位等待下行的乘客，电梯就不能只因为 4 楼是轿内乘客的最高目的地，而直接掉头返回。
它还需要前往 5 楼，响应那里的下行呼叫。
所以，决定电梯何时折返的，不是建筑物的高度，也不只是轿内乘客的目的地，而是整个系统中尚未完成的请求。
那么，如果所有请求都已经处理完毕，电梯又该怎么办？
最简单的方式，就是停在当前楼层，等待下一次呼叫。
当然，现实中有些电梯会在空闲一段时间后，主动返回预设的待机楼层，比如 1 楼。这属于进一步的调度策略，我们暂时不展开。
五、原来，电梯调度可以这么简单
回顾前面的推导，其实我们只做了几次很自然的调整。
最初，我们采用先来先服务的规则，发现这种方式虽然直观，却可能造成大量不必要的往返。
于是，我们开始尝试顺路接人。
随后又发现，顺路并不代表经过任何楼层都应该停靠，还需要考虑乘客希望前往的方向。
最后，我们意识到电梯也没有必要运行到建筑物的尽头，而应该根据尚未完成的请求，决定何时改变方向。
如果把这些规则组合起来，就形成了一套相对简单的调度流程：
收到新的请求
│
▼
记录请求信息
│
▼
确定运行方向
│
▼
沿当前方向运行
│
▼
是否需要在此停靠？
│ │
是 否
│ │
开门服务 继续运行
└────┬────┘
│
▼
前方还有待处理请求吗？
│ │
有 没有
│ │
继续前进 考虑掉头
│
▼
还有其他请求吗？
│ │
有 没有
│ │
继续调度 待机上面是一张简化的流程图。如果将其中的主要决策进一步转换成伪代码，大概是这样：
当电梯准备进行下一步调度时：
如果当前楼层有需要服务的请求：
停靠，处理对应请求
如果当前方向的前方还有请求：
继续朝当前方向运行
否则：
如果还有其他尚未处理的请求：
根据请求位置改变方向
继续提供服务
否则：
进入待机状态当然，这里的「需要服务」，还要考虑厅外请求的方向。例如，上行过程中遇到下行呼叫，通常不会立即停靠。
而当电梯恰好到达最远的反方向呼叫楼层时，则可以先切换方向，再提供服务。
虽然我们并没有引入复杂的数学公式，但已经能够理解一套基础的电梯调度机制。
六、这和计算机中的电梯算法有什么关系？
如果你接触过操作系统，可能会觉得前面的调度思路似曾相识。
事实上，在传统磁盘调度中，也存在一种被称为「电梯算法」的调度方式。
它的名字叫作 SCAN。
传统机械硬盘需要移动磁头，才能读取不同位置的数据。如果每次都按照请求到达的先后顺序移动磁头，就可能出现大量来回寻道。
于是，SCAN 采用了一种类似电梯的思路：磁头沿一个方向移动，依次处理途经位置的请求，到达边界后再反向移动。
听起来是不是十分熟悉？
不过，按照经典定义，SCAN 通常会一直移动到磁盘的物理边界，而我们前面设计的电梯，并不一定需要运行到最高层或最低层。
这就涉及另一种磁盘调度算法：LOOK。
LOOK 会观察当前方向上是否还有未完成的请求。如果已经没有，就不必继续移动到磁盘边界，而是可以提前改变方向。
这与我们在第四节推导出的优化思路十分相似。
但这里需要区分两个概念：
一方面，SCAN 和 LOOK 是经典的磁盘调度算法。
另一方面，真实电梯还需要考虑厅外上下行方向、轿内目的楼层、载重、乘客等待时间以及安全控制等因素。
因此，我们可以借助 SCAN 和 LOOK 理解方向调度的思想，却不能直接将它们等同于真实电梯的完整控制程序。
这也正是算法有趣的地方。
两个看似完全不同的问题，可能隐藏着十分相似的解决思路。
七、效率提高了，公平问题就解决了吗？
到这里，我们似乎已经得到了一套相对合理的调度方案。
但如果再仔细思考，就会发现新的问题。
假设一台电梯正在上行，而你恰好在它刚刚经过的楼层按下上行按钮。
此时，即使电梯距离你只有一层楼，你也可能不得不等它处理完前方的请求，再折返回来。
从你的角度来看，这似乎并不公平。
可如果电梯立即掉头，又可能影响已经进入电梯的乘客。
这让我们不得不重新思考：究竟什么才叫公平？
是严格按照按钮按下的时间先后提供服务，还是尽量缩短所有乘客的平均等待时间？
又或者，我们应该优先照顾那些已经等待很久的人？
事实上，这些目标并不总能同时实现。
尤其是当新的请求不断出现时，调度器不仅需要提高整体效率，还需要避免某些请求长期得不到响应。
因此，真实的电梯系统往往还会考虑更多因素，例如等待时间、载重、客流量以及不同时段的运行策略。
本文推导出的，只是理解单台电梯调度的一种基础模型，并不意味着所有电梯都会严格遵循完全相同的规则。
但至少现在，当我们再次站在电梯门口，看到它经过自己所在的楼层却没有停下时，就能够从调度的角度，尝试理解它的行为了。
八、动手实践：用 TypeScript 模拟电梯调度
前面的内容已经足以理解电梯调度的基本思想。
如果你对编程感兴趣，我们还可以继续尝试，把刚才推导出的规则写成代码。
这里仍然只考虑一台运行于 1～6 楼的电梯。
我们不模拟开门、关门、载重和加减速，而是让程序每执行一次 step()，就进行一次运行决策。
首先，定义电梯的状态：
type Direction = -1 | 0 | 1;
// -1：下行
// 0：待机
// 1：上行
class Elevator {
floor = 1;
direction: Direction = 0;
// 厅外请求：按方向分别记录
private up = new Set<number>();
private down = new Set<number>();
// 轿内请求：具体目的楼层
private inside = new Set<number>();
}之所以使用 Set，是因为同一个楼层、同一方向的呼叫，只需要记录一次。
例如，即使 2 楼有三位乘客同时按下上行按钮，也不意味着电梯需要在 2 楼连续停靠三次。
接下来，我们将请求记录、方向判断以及停靠规则组合起来。
下面是一份完整的简化实现：
type Direction = -1 | 0 | 1;
class Elevator {
floor = 1;
direction: Direction = 0;
private up = new Set<number>();
private down = new Set<number>();
private inside = new Set<number>();
private validate(floor: number) {
if (!Number.isInteger(floor) || floor < 1 || floor > 6) {
throw new Error("楼层必须在 1～6 之间");
}
}
// 厅外乘客呼叫电梯
call(floor: number, direction: "up" | "down") {
this.validate(floor);
if (
(floor === 1 && direction === "down") ||
(floor === 6 && direction === "up")
) {
throw new Error("该楼层没有对应方向的按钮");
}
const calls = direction === "up" ? this.up : this.down;
calls.add(floor);
}
// 乘客进入电梯后选择目的楼层
select(floor: number) {
this.validate(floor);
this.inside.add(floor);
}
// 合并所有尚未处理的请求楼层
private pending(): number[] {
return [...new Set([
...this.up,
...this.down,
...this.inside,
])];
}
// 当前楼层是否需要停靠
private shouldStop(): boolean {
return (
this.inside.has(this.floor) ||
(this.direction === 1 && this.up.has(this.floor)) ||
(this.direction === -1 && this.down.has(this.floor))
);
}
// 当前方向的前方是否还有请求
private hasAhead(): boolean {
return this.pending().some(floor =>
this.direction === 1
? floor > this.floor
: floor < this.floor
);
}
// 完成当前楼层的对应请求
private stop(): string {
this.inside.delete(this.floor);
if (this.direction === 1) {
this.up.delete(this.floor);
} else if (this.direction === -1) {
this.down.delete(this.floor);
}
return `${this.floor} 楼停靠`;
}
// 模拟一次运行决策
step(): string {
const requests = this.pending();
if (requests.length === 0) {
this.direction = 0;
return `${this.floor} 楼待机`;
}
// 待机时，先选择最近的请求楼层
if (this.direction === 0) {
const nearest = requests.reduce((a, b) =>
Math.abs(a - this.floor) <= Math.abs(b - this.floor)
? a
: b
);
this.direction =
nearest > this.floor ? 1 :
nearest < this.floor ? -1 :
this.up.has(this.floor) ? 1 : -1;
}
// 前方没有请求时，考虑反向
if (!this.shouldStop() && !this.hasAhead()) {
this.direction = this.direction === 1 ? -1 : 1;
}
if (this.shouldStop()) {
return this.stop();
}
// 每次向当前方向移动一层
this.floor += this.direction;
// 到达折返点后，允许先掉头再接人
if (!this.shouldStop() && !this.hasAhead()) {
this.direction = this.direction === 1 ? -1 : 1;
}
if (this.shouldStop()) {
return this.stop();
}
return `${this.floor} 楼经过`;
}
}这段代码最核心的部分，其实只有三个判断：
- 当前楼层是否应该停靠？
- 当前方向的前方是否还有请求？
- 如果没有，应该改变方向还是进入待机？
我们用第四节的例子简单验证一下。
const elevator = new Elevator();
// 2 楼想上行，3 楼想下行
elevator.call(2, "up");
elevator.call(3, "down");
console.log(elevator.step()); // 2 楼停靠
// 2 楼乘客进入电梯，选择 4 楼
elevator.select(4);
console.log(elevator.step()); // 3 楼经过
console.log(elevator.step()); // 4 楼停靠
// 上行任务完成，准备处理下行请求
console.log(elevator.step()); // 3 楼停靠
// 3 楼乘客进入电梯，选择 1 楼
elevator.select(1);
console.log(elevator.step()); // 2 楼经过
console.log(elevator.step()); // 1 楼停靠最终得到的停靠顺序：
1 → 2 → 4 → 3 → 1正好符合前面推导出的调度规则。
需要说明的是，这段代码只是一个教学模型，重点在于表达请求、方向与停靠之间的关系。它采用同步、逐层执行的方式，没有模拟真实电梯的运行时间和开关门过程。
另外，乘客上下车也需要由外部示例代码配合完成。比如 select(4)，是我们在电梯停靠 2 楼后，模拟乘客进入轿厢并按下目的楼层。
在真正的电梯系统中，还需要处理异步事件、开关门状态、满载运行、故障保护以及更复杂的调度边界。
不过，对这篇文章来说，我们并不需要实现一个完整的电梯控制器。
只要能够通过几十行核心逻辑，把前面的调度思想表达出来，就已经达到了实践的目的。
九、写在最后
回过头看，一台电梯的运行逻辑，其实没有想象中那么神秘。
从最初的先来先服务，到顺路接人，再到依据方向集中处理请求，我们并没有引入复杂的数学公式，却已经能够逐步改善电梯的运行方式。
而这一切，最初不过是从一个很简单的问题开始：
为什么电梯明明经过了我的楼层，却没有停下来？
在尝试回答这个问题的过程中，我们逐渐发现，电梯并不是只需要考虑眼前的某位乘客，而是需要协调所有正在发生的请求。
有时候，暂时不为某个人停靠，反而可能是为了让整体运行更加高效。
当然，这还只是单台电梯的情况。
如果一栋建筑拥有三台、五台甚至更多电梯，它们又应该如何分配任务？
例如，三台电梯分别停在 1 楼、3 楼和 6 楼，此时 4 楼有人按下了上行按钮。
系统究竟应该派哪一台电梯前去接人？
距离最近的电梯，就一定是最合适的吗？
如果最近的电梯已经满载，又该怎么办？
这些问题就不再只是单台电梯内部的调度，而涉及多台电梯之间的协作。
下一篇，我们继续聊聊电梯群控调度，以及多台电梯如何分工，才能让整栋建筑的乘客等得更少。
延伸阅读
本文采用 CC BY-NC-SA 4.0 协议许可，转载请保留原文链接及作者。