匈牙利算法员工重分配函数失效问题排查与修复

我希望用Hungarian算法解决以下组合优化任务：同一公司的不同团队员工分布在不同城市，仅同岗位员工可互换，目标是重分配员工，最大化拥有同城市员工的团队数量。数据包含员工ID、团队ID、岗位、城市四列，需输出重分配后的同结构表格。

示例输入 #

employee_id    team_id  position    city
             1       0.0    Manager     New York
             2       0.0    Manager     San Francisco
             3       1.0    Engineer    Boston
             4       1.0    Engineer    Boston
             5       2.0    Engineer    London
             6       2.0    Engineer    London
             7       2.0    Manager     New York

示例输出 #

employee_id    team_id  position    city
             1       0.0    Manager     New York
             7       0.0    Manager     New York
             3       1.0    Engineer    Boston
             4       1.0    Engineer    Boston
             5       2.0    Engineer    London
             6       2.0    Engineer    London
             2       2.0    Manager     San Francisco

如示例所示，员工7和2互换后，团队0.0的员工均位于纽约。

当前代码 #

import numpy as np
import scipy.optimize as opt

def hungarian(cost_matrix):
    row_ind, col_ind = opt.linear_sum_assignment(cost_matrix)
    return row_ind, col_ind

def redistribute_employees(employee_data, cost_matrix):
    n = len(employee_data)
    row_ind, col_ind = hungarian(cost_matrix)
    new_teams = np.zeros(n)
    for i in range(n):
        new_teams[i] = col_ind[int(employee_data[i, 1])]
    return np.column_stack((employee_data[:, 0], new_teams, employee_data[:, 2], employee_data[:, 3]))

employee_data = np.array([[1, 0, 'Manager', 'New York'],
                          [2, 0, 'Manager', 'San Francisco'],
                          [3, 1, 'Engineer', 'Boston'],
                          [4, 1, 'Engineer', 'Boston'],
                          [5, 2, 'Engineer', 'London'],
                          [6, 2, 'Engineer', 'London'],
                          [7, 2, 'Manager', 'New York']])
city_map = {'New York': 0, 'San Francisco': 1, 'Boston': 2, 'London': 3}
n = len(employee_data)
cost_matrix = np.zeros((n, n))
for i in range(n):
    for j in range(n):
        if employee_data[i, 2] == employee_data[j, 2] and employee_data[i, 3] != employee_data[j, 3]:
            cost_matrix[i, j] = 1

redistributed_employees = redistribute_employees(employee_data, cost_matrix)
print(redistributed_employees)

问题现象 #

代码运行后输出与输入完全一致，无任何变化。当前算法步骤设计为：

1. 创建成本矩阵，若员工所在城市不同则成本为1，相同则为0；
2. 运行Hungarian算法找到员工与团队间的最小成本匹配；
3. 基于匹配结果重分配员工，最大化同城市员工的团队数量；
4. 输出重分配后的员工表格。

现在需要找出代码中的问题并修复。

核心问题点 #

1. 成本矩阵含义错误：当前成本矩阵定义的是员工到员工的映射成本，完全偏离了"员工-团队岗位匹配"的任务场景，且未关联"最大化同团队同岗位员工同城市"的目标。
2. 匹配结果逻辑错误：redistribute_employees函数中，用col_ind[int(employee_data[i,1])]分配新团队，完全误解了linear_sum_assignment的输出——该函数返回的是行与列的最优匹配对，行/列定义错误时结果毫无意义。
3. 任务建模错误：未按岗位拆分任务，也未统计团队的岗位需求和城市的员工供给，导致算法无法针对核心目标进行优化。

修复步骤与代码 #

正确建模思路 #

• 按岗位分组处理：不同岗位员工不可互换，需独立分配。
• 对每个岗位：
  1. 统计各团队对该岗位的员工需求（即原团队中该岗位的人数）。
  2. 统计各城市该岗位的员工供给数量。
  3. 用Hungarian算法匹配团队与最优城市（能最大化满足团队需求的城市）。
  4. 将对应城市的员工分配到匹配的团队岗位，确保同一团队同岗位员工尽可能来自同一城市。

