OR-TOOLS医生手术排班优化空解问题排查咨询

我正在解决以最小化医生数量为目标的医生-手术-手术室分配优化问题，已知各手术的起止时间、手术总数及手术室数量。使用OR-TOOLS构建模型并添加多种约束后，得到空解，需要定位问题并确认约束定义是否存在错误。

一、空解定位方法 #

• 逐步移除约束排查：每次移除一个约束重新运行求解，直到找到导致无解的约束，这是最快定位冲突的方式。
• 启用OR-Tools诊断输出：添加以下代码获取求解状态和不可行性信息：

  solver = cp_model.CpSolver()
  solver.parameters.log_search_progress = True
  status = solver.Solve(model)
  print(f"求解状态: {solver.StatusName(status)}")
  if status == cp_model.INFEASIBLE:
      print("模型不可行，导出不可行约束文件：")
      solver.ExportInfeasibleModelToFile("infeasible_model.txt")
  

• 校验变量合理性：确认医生数量、手术室数量等参数是否满足最低需求（比如早高峰并行手术数不能超过医生数与手术室数的合理组合）。

二、现有代码的约束错误分析及修正 #

1. 时间差计算逻辑错误 #

原getTimediffrence函数颠倒了起止时间顺序，导致结果为负数，完全破坏后续时间相关约束：

# 修正后的时间差计算函数
def getTimediffrence(start, end):
    startTime = datetime.datetime.strptime(start, '%m/%d/%Y %H:%M')
    endTime = datetime.datetime.strptime(end, '%m/%d/%Y %H:%M')
    timeDiff = endTime - startTime  # 正确顺序：结束时间减开始时间
    return int(timeDiff.total_seconds() / 60)

2. 约束2：医生时间冲突校验错误 #

原约束仅限制同一医生在同一手术室最多参与1台手术，未校验时间重叠的手术。正确的时间冲突约束应比较手术时间：

# 替换原约束2：医生不能同时参与时间重叠的手术
for i in range(num_doctors):
    for j1 in range(num_analyses):
        start1, end1 = analysis_dict[j1]
        end1_dt = datetime.datetime.strptime(end1, '%m/%d/%Y %H:%M')
        start1_dt = datetime.datetime.strptime(start1, '%m/%d/%Y %H:%M')
        for j2 in range(j1 + 1, num_analyses):
            start2, end2 = analysis_dict[j2]
            start2_dt = datetime.datetime.strptime(start2, '%m/%d/%Y %H:%M')
            end2_dt = datetime.datetime.strptime(end2, '%m/%d/%Y %H:%M')
            # 判断两台手术时间是否重叠
            if start1_dt < end2_dt and start2_dt < end1_dt:
                # 同一医生不能同时参与这两台手术（无论手术室）
                for k1 in range(num_rooms):
                    for k2 in range(num_rooms):
                        model.Add(x[(i, j1, k1)] + x[(i, j2, k2)] <= 1)

3. 约束3：逻辑无效可移除 #

原约束3的表达式无法实现“医生必须全程参与手术”的意图，该逻辑已包含在时间冲突约束中，可直接删除此约束。

4. 约束5：换手术室逻辑混乱 #

原约束5的表达式不符合“间隔≥15分钟可换手术室”的需求，反而会引入矛盾。正确逻辑应为：间隔不足15分钟时医生必须留在同一手术室：

# 替换原约束5：手术间隔不足15分钟时，医生不能换手术室
for i in range(num_doctors):
    for j1 in range(num_analyses):
        end1_dt = datetime.datetime.strptime(analysis_dict[j1][1], '%m/%d/%Y %H:%M')
        for j2 in range(num_analyses):
            if j1 == j2:
                continue
            start2_dt = datetime.datetime.strptime(analysis_dict[j2][0], '%m/%d/%Y %H:%M')
            gap = int((start2_dt - end1_dt).total_seconds() / 60)
            # 仅针对j1结束后j2开始、且间隔不足15分钟的情况
            if 0 <= gap < 15:
                for k1 in range(num_rooms):
                    for k2 in range(num_rooms):
                        if k1 != k2:
                            model.Add(x[(i, j1, k1)] + x[(i, j2, k2)] <= 1)

5. 目标函数错误 #

原目标函数计算的是所有赋值变量的总数（等于手术数），无法实现最小化医生数量的目标。正确实现应为：

# 创建医生是否被使用的变量
doctor_used = [model.NewBoolVar(f'doctor_used[{i}]') for i in range(num_doctors)]
for i in range(num_doctors):
    # 关联医生使用状态与手术分配
    model.Add(sum(x[(i,j,k)] for j in range(num_analyses) for k in range(num_rooms)) >= 1).OnlyEnforceIf(doctor_used[i])
    model.Add(sum(x[(i,j,k)] for j in range(num_analyses) for k in range(num_rooms)) == 0).OnlyEnforceIf(doctor_used[i].Not())

# 目标：最小化被使用的医生数量
model.Minimize(sum(doctor_used))

三、完整修正后的核心代码片段 #

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

def getTimediffrence(start, end):
    startTime = datetime.datetime.strptime(start, '%m/%d/%Y %H:%M')
    endTime = datetime.datetime.strptime(end, '%m/%d/%Y %H:%M')
    timeDiff = endTime - startTime
    return int(timeDiff.total_seconds() / 60)

