如何在指定约束下最小化pandas DataFrame总值，实现人员到客户的最优分配

你遇到的是典型的带多需求约束的二分图最小权匹配问题，可以直接用谷歌开源的运筹优化工具ortools实现，无需自研底层算法，步骤如下：

核心建模逻辑 #

• 二分图左侧为所有员工，每个员工最多分配1次，对应流量流出上限为1
• 二分图右侧为所有客户，每个客户按需求分配2/3名员工，对应流量流入下限等于需求值
• 员工到客户的边权为对应驾车时长，求解目标为所有选中边的总权值最小

可运行代码实现 #

第一步：安装依赖 #

pip install ortools pandas

第二步：完整代码示例 #

import pandas as pd
from ortools.linear_solver import pywraplp

# ---------------------- 1. 准备数据（替换为你自己的未透视DataFrame即可） ----------------------
# 未透视df默认列名：customer（客户）、employee（员工）、drive_time（驾车时长）
# 下方为模拟示例数据，可直接替换为你的真实数据
raw_data = [
    {"customer": "客户A", "employee": f"员工{i}", "drive_time": 100*i + 50} for i in range(10)
] + [
    {"customer": "客户B", "employee": f"员工{i}", "drive_time": 80*i + 120} for i in range(10)
] + [
    {"customer": "客户C", "employee": f"员工{i}", "drive_time": 120*i + 30} for i in range(10)
]
df = pd.DataFrame(raw_data)
# 按实际需求定义每个客户需要的员工数
customer_demand = {
    "客户A": 2,
    "客户B": 2,
    "客户C": 3
}
# 校验员工总数是否满足总需求
total_demand = sum(customer_demand.values())
employee_list = df["employee"].unique()
assert len(employee_list) >= total_demand, "员工总数不足，无法满足客户需求"

# ---------------------- 2. 初始化求解器 ----------------------
solver = pywraplp.Solver.CreateSolver("SCIP")

# ---------------------- 3. 定义决策变量：x[i][j] = 1 表示员工i分配给客户j ----------------------
x = {}
for idx, row in df.iterrows():
    emp = row["employee"]
    cust = row["customer"]
    x[(emp, cust)] = solver.IntVar(0, 1, f"x_{emp}_{cust}")

# ---------------------- 4. 添加约束 ----------------------
# 约束1：每个员工最多分配给1个客户
for emp in employee_list:
    solver.Add(
        sum(x[(emp, cust)] for cust in df[df["employee"]==emp]["customer"].unique()) <= 1
    )
# 约束2：每个客户分配的员工数等于需求值
for cust, demand in customer_demand.items():
    solver.Add(
        sum(x[(emp, cust)] for emp in df[df["customer"]==cust]["employee"].unique()) == demand
    )

# ---------------------- 5. 定义目标函数：总驾车时长最小 ----------------------
solver.Minimize(
    sum(row["drive_time"] * x[(row["employee"], row["customer"])] for idx, row in df.iterrows())
)

# ---------------------- 6. 求解并输出结果 ----------------------
status = solver.Solve()
if status == pywraplp.Solver.OPTIMAL:
    print(f"最优总驾车时长：{solver.Objective().Value()} 秒")
    print("分配方案：")
    res = []
    for (emp, cust), var in x.items():
        if var.solution_value() == 1:
            res.append({
                "员工": emp, 
                "客户": cust, 
                "驾车时长": df[(df["employee"]==emp)&(df["customer"]==cust)]["drive_time"].iloc[0]
            })
    res_df = pd.DataFrame(res)
    print(res_df)
else:
    print("没有找到可行解，请检查需求和员工数量是否匹配")

补充说明 #

如果你的数据规模在千人级别，上述线性规划方案依然可以快速求解；如果规模更大，可以改用ortools的最小费用流接口，求解效率会更高。

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