修复后的代码 #

import numpy as np
from scipy.optimize import linear_sum_assignment

def redistribute_by_position(employee_data):
    # 按岗位分组处理
    positions = np.unique(employee_data[:, 2])
    result = []
    
    for pos in positions:
        # 筛选当前岗位的所有员工
        pos_employees = employee_data[employee_data[:, 2] == pos]
        emp_ids = pos_employees[:, 0]
        cities = pos_employees[:, 3]
        original_teams = pos_employees[:, 1].astype(float)
        
        # 统计每个团队需要该岗位的人数（原团队该岗位的人数）
        team_counts = {}
        for team in original_teams:
            team_counts[team] = team_counts.get(team, 0) + 1
        teams = list(team_counts.keys())
        team_demands = np.array([team_counts[t] for t in teams])
        
        # 统计每个城市该岗位的员工数
        city_counts = {}
        for city in cities:
            city_counts[city] = city_counts.get(city, 0) + 1
        cities_list = list(city_counts.keys())
        city_supplies = np.array([city_counts[c] for c in cities_list])
        
        # 构建团队-城市的收益矩阵：收益为该城市能满足团队需求的员工数
        team_city_benefit = np.zeros((len(teams), len(cities_list)))
        for t_idx in range(len(teams)):
            demand = team_demands[t_idx]
            for c_idx in range(len(cities_list)):
                supply = city_supplies[c_idx]
                team_city_benefit[t_idx, c_idx] = min(demand, supply)
        
        # 转换为成本矩阵（linear_sum_assignment求最小成本，用负收益作为成本）
        cost_matrix = -team_city_benefit
        team_ind, city_ind = linear_sum_assignment(cost_matrix)
        
        # 记录每个团队匹配的最优城市
        team_to_city = {teams[t_idx]: cities_list[city_ind[t_idx]] for t_idx in team_ind}
        
        # 为员工分配团队：优先分配到匹配城市的团队岗位
        team_remaining = team_counts.copy()
        emp_new_teams = []
        
        for emp_id, city, orig_team in zip(emp_ids, cities, original_teams):
            # 找符合城市要求且有空缺的团队
            eligible_teams = [t for t in teams if team_to_city[t] == city and team_remaining[t] > 0]
            if eligible_teams:
                chosen_team = eligible_teams[0]
            else:
                # 无匹配城市时，选任意有空缺的团队
                chosen_team = next(t for t in teams if team_remaining[t] > 0)
            emp_new_teams.append(chosen_team)
            team_remaining[chosen_team] -= 1
        
        # 将当前岗位的结果加入总列表
        for emp_id, new_team, pos, city in zip(emp_ids, emp_new_teams, [pos]*len(emp_ids), cities):
            result.append([emp_id, new_team, pos, city])
    
    return np.array(result, dtype=object)

# 测试数据
employee_data = np.array([[1, 0, 'Manager', 'New York'],
                          [2, 0, 'Manager', 'San Francisco'],
                          [3, 1, 'Engineer', 'Boston'],
                          [4, 1, 'Engineer', 'Boston'],
                          [5, 2, 'Engineer', 'London'],
                          [6, 2, 'Engineer', 'London'],
                          [7, 2, 'Manager', 'New York']], dtype=object)

# 执行重分配
redistributed = redistribute_by_position(employee_data)

# 格式化输出结果
print(f"{'employee_id':>15} {'team_id':>10} {'position':>10} {'city':>15}")
for row in redistributed:
    print(f"{row[0]:>15} {row[1]:>10.1f} {row[2]:>10} {row[3]:>15}")

修复说明 #

1. 岗位拆分处理：严格遵循"仅同岗位员工可互换"的规则，每个岗位独立进行分配逻辑。
2. 目标对齐的建模：通过团队-城市的收益矩阵，用Hungarian算法找到能最大化满足团队需求的城市匹配，确保同一团队同岗位员工尽可能来自同一城市。
3. 正确的匹配逻辑：不再误解linear_sum_assignment的输出，而是用它解决团队与城市的最优匹配，再基于此完成员工到团队的分配。
4. 可读性优化：输出结果采用对齐格式，与示例输出风格一致。

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