求解矩形件排样问题的启发式算法研究

摘要

排样问题是指在下料的过程中尽量减少材料的损失，使材料的利用率达到最高。它广泛存在于加工生产中，如板材切割、集装箱装载、服装和家具制造等。解决好这一问题，不仅可以节省原材料，降低企业生产成本，而且还可提高企业生产效率。 矩形件排样问题是二维排样问题的一个分支。国内外许多学者对其进行过深入和广泛地研究，理论上证明其属于NP完全问题。当遇到较大规模时，势必会带来计算量的组合爆炸，因此很难在一定时间内取得最优解。针对上述问题，目前解决的方法多为启发式方法。因此，研究矩形件排样问题既有实际应用价值，又有理论意义。 启发式方法的特点是解决问题时，利用过去的经验规则，选择行之有效的方法。对于大规模问题的优化求解，其具有快速随机的全局搜索能力，大大减少了计算量，表现出比其它方法更优越的性能。除此以外，启发式方法简单易行、易于理解，具有良好的可扩展性，是解决排样问题的重要工具。 本文研究的是二维矩形件排样问题，即在多张规格相同的矩形板材上排放一定需求量的毛坯，使得消耗板材的总面积达到最小。基于上述考虑，为了求解该问题，本文以“最小浪费优先策略”为基础，提出了一种分组搜索的启发式算法。与其它文献中报道的实例测试对比，板材利用率均有所改善，验证了本文算法的有效性。 本文所做的主要工作如下： 第一，认真分析了中外学者提出的多种启发式算法，经过仔细比较，在总结其优缺点的基础上，对“最小浪费优先策略”进行了改造。“最小浪费优先策略”是从浪费区域的角度考虑，即毛坯排入后是否产生浪费区域以及产生浪费区域的大小。本文在其基础上提出了两种改造策略，第一，增加了一个限制条件，即毛坯排入后如果产生的浪费区域大于某值，则取消其排入。修改后的策略避免了一些不良方案的出现。第二，是毛坯排入的方向。早期的策略使用“最左原则”排入毛坯，取得了很好的效果。本文在其基础上进行改造，增加了一个“最右原则”。改造后可能会增加毛坯摆放的多样性，对提高板材的利用率或许起到帮助。 第二，考虑优化计算时间过长，以及排样方案不均衡等问题，本文提出了一种分组策略，即把所有的毛坯按面积大小均分三组，每次生成当前方式前，都从三组中各选择适当的块数，用于生成当前方式。在分组的过程中，有一些参数可以依据实际情况进行调整。例如，为了确定适当的块数，从一组中挑选出的毛坯面积和应该定为何值，本文规定其最大为1倍的板材面积，最小为0.3倍的板材面积。经过分组操作后，选择了一个毛坯集合的子集，从而缩短生成当前方式所需时间。 第三，将改造的最小浪费优先和分组策略相结合，提出了一种启发式算法——分组搜索算法。算法中如何产生排样序列是其关键步骤。在现有的启发式算法中，有些学者应用遗传学的原理来生成排样序列，已经取得了较好的效果。本文引用随机局部搜索，利用随机交换两个毛坯的相对顺序，来生成新的排样序列。在随机操作中，需要使用一些技巧，当随机产生两个小矩形件的位置时，如果产生的位置相同，或者两个位置上小矩形件是同种，则把其中一个位置逐渐递加，直到位置上的两个小矩形件是不同种类为止，这样尽量增加序列的多样性，避免重复序列的生成。经过整体重复计算后，通过比较结果，保存较好的解，得到最终排样方案。分组搜索算法是一个组合算法，文中给出了其详细的伪码描述。 第四，通过对矩形件优化排样系统框架的分析，分别实现了其四个主要模块功能。包括数据输入模块、优化排样模块、排样结果显示模块、系统帮助模块。其中算法模块是整个框架的核心部分。本文选取了三组文献中的测试实例，其均与本文研究问题的排样规则相似，因此本文的算法与其测试结果具有可比性。经过测试后，并将实验结果与其进行了比较和分析，板材利用率均有所提升，验证了本文算法的有效性。 第五，对己完成的工作进行了总结，提出了需要进一步改进之处。