Ortools调度模型无可行解求助：司机数满足需求却无解

我基于Ortools CP-SAT编写了司机调度函数，参数包含司机列表、枢纽列表、司机可工作的枢纽关系列表，以及需转换为含hub和drivers_needed列的DataFrame的枢纽需求数据。目前司机总数满足含休息日在内的需求，但模型始终输出无可行解，恳请协助排查问题。

相关数据 #

• 司机列表：

  ['Driver_0', 'Driver_1', 'Driver_2', 'Driver_3', 'Driver_4', 'Driver_5', 'Driver_6', 'Driver_7', 'Driver_8', 'Driver_9', 'Driver_10', 'Driver_11', 'Driver_12', 'Driver_13', 'Driver_14', 'Driver_15', 'Driver_16', 'Driver_17', 'Driver_18', 'Driver_19', 'Driver_20', 'Driver_21', 'Driver_22', 'Driver_23', 'Driver_24', 'Driver_25', 'Driver_26', 'Driver_27', 'Driver_28', 'Driver_29', 'Driver_30', 'Driver_31', 'Driver_32', 'Driver_33', 'Driver_34', 'Driver_35', 'Driver_36', 'Driver_37', 'Driver_38', 'Driver_39', 'Driver_40', 'Driver_41', 'Driver_42', 'Driver_43', 'Driver_44', 'Driver_45', 'Driver_46', 'Driver_47', 'Driver_48', 'Driver_49', 'Driver_50', 'Driver_51', 'Driver_52', 'Driver_53', 'Driver_54', 'Driver_55', 'Driver_56', 'Driver_57', 'Driver_58', 'Driver_59', 'Driver_60', 'Driver_61', 'Driver_62', 'Driver_63', 'Driver_64', 'Driver_65', 'Driver_66', 'Driver_67', 'Driver_68', 'Driver_69', 'Driver_70', 'Driver_71', 'Driver_72', 'Driver_73', 'Driver_74', 'Driver_75', 'Driver_76', 'Driver_77', 'Driver_78', 'Driver_79', 'Driver_80', 'Driver_81', 'Driver_82', 'Driver_83', 'Driver_84', 'Driver_85', 'Driver_86', 'Driver_87', 'Driver_88', 'Driver_89', 'Driver_90', 'Driver_91', 'Driver_92', 'Driver_93', 'Driver_94', 'Driver_95', 'Driver_96', 'Driver_97', 'Driver_98', 'Driver_99']
  

• 枢纽列表：

  ['Hub_A', 'Hub_B', 'Hub_C', 'Hub_D', 'Hub_E', 'Hub_F', 'Hub_G', 'Hub_H', 'Hub_I', 'Hub_J']
  

• 司机-枢纽可工作关系：以字典形式存储，每个司机对应其可工作的枢纽列表（示例：Driver_0对应['Hub_A', 'Hub_B']）
• 枢纽需求数据：转换为DataFrame后，每个枢纽每日需要10名司机，覆盖一周7天。

调度函数代码 #

from ortools.sat.python import cp_model
from datetime import datetime, timedelta
import time
import copy

days = ['Monday', 'Tuesday', 'Wednesday', 'Thursday', 'Friday', 'Saturday', 'Sunday']

def create_schedule(drivers,
                    hubs,
                    hubs_and_demand,
                    driver_hubs_relationships):
    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')

    # 创建变量：总规模为 len(drivers)*(1+len(hubs))*len(days)
    schedule = {}
    for e in drivers_list:
        for d in days:
            for r in hubs_list:
                schedule[(e, d, r)] = model.NewBoolVar(f'schedule_{e}_{d}_{r}')

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

    # 每位司机每天只能在一个枢纽工作（或休息）
    for e in drivers_list:
        for d in days:
            model.Add(sum(schedule[(e, d, r)] for r in hubs_list) == 1)

    # 限制司机只能分配到允许的枢纽
    for e in drivers_list:
        for r in hubs_list:
            if r not in driver_hubs_list_relationships[e]:
                for d in days:
                    model.Add(schedule[(e, d, r)] == 0)

    # 创建枢纽每日所需司机数的变量
    drivers_needed = {}
    for d in days:
        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[(d, r)] = model.NewIntVar(1,
                                                         int(hub_demand.values[0]),
                                                         f'drivers_needed_{d}_{r}')

    # 每个枢纽每日必须满足所需司机数量
    for d in days:
        for r in hubs_list:
            if r != 'OFF':
                model.Add(sum(schedule[(e, d, r)] for e in drivers_list) == drivers_needed[(d, r)])

    # 求解并输出调度结果
    solver = cp_model.CpSolver()
    solver.parameters.max_time_in_seconds = 2500.0
    solver.parameters.log_search_progress = True
    status = solver.Solve(model)
    print(f"状态码 {status}")

    # 输出求解状态
    if status == cp_model.OPTIMAL:
        print('找到最优解。')
    elif status == cp_model.FEASIBLE:
        print('找到可行解，但不一定是最优解。')
    elif status == cp_model.INFEASIBLE:
        print('未找到可行解。')
    elif status == cp_model.MODEL_INVALID:
        print('给定模型无效。')
    elif status == cp_model.UNKNOWN:
        print(
            '模型状态未知，可能因为达到时间限制或问题未解决。')

    if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
        solution = {}
        for e in drivers_list:
            solution[e] = {}
            for d in days:
                for r in hubs_list:
                    if solver.Value(schedule[(e, d, r)]) == 1:
                        print(f"{e} 在 {d} 于 {r} 工作")
                        solution[e][d] = r

        return solution
    else:
        return None

排查结果与修复建议 #

1. 总需求与可用工作天数不匹配（根本原因）
   计算总需求：10个枢纽 × 7天 × 每日10名司机 = 700个司机工作日。
   计算司机总可用工作天数：100名司机 × 每周工作6天 = 600个司机工作日。
   总需求远超司机可提供的工作天数，直接导致模型无可行解。需调整枢纽每日需求，或增加司机数量。

2. 需求变量下界设置错误
   代码中drivers_needed变量的下界设为1，若后续出现枢纽需求为0的场景会触发约束冲突，建议改为0适配所有情况：

   drivers_needed[(d, r)] = model.NewIntVar(0,
                                            int(hub_demand.values[0]),
                                            f'drivers_needed_{d}_{r}')
   

3. 司机-枢纽权限验证
   若调整总需求后仍无解，需检查单个枢纽的每日需求是否不超过能分配到该枢纽的司机总数。比如某枢纽每日需求10名司机，但只有8名司机有该枢纽的工作权限，也会导致局部约束冲突。

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