教培系统课表生成的约束求解方案从回溯算法到OR-Tools的实战演进
背景
教培机构的排课问题是一个经典的约束满足问题（CSP）。一个中型机构可能有50个老师、200个班级、10间教室、5个时间段，需要在满足各种约束条件下生成一份无冲突的课表。
我们最初用回溯算法实现了一版排课引擎，在小规模数据下运行良好。但当机构学员超过500人时，排课耗时从几秒飙升到几分钟甚至超时。今天分享我们从回溯算法迁移到Google OR-Tools约束求解器的过程和踩坑经验。
一、回溯算法的瓶颈
最初的排课引擎使用经典的回溯加剪枝策略。核心数据结构是一个三维矩阵：
// timeslot[teacher][class][room] = true/false
// 表示老师t在教室r给班级c上课是否可行
class ScheduleBacktracker:
def __init__(self, teachers, classes, rooms, timeslots):
self.teachers = teachers
self.classes = classes
self.rooms = rooms
self.timeslots = timeslots
self.assignment = {} # {class_id: (teacher_id, room_id, timeslot_id)}
def is_valid(self, class_id, teacher_id, room_id, timeslot_id):
# 检查教师时间冲突
for cid, (tid, rid, ts) in self.assignment.items():
if tid == teacher_id and ts == timeslot_id:
return False
# 检查教室时间冲突
if rid == room_id and ts == timeslot_id:
return False
# 检查教师跨校区通勤时间
teacher = self.teachers[teacher_id]
for cid, (tid, rid, ts) in self.assignment.items():
if tid == teacher_id:
time_diff = abs(ts - timeslot_id)
if time_diff == 1:
room1 = self.rooms[rid]
room2 = self.rooms[room_id]
if room1.campus != room2.campus:
return False # 相邻时段不同校区不可行
return True
def backtrack(self, class_ids):
if not class_ids:
return True
class_id = class_ids[0]
for teacher_id in self.teachers:
for room_id in self.rooms:
for timeslot_id in self.timeslots:
if self.is_valid(class_id, teacher_id, room_id, timeslot_id):
self.assignment[class_id] = (teacher_id, room_id, timeslot_id)
if self.backtrack(class_ids[1:]):
return True
del self.assignment[class_id]
return False
这个实现在50个班级以内时大约2到3秒出结果。但到了200个班级时，搜索空间爆炸，运行10分钟也排不完。即使加了MRV（最小剩余值）和LCV（最少约束值）启发式策略，改善也有限。
二、迁移到OR-Tools CP-SAT求解器
Google OR-Tools的CP-SAT求解器是我们找到的最佳替代方案。它内部使用了高效的约束传播和Lazy Clause Generation技术，处理大规模CSP问题的能力远超手写回溯。
核心思路是把排课问题建模为布尔变量矩阵：
from ortools.sat.python import cp_model
class ScheduleOptimizer:
def __init__(self, teachers, classes, rooms, timeslots):
self.model = cp_model.CpModel()
self.teachers = teachers
self.classes = classes
self.rooms = rooms
self.timeslots = timeslots
self.vars = {} # {class_id: {teacher_id: {room_id: {timeslot_id: BoolVar}}}}
def build_model(self):
# 创建布尔变量
for c in self.classes:
self.vars[c.id] = {}
for t in c.available_teachers:
self.vars[c.id][t] = {}
for r in self.rooms:
if r.type >= c.required_room_type:
self.vars[c.id][t][r] = {}
for ts in c.available_timeslots:
self.vars[c.id][t][r][ts] = self.model.NewBoolVar(
f'c{c.id}_t{t}_r{r.id}_ts{ts}'
)
# 约束1：每个班级恰好分配一个老师+教室+时间段
for c in self.classes:
all_vars = []
for t in self.vars[c.id]:
for r in self.vars[c.id][t]:
for ts in self.vars[c.id][t][r]:
all_vars.append(self.vars[c.id][t][r][ts])
self.model.AddExactlyOne(all_vars)
# 约束2：同一老师同一时间段只能上一门课
for t in self.teachers:
for ts in self.timeslots:
conflict_vars = []
for c in self.classes:
if t.id in self.vars.get(c.id, {}) and ts.id in self.vars[c.id][t.id].get(next(iter(self.vars[c.id][t.id])), {}):
for r in self.vars[c.id][t.id]:
if ts in self.vars[c.id][t.id][r]:
conflict_vars.append(self.vars[c.id][t.id][r][ts])
if len(conflict_vars) > 1:
self.model.AddAtMostOne(conflict_vars)
# 约束3：同一教室同一时间段只能有一门课
for r in self.rooms:
for ts in self.timeslots:
conflict_vars = []
for c in self.classes:
if c.id in self.vars:
for t in self.vars[c.id]:
if r.id in self.vars[c.id][t] and ts.id in self.vars[c.id][t][r.id]:
conflict_vars.append(self.vars[c.id][t][r.id][ts])
if len(conflict_vars) > 1:
self.model.AddAtMostOne(conflict_vars)
# 约束4：教师跨校区通勤约束
for t in self.teachers:
for ts_idx in range(len(self.timeslots) - 1):
ts1 = self.timeslots[ts_idx]
ts2 = self.timeslots[ts_idx + 1]
for r1 in self.rooms:
for r2 in self.rooms:
if r1.campus != r2.campus:
for c1 in self.classes:
for c2 in self.classes:
if c1.id != c2.id and t.id in self.vars.get(c1.id, {}) and t.id in self.vars.get(c2.id, {}):
v1 = self.vars[c1.id][t.id].get(r1.id, {}).get(ts1.id)
v2 = self.vars[c2.id][t.id].get(r2.id, {}).get(ts2.id)
if v1 and v2:
self.model.Add(v1 + v2 <= 1)
迁移过程中最大的坑是变量数量爆炸。200个班级乘以50个老师乘以10间教室乘以5个时间段，布尔变量数量达到50万个。OR-Tools虽然能处理这个规模，但内存占用很高。
解决方案是预处理阶段做激进的变量剪枝。对于每个班级，只保留真正可用的老师、教室和时间段组合，把不可能的组合直接从变量空间里剔除。实际操作后变量数量降到了5万左右，求解时间从超时降到8到12秒。
三、优化目标与软约束
排课不只是找到一份可行解，还要找到一份"好"的课表。比如老师不希望一天跑三个校区，教室不希望频繁切换，热门时间段应该优先分给大班课。
这些是软约束，不能硬性排除但可以设为优化目标。OR-Tools支持通过AddHint和Minimize来实现：
# 目标函数：最小化教师跨校区次数
cross_campus_count = []
for t in self.teachers:
for ts_idx in range(len(self.timeslots) - 1):
ts1 = self.timeslots[ts_idx]
ts2 = self.timeslots[ts_idx + 1]
for r1 in self.rooms:
for r2 in self.rooms:
if r1.campus != r2.campus:
for c1 in self.classes:
for c2 in self.classes:
if c1.id != c2.id:
v1 = self.vars[c1.id][t.id].get(r1.id, {}).get(ts1.id)
v2 = self.vars[c2.id][t.id].get(r2.id, {}).get(ts2.id)
if v1 and v2:
cross_campus = self.model.NewBoolVar(f'cc_{t.id}_{ts_idx}')
self.model.Add(v1 + v2 <= 1 + cross_campus)
cross_campus_count.append(cross_campus)
self.model.Minimize(sum(cross_campus_count))
加入优化目标后，求解时间增加到15到20秒，但生成的课表质量明显提升。教师跨校区次数平均减少了60%。
四、总结
从回溯算法迁移到OR-Tools的核心收获：
1. 约束满足问题不要自己写求解器，CP-SAT已经做了大量优化，性能远超手写方案。
2. 变量预处理比求解器优化更重要，减少变量数量是最有效的性能提升手段。
3. 软约束和优化目标的设计需要跟业务方反复对齐，不同机构对"好课表"的定义不同。
4. 求解时间控制在15秒以内是用户可接受的边界，超过这个时间需要加进度提示。