二维下料问题的顺序按叠分组启发式算法

摘要

提出顺序按叠分组启发式算法求解二维按叠下料问题,确定按叠下料方案。顺序按叠分组启发式算法按顺序生成组成下料方案的布局图,对于每一个布局图,先根据整叠规则选择毛坯(矩形件)形成的候选毛坯集,再按候选毛坯集分组排样生成当前布局图,并根据整叠规则确定该布局图的使用次数;重复此布局图的生成过程,直至所有毛坯的需求均得到满足,从而确定下料方案。每次生成一个布局图后,通过毛坯价值修正算法对毛坯价值进行修正,使毛坯价值趋于合理。经多次迭代,生成多个不同的下料方案,从中选择总成本最低者作为按叠下料问题的解。实验结果表明,基于整叠规则的顺序分组启发式算法可明显降低二维按叠下料的总成本。