使用OR-Tools实现司机排班时出现不可行解的问题求助

问题背景 #

开发司机排班系统，要求每位司机每周至少休息1天，但运行代码后始终返回不可行解，输入数据与代码如下：

输入数据 #

dow  driver   hub
0      Sunday  1       S
1      Sunday  2       S
2      Sunday  3       S
3      Monday  1       S
4      Monday  2       S
5      Monday  3       S
6     Tuesday  2       S
7     Tuesday  3       S
8   Wednesday  1       S
9   Wednesday  3       S
10   Thursday  1       S
11   Thursday  2       S
12   Thursday  3       S
13     Friday  1       S
14     Friday  2       S
15   Saturday  1       S
16   Saturday  2       S
17   Saturday  3       S

运行代码 #

from ortools.sat.python import cp_model
import pandas as pd


def create_shift_schedule(drivers,
                          shifts,
                          week_days,
                          hubs,
                          min_shift_drivers,
                          max_shift_drivers,
                          driver_hubs_relationships):
    model = cp_model.CpModel()

    # 创建班次变量
    schedule = {}
    for e in drivers:
        for d in week_days:
            for s in shifts:
                for r in hubs:
                    schedule[(e, d, s, r)] = model.NewBoolVar(f'schedule_{e}_{d}_{s}_{r}')

    # 每位司机每天恰好分配一个班次（包括"Off"休息班次），且对应特定枢纽
    for e in drivers:
        for d in week_days:
            model.Add(sum(schedule[(e, d, s, r)] for s in shifts for r in hubs) == 1)

    # 满足每天、每个枢纽、每个班次的司机数量最小和最大值限制
    for d in week_days:
        for s in shifts:
            for r in hubs:
                min_drivers = min_shift_drivers.get((d, s, r), 0)
                max_drivers = max_shift_drivers.get((d, s, r), len(drivers))
                model.Add(sum(schedule[(e, d, s, r)] for e in drivers) >= min_drivers)
                model.Add(sum(schedule[(e, d, s, r)] for e in drivers) <= max_drivers)

    # 确保每位司机每周至少休息1天，最多休息3天
    for e in drivers:
        model.Add(sum(schedule[(e, d, "Off", r)] for d in week_days for r in hubs) >= 1)
    for e in drivers:
        model.Add(sum(schedule[(e, d, "Off", r)] for d in week_days for r in hubs) <= 3)

    # 限制司机只能分配到对应枢纽的班次
    for e in drivers:
        for r in hubs:
            if r not in driver_hubs_relationships[e]:
                for d in week_days:
                    for s in shifts:
                        model.Add(schedule[(e, d, s, r)] == 0)

    # 创建辅助变量，用于标记两位司机是否在同一天同一枢纽分配了相同的工作班次
    same_shift_aux = {}
    for e1 in drivers:
        for e2 in drivers:
            if e1 != e2:
                for d in week_days:
                    for s in shifts:
                        if s != "Off":
                            for r in hubs:
                                same_shift_aux[(e1, e2, d, s, r)] = model.NewBoolVar(
                                    f'same_shift_aux_{e1}_{e2}_{d}_{s}_{r}')

    # 添加约束关联辅助变量与班次变量
    for e1 in drivers:
        for e2 in drivers:
            if e1 != e2:
                for d in week_days:
                    for s in shifts:
                        if s != "Off":
                            for r in hubs:
                                model.AddImplication(schedule[(e1, d, s, r)],
                                                     same_shift_aux[(e1, e2, d, s, r)])
                                model.AddImplication(schedule[(e2, d, s, r)],
                                                     same_shift_aux[(e1, e2, d, s, r)])

    # 调整目标函数：最小化总工作班次数量，同时对同班次的司机组合施加惩罚
    penalty_for_same_shift = 1  # 调整此值控制同班次惩罚力度
    model.Minimize(
            sum(schedule[(e, d, s, r)] for e in drivers for d in week_days for s in shifts if
                s != "Off" for r in hubs)
            + penalty_for_same_shift * sum(
                    same_shift_aux[(e1, e2, d, s, r)] for e1 in drivers for e2 in drivers if
                    e1 != e2 for d in week_days for s in shifts if s != "Off" for r in hubs))

    # 求解排班问题
    solver = cp_model.CpSolver()
    solver.parameters.max_time_in_seconds = 300.0
    solver.parameters.log_search_progress = True
    status = solver.Solve(model)
    print(f"状态码 {status}")
    if status == cp_model.OPTIMAL:
        solution = {}
        for e in drivers:
            solution[e] = {}
            for d in week_days:
                for s in shifts:
                    for r in hubs:
                        if solver.Value(schedule[(e, d, s, r)]) == 1:
                            solution[e][d] = (s, r)
        return solution
    else:
        return None


