带类别约束的Bin Packing变体问题：寻求最优解算法

问题概述 #

这是经典装箱问题的双目标变体：

• 有n个不同重量的物品，分成X、Y两类
• 所有物品需装入固定容量的箱子中
• 核心目标：最小化使用的箱子总数
• 附加目标：在箱子总数最优的前提下，尽量减少同时包含X、Y两类物品的混合箱子数量

已有的研究局限 #

目前检索到的带类别约束的装箱问题变体，大多是以「每个箱子内的类别数量上限」为约束条件的类型，尚未发现直接针对「最小化混合箱子数量」这个目标的最优解算法相关研究。

可行的探索方向 #

• 先通过经典装箱问题求解逻辑得出最小箱子数的最优解集合，再在该集合内筛选混合箱数量最少的方案——可采用整数规划建模，将两个目标按优先级处理，先确保箱子数最优，再优化混合箱数量
• 改造经典近似算法（如FFD首次递减、BF最佳适配）：分配物品时优先将同类别物品凑满一箱，仅当同类别物品无法填满剩余容量时，才考虑放入另一类物品，以此尽可能减少混合箱的产生
• 参考多目标组合优化的通用框架，比如帕累托最优解的求解思路，不过由于该问题有明确的目标优先级，分层优化的效率可能更高

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