三次分配问题(AP3问题)是一种经典的组合优化问题,是线性分配问题的直接推广。线性分配问题是在两个基数相同的有限集合上进行一对一分配。线性分配问题可以使用匈牙利算法在多项式时间内完成最优值求解。三次分配问题,是在三个基数相同的有限集合上进行分配,但三次分配问题已经被证明是NP难问题,因此不存在多项式时间算法求解三次分配问题的最优值。而三次分配问题具有很广泛的应用领域,因此目前学术界已经提出了许多启发式算法来求解三次分配问题的次优解。本文首先基于NP难问题求解的有效策略“肌肉”(最优解的并集),提出了一种基于近似“肌肉”的束搜索(Beam Search)算法来求解三次分配问题。该算法首先对问题进行分析,求解出其近似“肌肉”,减小搜索空间,再使用束搜索在所得的近似“肌肉”上完成求解。通过“肌肉”和束搜索来合理地缩小问题搜索空间,达到了问题求解质量和算法运行时间开销的平衡。通过在标准数据集上进行实验,从实验结果中可以发现,和现有的启发式算法相比,本文提出的算法可以求得质量较好解,并且在规模较大的问题上也可以在合理的运行时间内完成求解。该算法不仅仅是一个求解三次分配问题的有效求解算法,更是束搜索的一种有效的改进方法。对于大规模的三次分配问题,本文提出了一种基于数学规划求解器的超启发式算法对其进行求解。数学规划求解器是一种专门用于求解数学规划问题的工具,可以在较短的时间内完成对规模较小的问题实例的求解。而对于规模较大的问题,数学规划求解器受内存大小和问题复杂度的影响,可能无法在合理时间内完成求解。本文提出了一个超启发式算法,通过在求解的不同阶段使用不同的算子构建出大规模的三次分配问题的子问题,然后使用数学规划求解器对子问题进行求解,进而完成对大规模的三次分配问题的求解。使用数学规划求解器的优势在于,只需要将问题转化为数学规划的格式作为求解器的输入即可,需要很少的领域知识来构建对应问题的启发式算法,有很好的可移植性。实验表明,该算法可以在较短的时间内求出大规模的三次分配问题的具有较高质量的解,并具有很好的适应性。