file = pd.DataFrame(input_data) # 从文件加载数据

file['driver'] = file['driver'].apply(lambda x: str(x))

drivers = file['driver'].unique().tolist()
num_shifts = 2  # 包含"Off"休息班次
# 创建班次列表
shifts = ["Off"] + [f"Shift_{d}" for d in range(1, num_shifts)]
week_days = ['Monday', 'Tuesday', 'Wednesday', 'Thursday', 'Friday', 'Saturday', 'Sunday']
hubs = file['hub'].unique().tolist()

# 统计每天每个枢纽需要的司机数量
hub_counts = \
    pd.DataFrame(file.groupby(['dow', 'hub'],
                              as_index=False)['driver'].count())

fixed_shift_drivers_per_day_hub = {
    day: {
        hub: driver_count
        for hub, driver_count in zip(hub_counts[hub_counts['dow'] == day]['hub'],
                                     hub_counts[hub_counts['dow'] == day]['driver'])
    }
    for day in week_days
}
min_shift_drivers = {
    (day, shift, hub): 1
    for day in week_days
    for shift in shifts
    for hub in hubs
}

max_shift_drivers = {
    (day, shift, hub): fixed_shift_drivers_per_day_hub[day][hub] if shift != "Off" else 0
    for day in week_days
    for shift in shifts
    for hub in hubs
}

driver_hubs_relationships = \
    pd.DataFrame(file.groupby('driver')['hub'].apply(list)).reset_index()
driver_hubs_relationships = \
    {key: value for key, value in zip(driver_hubs_relationships['driver'],
                                      driver_hubs_relationships['hub'])}


solution = create_shift_schedule(drivers, shifts, week_days, hubs, min_shift_drivers,
                                 max_shift_drivers, driver_hubs_relationships)

if solution:
    for e in drivers:
        print(f"{e}:")
        for d in week_days:
            print(f"  {d}: {solution[e][d]}")
else:
    print("未找到可行解。")

问题根源与修复方案 #

1. 班次约束矛盾 #

当前代码中min_shift_drivers设置为所有班次（包括"Off"）每天每个枢纽至少1名司机，但max_shift_drivers中"Off"班次的最大值被设为0，直接导致min >=1且max <=0的矛盾约束，这是无解的核心原因。

修复：
仅对工作班次设置最小司机数，"Off"班次最小司机数设为0：

min_shift_drivers = {}
for day in week_days:
    for shift in shifts:
        for hub in hubs:
            if shift != "Off":
                # 工作班次最小司机数匹配输入数据的当日枢纽需求
                min_shift_drivers[(day, shift, hub)] = fixed_shift_drivers_per_day_hub.get(day, {}).get(hub, 0)
            else:
                min_shift_drivers[(day, shift, hub)] = 0

2. 班次命名与逻辑冗余 #

原代码生成的班次列表为["Off", "Shift_1"]，但辅助变量的同班次惩罚逻辑会对所有同工作班次的司机组合施加惩罚，而当前场景仅需一个工作班次，惩罚逻辑会额外增加求解复杂度，甚至干扰可行解的搜索。

修复：
简化班次命名，暂时注释掉辅助变量与惩罚逻辑，先确保找到可行解：

# 简化班次命名
shifts = ["Off", "Work"]

# 注释掉辅助变量相关代码
# same_shift_aux = {}
# ...（省略辅助变量定义、关联约束）

# 使用基础目标函数：最小化总工作班次数量
model.Minimize(sum(schedule[(e, d, s, r)] for e in drivers for d in week_days for s in shifts if s != "Off" for r in hubs))

3. 总需求与休息约束的匹配验证 #

3位司机每周至少休息1天、最多休息3天，总工作天数范围为12-18天。输入数据的总工作需求恰好为18天（3+3+2+2+3+2+3），因此必须让每位司机恰好休息1天才能满足需求，原代码的max 3 off shifts约束无需调整。

修复后预期结果 #

修复后运行代码，将得到符合要求的可行解，例如：

• 司机1：周二休息，其余6天在枢纽S上班
• 司机2：周三休息，其余6天在枢纽S上班
• 司机3：周五休息，其余6天在枢纽S上班

该方案完全满足所有约束条件与需求。

内容的提问来源于stack exchange，提问作者azal