OR-Tools调度模型始终无解，求问题排查与解决思路

问题背景 #

现有400名司机、45个枢纽，每日总司机需求约250人，司机与枢纽存在关联绑定关系。模型要求每位司机每周必须休息1天，但无论是否放宽绑定（允许司机任意枢纽工作），始终无法得到可行解。

排查思路 #

1. 休息日分布约束冲突 #

代码中通过average_off_days = len(drivers_list) // len(days)强制每天休息人数≥该值，但未匹配总休息人次的固定要求：

• 总休息人次固定为400（每人每周1天），若days * average_off_days < 400，仅靠≥average_off_days的约束无法凑够总休息人次，直接导致约束冲突。
• 例如一周7天场景：400//7=57，7*57=399，还差1个休息人次，但代码未允许某一天多安排1人休息，模型无法满足总休息要求。

2. 枢纽需求约束逻辑错误 #

代码中创建drivers_needed变量并使用10*实际人数 ≥9*需求变量的约束，存在两个核心问题：

• drivers_needed是变量而非固定需求值，模型可通过抬高变量值规避实际需求的满足，导致需求约束失效。
• 10/9的系数设计无明确业务逻辑，模糊了“必须满足枢纽需求”的核心要求。

3. 变量规模过大（潜在求解效率问题） #

原模型使用len(drivers)*(1+len(hubs))*len(days)个布尔变量（约12.8万），虽400司机的规模不算极端，但过多变量会增加求解器的搜索难度，可能导致在500秒内无法找到可行解（即使存在解）。

4. 隐性约束冲突 #

需确认：

• 是否存在司机的可工作枢纽仅包含OFF（即原关联枢纽为空），导致该司机需每天休息，但与“每周仅休息1天”的约束冲突。
• 每日总需求是否超过当日最大可上班司机数（总司机数-当日休息人数）。

解决方案 #

1. 修正休息日分布约束 #

将均匀分布约束调整为精确匹配总休息人次，避免冲突：

# 替换原休息日分布约束代码
total_drivers = len(drivers_list)
average_off_days = total_drivers // len(days)
remainder = total_drivers % len(days)

for idx, d in enumerate(days):
    if idx < remainder:
        # 前remainder天每天多安排1人休息
        model.Add(off_days[d] == average_off_days + 1)
    else:
        model.Add(off_days[d] == average_off_days)

2. 重构枢纽需求约束 #

直接使用固定需求值，强制实际安排人数≥需求：

# 移除原drivers_needed变量创建代码，替换为以下约束
for d in days:
    total_daily_demand = 0
    for r in hubs_list:
        if r != 'OFF':
            hub_demand = hubs_list_and_demand.loc[hubs_list_and_demand['hub'] == r, 'drivers_needed']
            drivers_needed_at_hub = int(hub_demand.values[0]) if len(hub_demand) > 0 else 0
            total_daily_demand += drivers_needed_at_hub
            # 强制实际安排人数≥需求
            model.Add(sum(schedule[(e, d, r)] for e in drivers_list) >= drivers_needed_at_hub)
    # 额外添加：当日可上班人数≥总需求，提前暴露冲突
    model.Add((total_drivers - off_days[d]) >= total_daily_demand)

3. 简化变量结构（可选但推荐） #

将多布尔变量改为单整数变量，大幅减少变量数量：

# 替换原schedule变量创建代码
hub_to_idx = {r: idx for idx, r in enumerate(hubs_list)}
schedule = {}
for e in drivers_list:
    for d in days:
        # 每个司机每天对应一个枢纽/休息的索引值
        schedule[(e, d)] = model.NewIntVar(0, len(hubs_list)-1, f'schedule_{e}_{d}')

# 修正“每位司机每周休息1天”的约束
off_idx = hub_to_idx['OFF']
for e in drivers_list:
    model.Add(sum(
        model.IsEqualCstVar(schedule[(e, d)], off_idx) for d in days
    ) == 1)

# 修正“司机仅能在关联枢纽工作”的约束
for e in drivers_list:
    allowed_idxs = [hub_to_idx[r] for r in driver_hubs_list_relationships[e]]
    for d in days:
        model.AddAllowedAssignments([schedule[(e, d)]], [allowed_idxs])

