基于Google OR-Tools CP-SAT的循环赛赛程编排优化约束咨询

看起来你已经搭好了CP-SAT模型的基础框架，核心的比赛场次、单天单赛、全对手覆盖这些约束都没问题，但确实需要补充赛程分布类的约束来解决连续对阵、主客场扎堆的问题。下面给你几个关键的约束方向，以及对应的实现思路和代码示例：

一、避免同一对手连续对阵 #

要防止X和Y连续两天交手（不管主客场），可以针对每一对对手(X,Y)和连续的日期D、D+1，添加约束：X和Y在D日的所有可能比赛（X主Y客、Y主X客），加上D+1日的所有可能比赛，最多只能有1场被选中。

实现代码 #

def avoid_consecutive_opponents(model, matches, dates):
    # 先拿到所有唯一的对手对（去重，比如(h,o)和(o,h)算同一对）
    team_pairs = set()
    for (h, o, d) in matches:
        if h < o:  # 用排序逻辑避免重复处理同一对手对
            team_pairs.add((h, o))
    # 遍历每对对手和连续日期窗口
    for (h, o) in team_pairs:
        for i in range(len(dates)-1):
            d1 = dates[i]
            d2 = dates[i+1]
            # 两天内该对手对的所有可能对阵组合
            possible_matches = [
                matches[(h, o, d1)],
                matches[(o, h, d1)],
                matches[(h, o, d2)],
                matches[(o, h, d2)]
            ]
            model.AddAtMostOne(possible_matches)

二、限制连续主/客场场次 #

针对“先打完所有主场再打客场”的问题，你可以通过约束单支球队连续主/客场的场次不超过N场（比如N=2，可根据需求调整）来解决。

实现代码 #

def limit_consecutive_home_away(model, matches, dates, max_consecutive=2):
    # 提取所有参赛球队
    teams = set()
    for (h, o, d) in matches:
        teams.add(h)
        teams.add(o)
    # 遍历每支球队和连续日期窗口
    for t in teams:
        window_size = max_consecutive + 1
        for i in range(len(dates) - window_size + 1):
            window_dates = dates[i:i+window_size]
            # 收集窗口内该球队的所有主/客场比赛变量
            home_matches = []
            away_matches = []
            for d in window_dates:
                # 主场比赛：t作为主队的所有可能对阵
                for o in teams:
                    if o != t and (t, o, d) in matches:
                        home_matches.append(matches[(t, o, d)])
                # 客场比赛：t作为客队的所有可能对阵
                for h in teams:
                    if h != t and (h, t, d) in matches:
                        away_matches.append(matches[(h, t, d)])
            # 约束：窗口内连续主/客场场次不超过max_consecutive
            model.Add(sum(home_matches) <= max_consecutive)
            model.Add(sum(away_matches) <= max_consecutive)

三、可选：软约束优化（防止硬约束导致无解） #

如果上面的硬约束太严格（比如小分组场景下可能出现无解），可以把部分约束改成软约束（惩罚项），让求解器尽量满足分布要求，而非强制要求。比如：

• 每出现一次连续3场主/客场，加1分惩罚
• 每出现一次连续对阵同一对手，加1分惩罚
  然后让求解器最小化总惩罚值。

实现代码片段 #

def add_soft_constraints(model, matches, dates):
    # 初始化惩罚变量
    total_penalty = model.NewIntVar(0, 1000, 'total_penalty')
    penalty_terms = []
    
    team_pairs = set()
    for (h, o, d) in matches:
        if h < o:
            team_pairs.add((h, o))
    teams = {h for (h, o, d) in matches} | {o for (h, o, d) in matches}

    # 1. 连续对阵同一对手的惩罚
    for (h, o) in team_pairs:
        for i in range(len(dates)-1):
            d1, d2 = dates[i], dates[i+1]
            conflict = model.NewBoolVar(f'conflict_{h}_{o}_{d1}')
            # 两天内存在对阵该对手的比赛则触发惩罚
            model.AddBoolAnd([
                matches[(h,o,d1)] | matches[(o,h,d1)],
                matches[(h,o,d2)] | matches[(o,h,d2)]
            ]).OnlyEnforceIf(conflict)
            penalty_terms.append(conflict)

    # 2. 连续3场主/客场的惩罚
    for t in teams:
        for i in range(len(dates)-2):
            d1, d2, d3 = dates[i], dates[i+1], dates[i+2]
            three_home = model.NewBoolVar(f'three_home_{t}_{d1}')
            # 三天均为主场则触发惩罚
            home_vars = []
            for d in [d1, d2, d3]:
                for o in teams:
                    if o != t and (t, o, d) in matches:
                        home_vars.append(matches[(t, o, d)])
            model.Add(sum(home_vars) == 3).OnlyEnforceIf(three_home)
            penalty_terms.append(three_home)

    # 绑定总惩罚并设置最小化目标
    model.Add(total_penalty == sum(penalty_terms))
    model.Minimize(total_penalty)
    return total_penalty

四、集成到现有代码 #

把这些新增约束加到你的现有流程中即可，比如在基础约束之后调用：

# 现有基础约束
home_opposition_constraint(model, matches)
teams_on_a_day_constraint(model, matches)
# 新增分布约束
avoid_consecutive_opponents(model, matches, dates)
limit_consecutive_home_away(model, matches, dates, max_consecutive=2)
# 如果用软约束，替换上面两行或额外添加
# add_soft_constraints(model, matches, dates)

其他小技巧 #

1. 先搭传统赛程框架：循环赛有成熟的编排算法（如贝格尔法），可以先用算法生成主客场对阵的大致框架，再用CP-SAT填充日期和场地，能大幅减少求解器的搜索空间。
2. 调整求解器参数：比如设置solver.parameters.search_branching = cp_model.PORTFOLIO_SEARCH，或增加求解时间限制，让求解器有更多时间找到更优解。

备注：内容来源于stack exchange，提问作者wantro