surgery_times = {0: ('4/25/2023 7:00', '4/25/2023 7:15'), 1: ('4/25/2023 7:00', '4/25/2023 7:30'), 2: ('4/25/2023 7:00', '4/25/2023 7:30'), 3: ('4/25/2023 7:00', '4/25/2023 7:30'), 4: ('4/25/2023 7:00', '4/25/2023 7:45'), 5: ('4/25/2023 7:00', '4/25/2023 8:00'), 6: ('4/25/2023 7:00', '4/25/2023 8:45'), 7: ('4/25/2023 7:00', '4/25/2023 9:45'), 8: ('4/25/2023 7:15', '4/25/2023 7:30'), 9: ('4/25/2023 7:15', '4/25/2023 7:30'), 10: ('4/25/2023 8:00', '4/25/2023 8:15'), 11: ('4/25/2023 8:00', '4/25/2023 8:45'), 12: ('4/25/2023 8:00', '4/25/2023 9:00'), 13: ('4/25/2023 9:15', '4/25/2023 10:30'), 14: ('4/25/2023 9:30', '4/25/2023 10:30'), 15: ('4/25/2023 9:30', '4/25/2023 10:45'), 16: ('4/25/2023 9:45', '4/25/2023 10:30')}

def solve_surgery_assignment(analysis_dict):
    model = cp_model.CpModel()
    
    num_doctors = len(analysis_dict)
    num_rooms = 5
    num_analyses = len(analysis_dict)

    # 决策变量：x[i,j,k] = 1表示医生i在手术室k负责手术j
    x = {}
    for i in range(num_doctors):
        for j in range(num_analyses):
            for k in range(num_rooms):
                x[(i, j, k)] = model.NewBoolVar(f'x[{i},{j},{k}]')

    # 约束1：每个手术必须分配给一名医生和一个手术室
    for j in range(num_analyses):
        model.Add(sum(x[(i, j, k)] for i in range(num_doctors) for k in range(num_rooms)) == 1)

    # 约束2：医生不能同时参与时间重叠的手术
    for i in range(num_doctors):
        for j1 in range(num_analyses):
            start1, end1 = analysis_dict[j1]
            end1_dt = datetime.datetime.strptime(end1, '%m/%d/%Y %H:%M')
            start1_dt = datetime.datetime.strptime(start1, '%m/%d/%Y %H:%M')
            for j2 in range(j1 + 1, num_analyses):
                start2, end2 = analysis_dict[j2]
                start2_dt = datetime.datetime.strptime(start2, '%m/%d/%Y %H:%M')
                end2_dt = datetime.datetime.strptime(end2, '%m/%d/%Y %H:%M')
                if start1_dt < end2_dt and start2_dt < end1_dt:
                    for k1 in range(num_rooms):
                        for k2 in range(num_rooms):
                            model.Add(x[(i, j1, k1)] + x[(i, j2, k2)] <= 1)

    # 约束4：每个手术室同一时间只能进行一台手术
    for j in range(num_analyses):
        for k in range(num_rooms):
            model.Add(sum(x[(i, j, k)] for i in range(num_doctors)) <= 1)

    # 约束5：手术间隔不足15分钟时，医生不能换手术室
    for i in range(num_doctors):
        for j1 in range(num_analyses):
            end1_dt = datetime.datetime.strptime(analysis_dict[j1][1], '%m/%d/%Y %H:%M')
            for j2 in range(num_analyses):
                if j1 == j2:
                    continue
                start2_dt = datetime.datetime.strptime(analysis_dict[j2][0], '%m/%d/%Y %H:%M')
                gap = int((start2_dt - end1_dt).total_seconds() / 60)
                if 0 <= gap < 15:
                    for k1 in range(num_rooms):
                        for k2 in range(num_rooms):
                            if k1 != k2:
                                model.Add(x[(i, j1, k1)] + x[(i, j2, k2)] <= 1)

    # 目标函数：最小化使用的医生数量
    doctor_used = [model.NewBoolVar(f'doctor_used[{i}]') for i in range(num_doctors)]
    for i in range(num_doctors):
        model.Add(sum(x[(i,j,k)] for j in range(num_analyses) for k in range(num_rooms)) >= 1).OnlyEnforceIf(doctor_used[i])
        model.Add(sum(x[(i,j,k)] for j in range(num_analyses) for k in range(num_rooms)) == 0).OnlyEnforceIf(doctor_used[i].Not())
    model.Minimize(sum(doctor_used))

    # 求解模型
    solver = cp_model.CpSolver()
    solver.parameters.log_search_progress = True
    status = solver.Solve(model)

    solution = {}
    if status == cp_model.OPTIMAL:
        print(f"最优医生数量: {int(solver.ObjectiveValue())}")
        for i in range(num_doctors):
            for j in range(num_analyses):
                for k in range(num_rooms):
                    if solver.Value(x[(i, j, k)]) == 1:
                        solution[(j, k)] = i
                        print(f"手术{j+1} 在手术室{k+1} 由医生{i}负责")

    # 生成结果文件
    doctor_list = []
    start_time_list = []
    end_time_list = []
    room_list = []
    for (surgery_idx, room_idx), doctor in solution.items():
        start, end = analysis_dict[surgery_idx]
        doctor_list.append(doctor)
        start_time_list.append(start)
        end_time_list.append(end)
        room_list.append(room_idx + 1)

    df = pd.DataFrame({
        'start_time': start_time_list,
        'end_time': end_time_list,
        'anesthetist_id': doctor_list,
        'room_id': room_list
    })
    df.to_csv('scheduled.csv', index=False)

solve_surgery_assignment(surgery_times)

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