引言
电梯作为现代高层建筑和复杂交通枢纽的核心垂直运输工具，其调度算法直接影响乘客的等待时间、系统的能源消耗以及整体运行效率。随着城市化进程加速和建筑规模扩大，多梯系统（Multi-Elevator System）的优化变得尤为关键。传统的电梯调度往往依赖简单的“先来先服务”或固定分区策略，但这些方法在高负载场景下容易导致长等待时间和资源浪费。本文将从经典算法入手，逐步探讨前沿技术，重点分析如何平衡乘客等待时间与系统效率。我们将通过理论解释、伪代码示例和实际案例，详细说明每种算法的原理、优缺点及优化策略，帮助读者理解从简单规则到智能AI的演进路径。
经典电梯调度算法
经典算法奠定了电梯调度的基础，主要基于规则驱动的逻辑，易于实现但适应性有限。这些算法通常适用于低到中等负载的单梯或简单多梯系统。
1. 先来先服务（FCFS, First-Come-First-Served）
FCFS 是最基本的调度策略，类似于操作系统的进程调度。它将所有呼叫请求（包括内部目标楼层和外部召唤）放入一个队列，按到达顺序处理。
工作原理
：电梯忽略方向，只按队列顺序移动。例如，如果电梯在1楼，而队列为[5楼（上行召唤）、3楼（内部目标）、10楼（下行召唤）]，它会先去5楼，然后3楼，最后10楼。
优缺点
：
优点
：简单、公平，无饥饿问题（所有请求最终都会被服务）。
缺点
：效率低下，尤其在多梯系统中，可能导致“乒乓效应”（电梯频繁上下切换），增加能耗和等待时间。平均等待时间可达20-30秒，在高峰期易造成拥堵。
优化多梯系统
：在多梯系统中，可结合“最小队列分配”，将新请求分配给队列最短的电梯。伪代码示例（Python风格）：
class FCFS_Elevator:
def __init__(self, id, current_floor):
self.id = id
self.current_floor = current_floor
self.queue = [] # 存储请求队列
def add_request(self, floor):
self.queue.append(floor) # 添加请求到队列末尾
def move(self):
if not self.queue:
return
target = self.queue.pop(0) # 取队列第一个
direction = 1 if target > self.current_floor else -1
while self.current_floor != target:
self.current_floor += direction
print(f”Elevator {self.id} moving to floor {self.current_floor}”)
print(f”Elevator {self.id} arrived at floor {target}”)
# 示例：多梯分配
elevators = [FCFS_Elevator(1, 0), FCFS_Elevator(2, 5)]
requests = [3, 8, 2] # 外部召唤
for req in requests:
# 简单分配：选择当前队列最短的电梯
best_elevator = min(elevators, key=lambda e: len(e.queue))
best_elevator.add_request(req)
print(f”Assigned request {req} to Elevator {best_elevator.id}”)
此代码展示了如何在多梯环境中分配请求，但实际中需扩展为实时监控队列长度。
2. 扫描算法（SCAN，又称电梯算法）
SCAN 模拟真实电梯的运行：电梯沿一个方向移动，服务所有沿途请求，直到尽头再反转方向。这避免了FCFS的随机性。
工作原理
：电梯有“当前方向”（上行或下行）。在上行时服务所有上行召唤和内部目标，直到最高请求楼层，然后反转下行。多梯系统中，可将楼层分区（如电梯1服务1-10楼，电梯2服务11-20楼）。
优缺点
：
优点
：减少方向切换，平均等待时间较FCFS降低30-50%；公平性好，无饥饿。
缺点
：在低负载时可能“空跑”（服务空闲楼层）；高峰期仍可能有长等待，因为不考虑请求密度。
优化多梯系统
：使用动态分区或负载均衡。例如，根据实时请求调整分区边界。伪代码示例：
class SCAN_Elevator:
def __init__(self, id, current_floor, max_floor=20):
self.id = id
self.current_floor = current_floor
self.direction = 1 # 1: up, -1: down
self.up_queue = [] # 上行请求
self.down_queue = [] # 下行请求
def add_request(self, floor, direction=None):
if direction is None:
direction = 1 if floor > self.current_floor else -1
if direction == 1:
self.up_queue.append(floor)
self.up_queue.sort()
else:
self.down_queue.append(floor)
self.down_queue.sort(reverse=True)
def move(self):
while self.up_queue or self.down_queue:
if self.direction == 1:
# 上行模式
while self.up_queue and self.up_queue[0] >= self.current_floor:
target = self.up_queue.pop(0)
self._move_to(target)
if not self.up_queue:
self.direction = -1
else:
# 下行模式
while self.down_queue and self.down_queue[0] <= self.current_floor:
target = self.down_queue.pop(0)
self._move_to(target)
if not self.down_queue:
self.direction = 1
def _move_to(self, target):
while self.current_floor != target:
self.current_floor += self.direction
print(f"Elevator {self.id} moving {self.direction} to floor {self.current_floor}")
print(f"Elevator {self.id} stopped at floor {target}")
# 示例：多梯SCAN与分区
elevators = [SCAN_Elevator(1, 0), SCAN_Elevator(2, 10)]
requests = [(3, 1), (8, -1), (15, 1)] # (floor, direction)
for floor, dir in requests:
# 分区：floor <=10 -> elevator1, else elevator2
if floor <= 10:
elevators[0].add_request(floor, dir)
else:
elevators[1].add_request(floor, dir)
此实现展示了方向维护和队列管理，在多梯中可通过中央控制器协调分区。
3. 最短寻找时间优先（SSTF, Shortest Seek Time First）
SSTF 选择离当前电梯位置最近的请求，优先服务。
工作原理
：计算所有请求与当前位置的距离，选择最小值。多梯系统中，分配请求给最近电梯。
优缺点
：
优点
：响应快，平均等待时间短（比SCAN低10-20%）。
缺点
：可能导致远距离请求饥饿；在多梯中需全局优化，否则局部最优非全局最优。
优化
：结合SCAN，避免饥饿。伪代码：
class SSTF_Elevator:
def __init__(self, id, current_floor):
self.id = id
self.current_floor = current_floor
self.requests = []
def add_request(self, floor):
self.requests.append(floor)
def move(self):
while self.requests:
# 找最近请求
nearest = min(self.requests, key=lambda f: abs(f - self.current_floor))
self.requests.remove(nearest)
direction = 1 if nearest > self.current_floor else -1
while self.current_floor != nearest:
self.current_floor += direction
print(f”Elevator {self.id} moving to {self.current_floor}”)
print(f”Arrived at {nearest}”)
经典算法在简单场景有效，但面对高峰期多梯负载不均时，效率仅为现代算法的60-70%。
中级优化算法：考虑多因素的策略
随着计算能力提升，算法开始整合等待时间、负载和能耗等多维度优化。
1. 成本函数法（Cost-Based Scheduling）
为每个请求计算“成本”，如等待时间成本 + 移动距离成本 + 能耗成本，选择成本最低的电梯。
工作原理
：成本 = α * 等待时间 + β * 距离 + γ * 负载。α,β,γ 为权重。多梯系统中，中央控制器评估所有电梯的成本。
优化多梯效率
：动态调整权重，例如高峰期增加等待时间权重。伪代码：
import time
class CostScheduler:
def __init__(self, elevators):
self.elevators = elevators
self.request_times = {} # 记录请求时间
def assign_request(self, floor, direction):
current_time = time.time()
best_elevator = None
min_cost = float(‘inf’)
for elevator in self.elevators:
wait_time = current_time – self.request_times.get((floor, direction), current_time)
distance = abs(floor – elevator.current_floor)
load = len(elevator.queue) # 当前负载
cost = 0.5 * wait_time + 1.0 * distance + 0.2 * load # 权重示例
if cost < min_cost:
min_cost = cost
best_elevator = elevator
best_elevator.add_request(floor)
print(f"Assigned to Elevator {best_elevator.id} with cost {min_cost:.2f}")
# 示例
elevators = [SCAN_Elevator(1, 0), SCAN_Elevator(2, 5)]
scheduler = CostScheduler(elevators)
scheduler.assign_request(3, 1) # 计算成本后分配
此方法可将平均等待时间缩短至15秒以下，但需实时数据支持。
2. 遗传算法（Genetic Algorithm, GA）在多梯优化中的应用
GA 是一种进化算法，用于搜索最优调度序列。它将调度方案编码为“染色体”，通过选择、交叉、变异进化。
工作原理
：
编码
：染色体表示电梯分配序列，如[电梯1服务请求A,B]。
适应度函数
：评估方案的总等待时间 + 总移动距离。
进化
：迭代100-500代，选择高适应度个体，交叉变异。
优缺点
：
优点
：全局优化，适合复杂多梯场景，可处理非线性约束（如最大载重）。
缺点
：计算密集，实时性差；需调参。
优化乘客等待时间
：在高峰期预计算调度方案。伪代码示例（简化版）：
import random
class GA_Scheduler:
def __init__(self, requests, num_elevators=3, population_size=50):
self.requests = requests # 请求列表
self.num_elevators = num_elevators
self.population_size = population_size
def fitness(self, chromosome):
# chromosome: [elevator_id for each request]
total_wait = 0
total_distance = 0
elevators_pos = [0] * self.num_elevators # 初始位置
for i, req in enumerate(self.requests):
elev_id = chromosome[i]
distance = abs(req - elevators_pos[elev_id])
total_distance += distance
total_wait += distance # 简化等待时间
elevators_pos[elev_id] = req
return -(total_wait + total_distance) # 负值最大化
def crossover(self, parent1, parent2):
point = random.randint(1, len(parent1)-1)
child = parent1[:point] + parent2[point:]
return child
def mutate(self, chromosome):
idx = random.randint(0, len(chromosome)-1)
chromosome[idx] = random.randint(0, self.num_elevators-1)
return chromosome
def evolve(self, generations=100):
population = [[random.randint(0, self.num_elevators-1) for _ in self.requests] for _ in range(self.population_size)]
for gen in range(generations):
population = sorted(population, key=self.fitness, reverse=True)[:self.population_size//2]
new_pop = population[:]
while len(new_pop) < self.population_size:
p1, p2 = random.sample(population, 2)
child = self.crossover(p1, p2)
if random.random() < 0.1: # 变异率
child = self.mutate(child)
new_pop.append(child)
population = new_pop
best = max(population, key=self.fitness)
return best # 返回最优分配
# 示例：高峰期10个请求
requests = [5, 10, 3, 8, 12, 2, 15, 7, 9, 4]
ga = GA_Scheduler(requests, num_elevators=2)
best_assignment = ga.evolve()
print(f"Optimal assignment: {best_assignment}")
# 输出如 [0,1,0,1,1,0,1,0,1,0]，表示每个请求分配给哪个电梯
GA 可将多梯系统效率提升20-40%，但需离线计算或结合实时启发式。
前沿技术：AI与智能优化
前沿算法引入机器学习和实时数据，处理动态多梯环境，如建筑物联网（IoT）数据。
1. 基于强化学习的调度（Reinforcement Learning, RL）
RL 让电梯系统通过试错学习最优策略。使用Q-Learning或Deep Q-Network (DQN)。
工作原理
：
状态
：电梯位置、方向、队列长度、等待时间。
动作
：选择下一个目标。
奖励
：负等待时间 + 负距离 + 正负载均衡。
训练
：模拟环境训练模型，部署时实时决策。
优化多梯效率
：RL 可动态适应负载变化，减少平均等待时间至10秒以下。缺点：训练数据需求大。
代码示例
（使用伪代码模拟Q-Learning，实际需TensorFlow/PyTorch）：
import numpy as np
class RL_Scheduler:
def __init__(self, num_states=20*2*5, num_actions=20): # 状态: floor*direction*load, 动作: target floor
self.q_table = np.zeros((num_states, num_actions))
self.alpha = 0.1 # 学习率
self.gamma = 0.9 # 折扣因子
self.epsilon = 0.2 # 探索率
def get_state(self, elevator):
# 简化状态编码: floor * 2 + direction + load*5
return int(elevator.current_floor * 2 + (1 if elevator.direction == 1 else 0) + min(len(elevator.queue), 4) * 5)
def choose_action(self, state):
if random.random() < self.epsilon:
return random.randint(0, 19) # 随机探索
return np.argmax(self.q_table[state])
def update_q(self, state, action, reward, next_state):
best_next = np.max(self.q_table[next_state])
self.q_table[state, action] += self.alpha * (reward + self.gamma * best_next - self.q_table[state, action])
def train_step(self, elevator, request):
state = self.get_state(elevator)
action = self.choose_action(state)
# 模拟执行动作
distance = abs(action - elevator.current_floor)
wait_time = distance # 简化
reward = - (wait_time + distance) # 奖励负值
elevator.add_request(action)
next_state = self.get_state(elevator)
self.update_q(state, action, reward, next_state)
return action
# 示例训练循环（简化）
scheduler = RL_Scheduler()
elevator = SCAN_Elevator(1, 0)
for _ in range(1000): # 训练步
req = random.randint(1, 19)
action = scheduler.train_step(elevator, req)
print(f"Learned action {action} for request {req}")
实际应用中，如Otis的RL系统，已在测试中将能耗降低15%。
2. 混合AI系统：结合预测与优化
前沿系统使用LSTM预测乘客流量，结合GA或RL优化。例如，Google的电梯AI使用历史数据预测高峰，提前调整电梯位置。
案例
：在多梯系统中，预测模型输入时间、天气、事件数据，输出未来5分钟请求分布。调度器据此预分配电梯。
优化乘客等待时间
：预测可将高峰期等待时间减少25%。实现需大数据平台。
结论与建议
从FCFS到RL，电梯调度算法演进体现了从规则到智能的转变。经典算法适合低成本系统，中级优化如成本函数和GA 提供了平衡，而前沿RL和预测AI则最大化多梯效率，目标是将平均等待时间控制在10-15秒，能耗降低20%以上。实际部署时，建议从SCAN起步，逐步集成AI模块，并监控KPI如平均等待时间（AWT）和系统吞吐量。未来，边缘计算和5G将进一步提升实时性，推动电梯系统向“零等待”愿景迈进。通过这些算法，建筑管理者可显著提升乘客体验和运营效益。