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,费用为0
- 用户节点→可用小组节点:边容量为1,费用对应用户对该小组的偏好等级
- 小组节点→汇节点:边容量按12-14的浮动区间设置,保证总容量≥100
- 运行最小费用流算法,得到当日分配结果
- 更新用户-小组可用映射表:将当日已分配的用户-小组组合标记为不可用,后续天数不再纳入候选
- 重复上述步骤直到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
相关产品推荐
相关产品推荐

