多类零件配对最小化合向量模长的最优组配方案求解问题

问题描述 #

场景需求 #

• 有三类零件Part A、Part B、Part C，每类零件数量相同（如各4个），每个零件对应一个二维向量(x,y)
• 组配规则：每个组合必须包含1个A、1个B、1个C，所有零件必须使用且仅使用一次
• 优化目标：所有组合的合向量模长sqrt((sum_x)^2 + (sum_y)^2)整体最优，需同时满足：
  • 所有组合的模长不超过预设的最大阈值
  • 所有组合的模长总和尽可能小，避免单组最优、剩余组效果极差的情况

现有实现问题 #

当前已通过三层循环遍历所有A、B、C的组合，预计算了每个组合的合向量模长，代码如下：

import math
import pandas as pd

i=1
for index, row in A.iterrows():
    SN_A = row['Serial Number']
    X_A = row['X']
    Y_A = row['Y']
    for index, row in B.iterrows():
        SN_B = row['Serial Number']
        X_B = row['X']
        Y_B = row['Y']
        for index, row in C.iterrows():
            SN_C = row['Serial Number']
            X_C = row['X']
            Y_C = row['Y']
            X_tot = X_A + X_B + X_C
            Y_tot = Y_A + Y_B + Y_C
            Res = math.sqrt((X_tot**2)+(Y_tot**2))
            Combo.loc[i] = [SN_A, SN_B, SN_C, X_tot, Y_tot, Res]
            i=i+1

但仅通过单组合模长排序的贪心选法会导致最后几组效果极差，无法得到全局最优的组配方案。

解决方法 #

该问题本质是三维带权完美匹配问题，可根据每类零件的数量选择对应方案：

小数据量（每类零件数n≤10） #

直接穷举所有合法组配方案即可，合法组配总数量为(n!)²，n=4时仅576种，计算量极低：

1. 分别提取A、B、C三类零件的列表，每个元素存储SN、x、y信息
2. 用itertools.permutations生成B的全排列，将B的排列元素和A按顺序一一配对
3. 再生成C的全排列，将C的排列元素和上一步的(A,B)配对按顺序一一匹配，得到一组完整的全量组配方案
4. 计算该方案下所有组合的模长总和，以及是否所有组合都符合阈值要求
5. 遍历所有合法方案后，筛选出满足阈值要求、总模长最小的方案即可

中等数据量（10<n≤20） #

用整数线性规划求解，不需要穷举，求解速度快，可保证得到全局最优解：

1. 预计算所有三元组(i,j,k)的模长res[i][j][k]，i对应A的索引、j对应B的索引、k对应C的索引
2. 定义变量x[i][j][k]，取值为1时表示该三元组成组，0表示不选
3. 约束条件设置：
   • 每个A仅用一次：所有j、k对应的x[i][j][k]之和为1
   • 每个B仅用一次：所有i、k对应的x[i][j][k]之和为1
   • 每个C仅用一次：所有i、j对应的x[i][j][k]之和为1
   • 阈值约束：res[i][j][k] * x[i][j][k] ≤ 最大阈值
4. 目标函数设置为所有res[i][j][k] * x[i][j][k]之和最小，调用ortools、pulp等线性规划库求解即可

大数据量（n>20） #

采用模拟退火、遗传算法等启发式算法，可在极短时间内得到接近最优的解，满足工业场景使用需求。

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