You need to enable JavaScript to run this app. Node.js环境下类最小费用流的多日人员分组方案实现问题
优惠活动
大模型
产品
解决方案
定价
更多

Node.js环境下类最小费用流的多日人员分组方案实现问题

Node.js 多日人员分组问题解决方案(最小费用流实现)

适配第三方开发库

以下库均完全适配Node.js技术栈,可直接在项目中引入使用:

  • @graph-algorithm/min-cost-flow:轻量型最小费用流算法实现,支持CommonJS/ES Module双规范,性能足以覆盖100人规模的分组运算需求
  • network-js:内置完整网络流模型封装,支持自定义边权、容量约束,无需手动从零搭建网络拓扑结构,可快速映射分组业务规则
  • munkres-js:仅适用于简化的单天二分图匹配场景,多日多约束场景下优先选择最小费用流相关库

具体实现方法

步骤1:业务约束转网络流模型

先将所有规则映射为最小费用流的拓扑参数:

  • 小组容量约束:100人/8组≈12.5人,每组容量可设为12-14人的浮动区间,保证每日各小组人数大致均等
  • 费用规则:用户1级偏好分组费用设为0,2级为1,以此类推,非偏好分组费用设为7(高于最高偏好等级对应的费用,保证算法优先匹配用户偏好)
  • 重复分配约束:用户在任意一天进入某小组后,后续天数的拓扑中直接移除该用户到对应小组的边,从底层避免重复分配

步骤2:迭代生成5天分组方案

按周一到周五的顺序依次生成每日分组,避免跨天冲突:

  1. 初始化用户-小组可用映射表:初始状态所有用户可进入所有小组
  2. 针对当日搭建最小费用流网络拓扑:
    • 源节点→用户节点:每条边容量为1,费用为0
    • 用户节点→可用小组节点:边容量为1,费用对应用户对该小组的偏好等级
    • 小组节点→汇节点:边容量按12-14的浮动区间设置,保证总容量≥100
  3. 运行最小费用流算法,得到当日分配结果
  4. 更新用户-小组可用映射表:将当日已分配的用户-小组组合标记为不可用,后续天数不再纳入候选
  5. 重复上述步骤直到5天的分组全部生成

步骤3:异常兜底逻辑

如果某日出现最小费用流无法达到最大流(部分用户无法分配)的情况,按以下优先级降级处理:

  • 临时放开对应日期的小组容量上限1人,优先保证所有用户都能分配
  • 若仍无法匹配,临时下调非偏好分组的费用权重,重新运算得到可行解

核心代码示例

const { MinCostFlow } = require('@graph-algorithm/min-cost-flow');

/**
 * 生成单日分组结果
 * @param {Array} users 用户列表,每个元素包含id、preference(小组id对应偏好等级,无则为undefined)
 * @param {Map} usedMap 已使用的用户-小组映射,key为`${userId}-${groupId}`
 * @param {Number} groupCount 小组总数
 * @param {Number} totalUser 总人数
 * @returns {Object} 当日分配结果
 */
function generateDailyGroup(users, usedMap, groupCount = 8, totalUser = 100) {
  const baseGroupSize = Math.floor(totalUser / groupCount);
  const mcf = new MinCostFlow();
  // 节点编号定义
  const source = 0;
  const userNodeStart = 1;
  const groupNodeStart = userNodeStart + users.length;
  const sink = groupNodeStart + groupCount;

  // 源点连接所有用户节点
  users.forEach((_, idx) => {
    mcf.addEdge(source, userNodeStart + idx, 1, 0);
  });

  // 用户节点连接可用的小组节点
  users.forEach((user, userIdx) => {
    for (let groupId = 0; groupId < groupCount; groupId++) {
      // 跳过已经去过的小组
      if (usedMap.has(`${user.id}-${groupId}`)) continue;
      const cost = user.preference[groupId] ?? 7;
      mcf.addEdge(userNodeStart + userIdx, groupNodeStart + groupId, 1, cost);
    }
  });

  // 小组节点连接汇点,设置容量浮动
  const extraCount = totalUser % groupCount;
  for (let groupId = 0; groupId < groupCount; groupId++) {
    const capacity = groupId < extraCount ? baseGroupSize + 1 : baseGroupSize;
    mcf.addEdge(groupNodeStart + groupId, sink, capacity, 0);
  }

  // 计算最小费用最大流
  mcf.flow(source, sink, totalUser);
  const dailyResult = {};
  // 解析分配结果
  mcf.edges.forEach(edge => {
    if (edge.from >= userNodeStart && edge.from < groupNodeStart && edge.flow === 1) {
      const user = users[edge.from - userNodeStart];
      const groupId = edge.to - groupNodeStart;
      dailyResult[user.id] = groupId;
      usedMap.set(`${user.id}-${groupId}`, true);
    }
  });
  return dailyResult;
}

// 生成5天分组的调用示例
function generate5DayGroups(users) {
  const usedMap = new Map();
  const result = [];
  for (let i = 0; i < 5; i++) {
    result.push(generateDailyGroup(users, usedMap));
  }
  return result;
}

内容的提问来源于stack exchange,提问作者nobody5000

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.10.08 11:00:02