基于Python的带约束团队-分区分配优化问题求解咨询

一、ORTools 缺失约束实现 #

步骤1：生成分区前缀分组 #

先将所有分区按编号前缀分组，代码如下：

from collections import defaultdict

# 按分区名称前缀分组，存储对应分区编号
prefix_to_sectors = defaultdict(list)
for sector_idx, sector_name in enumerate(data['sector_names']):
    # 提取数字前缀，如"1A"的前缀为"1"，如果前缀是多位数可以改用正则匹配
    prefix = sector_name[0]
    prefix_to_sectors[prefix].append(sector_idx)
prefix_list = list(prefix_to_sectors.keys())

步骤2：定义辅助变量 #

新增0-1变量z[j,p]，表示团队j是否使用前缀p下的分区：

z = {}
for j in data['teams']:
    for p in prefix_list:
        z[(j, p)] = solver.IntVar(0, 1, f'z_{j}_{p}')

步骤3：添加前缀约束 #

# 约束1：如果团队j使用了前缀p下的任意分区，z[j,p]必须置为1
for j in data['teams']:
    for p in prefix_list:
        allocated_sector_cnt = sum(x[(i, j)] for i in prefix_to_sectors[p])
        solver.Add(allocated_sector_cnt <= z[(j, p)] * len(prefix_to_sectors[p]))

# 约束2：每个团队最多只能使用一个前缀的分区
for j in data['teams']:
    solver.Add(sum(z[(j, p)] for p in prefix_list) <= 1)

步骤4：修正目标函数 #

你当前的目标函数是最大化已分配的团队数量，和你要求的「最大化已分配团队总人数」不符，修正如下：

solver.Maximize(solver.Sum([y[j] * data['team_members'][j] for j in data['teams']]))

二、其他方案说明 #

你当前的场景数据量极小（仅6个分区、8个团队），ORTools的整数规划方案已经是最简单的实现，不需要额外更换算法。如果后续数据量扩大到数百级，可以考虑将问题转化为分组背包问题求解：

• 把每个前缀的所有分区组合视为一个分组，每个分组下的可选物品为「选某团队，消耗对应容量，收益为团队人数」
• 约束为同一分组下选的团队总容量不超过该前缀总容量，且每个团队最多选一次

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