# 修正枢纽需求统计约束
for d in days:
    for r in hubs_list:
        if r != 'OFF':
            r_idx = hub_to_idx[r]
            hub_demand = hubs_list_and_demand.loc[hubs_list_and_demand['hub'] == r, 'drivers_needed']
            drivers_needed_at_hub = int(hub_demand.values[0]) if len(hub_demand) > 0 else 0
            # 统计安排到该枢纽的司机数量
            assigned = sum(
                model.IsEqualCstVar(schedule[(e, d)], r_idx) for e in drivers_list
            )
            model.Add(assigned >= drivers_needed_at_hub)

4. 调试与验证步骤 #

• 先注释所有非核心约束（如均匀休息、枢纽绑定），仅保留：
  1. 每位司机每周休息1天
  2. 每位司机每天仅能在一个枢纽/休息
  3. 枢纽需求满足
     确认是否能得到可行解，逐步添加约束排查冲突点。
• 打印average_off_days、remainder、每日总需求等关键数值，验证逻辑合理性。

修正后完整代码示例 #

import copy
from ortools.sat.python import cp_model

def create_schedule(drivers,
                    hubs,
                    hubs_and_demand,
                    driver_hubs_relationships,
                    days):
    drivers_list = copy.deepcopy(drivers)
    hubs_list = copy.deepcopy(hubs)
    hubs_list_and_demand = copy.deepcopy(hubs_and_demand)
    driver_hubs_list_relationships = copy.deepcopy(driver_hubs_relationships)

    model = cp_model.CpModel()

    # 添加休息日枢纽
    hubs_list.append('OFF')
    for e in drivers_list:
        driver_hubs_list_relationships[e].append('OFF')

    # 简化变量：每个司机每天对应一个枢纽/休息的索引
    hub_to_idx = {r: idx for idx, r in enumerate(hubs_list)}
    off_idx = hub_to_idx['OFF']
    schedule = {}
    for e in drivers_list:
        for d in days:
            schedule[(e, d)] = model.NewIntVar(0, len(hubs_list)-1, f'schedule_{e}_{d}')

    # 当日休息人数变量
    off_days = {d: model.NewIntVar(0, len(drivers_list), f'off_{d}') for d in days}
    for d in days:
        model.Add(off_days[d] == sum(
            model.IsEqualCstVar(schedule[(e, d)], off_idx) for e in drivers_list
        ))

    # 修正休息日分布约束：精确匹配总休息人次
    total_drivers = len(drivers_list)
    average_off_days = total_drivers // len(days)
    remainder = total_drivers % len(days)
    for idx, d in enumerate(days):
        if idx < remainder:
            model.Add(off_days[d] == average_off_days + 1)
        else:
            model.Add(off_days[d] == average_off_days)

    # 每位司机每周必须休息1天
    for e in drivers_list:
        model.Add(sum(
            model.IsEqualCstVar(schedule[(e, d)], off_idx) for d in days
        ) == 1)

    # 司机仅能在关联枢纽工作
    for e in drivers_list:
        allowed_idxs = [hub_to_idx[r] for r in driver_hubs_list_relationships[e]]
        for d in days:
            model.AddAllowedAssignments([schedule[(e, d)]], [allowed_idxs])

    # 枢纽需求约束：实际安排人数≥需求
    for d in days:
        total_daily_demand = 0
        for r in hubs_list:
            if r != 'OFF':
                hub_demand = hubs_list_and_demand.loc[hubs_list_and_demand['hub'] == r, 'drivers_needed']
                drivers_needed_at_hub = int(hub_demand.values[0]) if len(hub_demand) > 0 else 0
                total_daily_demand += drivers_needed_at_hub
                r_idx = hub_to_idx[r]
                assigned = sum(
                    model.IsEqualCstVar(schedule[(e, d)], r_idx) for e in drivers_list
                )
                model.Add(assigned >= drivers_needed_at_hub)
        # 验证当日可上班人数≥总需求
        model.Add((total_drivers - off_days[d]) >= total_daily_demand)

    # 求解
    solver = cp_model.CpSolver()
    solver.parameters.max_time_in_seconds = 500.0
    solver.parameters.log_search_progress = True
    status = solver.Solve(model)
    print(f"status code {status}")
    
    if status in [cp_model.OPTIMAL, cp_model.FEASIBLE]:
        solution = {}
        idx_to_hub = {v: k for k, v in hub_to_idx.items()}
        for e in drivers_list:
            solution[e] = {}
            for d in days:
                hub_idx = solver.Value(schedule[(e, d)])
                hub_name = idx_to_hub[hub_idx]
                solution[e][d] = hub_name
                print(f"{e} works at {hub_name} on {d}")
        return solution
    else:
        return None

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