基于OR-Tools CP-SAT求解器实现赛事无重复对阵约束的方法问询

问题背景 #

我正在组织一场200余支队伍的赛事，队伍将被划分为40余个小组（每组6支，按年龄和实力划分），进行4轮比赛，目标是最小化所有队伍的总行驶距离。

已采用布尔变量实现以下逻辑：

• 队伍分配至允许的小组
• 队伍全程固定在同一小组
• 每轮与组内另一队伍对阵

但目前存在**任意两支队伍重复对阵（A vs B和B vs A视为同一对阵）**的问题，示例输出如下：

In Group 1 Round 1 (Pos 0-1) Team 6 vs. 3
In Group 1 Round 1 (Pos 2-3) Team 2 vs. 8
In Group 1 Round 1 (Pos 4-5) Team 5 vs. 1

In Group 1 Round 2 (Pos 0-1) Team 6 vs. 3
In Group 1 Round 2 (Pos 2-3) Team 2 vs. 8
In Group 1 Round 2 (Pos 4-5) Team 5 vs. 1

需要添加约束确保同一对阵仅出现一次。

解决方案 #

核心思路是跟踪每对队伍的对阵次数，限制其总次数不超过1。具体实现步骤：

1. 定义辅助变量：创建布尔变量pair_played[r, g, t1, t2]，仅当t1 < t2时定义，代表第r轮第g组中t1与t2是否对阵。
2. 关联对阵变量与位置分配：当某一轮某组的位置s（偶数位）是t1、位置s+1是t2，或者位置s是t2、位置s+1是t1时，对应的pair_played[r, g, t1, t2]必须为1。
3. 限制对阵次数：对每一对t1 < t2的队伍，约束所有轮次和组中他们的对阵总次数≤1。

修改后的完整代码 #

from ortools.sat.python import cp_model

def main():
    # 分组允许列表（布尔版）
    GroupTypeListBool = [
        [True,True,True,False,True,True,True,True,False,False,False,False,False,False,False,False,False,False],
        [False,False,False,False,False,True,True,True,True,True,True,True,True,False,False,False,False,False],
        [False,False,False,True,False,False,False,False,False,False,True,True,True,True,True,True,True,True]
    ]
    
    num_teams = 18  # 队伍总数
    Groups = 3      # 小组数量
    GroupSize = 6   # 每组队伍数
    Rounds = 4      # 轮次数量
      
    # 初始化模型
    model = cp_model.CpModel()
  
    # 定义核心变量：Teams[r,g,s,t] 表示第r轮第g组第s位置是否是队伍t
    Teams = {}
    for r in range(Rounds):
        for g in range(Groups):
            for s in range(GroupSize):    
                for t in range(num_teams):   
                    Teams[r,g,s,t] = model.NewBoolVar(f'x[{r},{g},{s},{t}]')
 
    # 定义辅助变量：pair_played[r,g,t1,t2] 表示第r轮第g组中t1与t2是否对阵（t1 < t2）
    pair_played = {}
    for r in range(Rounds):
        for g in range(Groups):
            for t1 in range(num_teams):
                for t2 in range(t1 + 1, num_teams):
                    pair_played[r, g, t1, t2] = model.NewBoolVar(f'pair_{r}_{g}_{t1}_{t2}')
 
    # 约束1：每个位置仅分配一支队伍
    for r in range(Rounds):
        for g in range(Groups):
            for s in range(GroupSize):    
                model.AddExactlyOne(Teams[r,g,s,t] for t in range(num_teams))
                
    # 约束2：队伍只能分配到允许的小组
    for r in range(Rounds):
        for g in range(Groups):
            for s in range(GroupSize):    
                for t in range(num_teams):  
                    if not GroupTypeListBool[g][t]:  
                        model.Add(Teams[r,g,s,t] == 0)     
    
    # 约束3：队伍全程固定在同一小组
    for r in range(1, Rounds):
        for g in range(Groups):
            for s in range(GroupSize):    
                for t in range(num_teams):
                    model.Add(Teams[r,g,s,t] == 1).OnlyEnforceIf(Teams[0,g,s,t])          
                    model.Add(Teams[r,g,s,t] == 0).OnlyEnforceIf(Teams[0,g,s,t].Not())

    # 约束4：每支队伍在所有轮次中都参赛
    for t in range(num_teams):
        model.Add(sum(Teams[r,g,s,t] for g in range(Groups) for s in range(GroupSize) for r in range(Rounds)) == Rounds)            
    
    # 约束5：关联位置分配与对阵变量
    for r in range(Rounds):
        for g in range(Groups):
            # 每组的对阵是0-1、2-3、4-5位置配对
            for s in range(0, GroupSize, 2):
                s1 = s
                s2 = s + 1
                for t1 in range(num_teams):
                    for t2 in range(t1 + 1, num_teams):
                        # 当s1是t1且s2是t2，或者s1是t2且s2是t1时，pair_played为1
                        model.AddBoolOr([
                            Teams[r,g,s1,t1].Not(), Teams[r,g,s2,t2].Not(), pair_played[r,g,t1,t2]
                        ])
                        model.AddBoolOr([
                            Teams[r,g,s1,t2].Not(), Teams[r,g,s2,t1].Not(), pair_played[r,g,t1,t2]
                        ])
                        # 当pair_played为1时，必须是s1和s2为t1/t2配对
                        model.AddBoolOr([
                            pair_played[r,g,t1,t2].Not(), Teams[r,g,s1,t1], Teams[r,g,s2,t2]
                        ])
                        model.AddBoolOr([
                            pair_played[r,g,t1,t2].Not(), Teams[r,g,s1,t2], Teams[r,g,s2,t1]
                        ])
    
    # 约束6：每对队伍最多对阵一次
    for t1 in range(num_teams):
        for t2 in range(t1 + 1, num_teams):
            total_plays = sum(pair_played[r,g,t1,t2] for r in range(Rounds) for g in range(Groups))
            model.Add(total_plays <= 1)
          
    # 求解
    solver = cp_model.CpSolver()
    status = solver.Solve(model)
    
    # 输出结果
    if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
        print(f'总行驶距离 = {solver.ObjectiveValue()}')
        for g in range(Groups):
            for r in range(Rounds):
                print()        
                for s in range(GroupSize):    
                    for t in range(num_teams): 
                        if solver.BooleanValue(Teams[r,g,s,t]):
                            if (s % 2) == 0:
                                print(f'In Group {g+1} Round {r+1} (Pos {s}-{s+1}) Team {t+1} vs. ', end="")
                            else:
                                print(f'{t+1}')
                                
    else:
        print('未找到可行解.')
                       
if __name__ == '__main__':
    main()

说明 #

• 修正了原代码中变量定义的引号闭合错误
• 添加的pair_played变量避免了重复计数（仅t1 < t2）
• 约束5确保了位置配对与对阵变量的双向关联
• 约束6严格限制每对队伍最多对阵一次

内容的提问来源于stack exchange，提问作者Carsten Nørgård