满足“一刀切”约束的单侧最低水平线法求解排样问题.pdf

年月第 卷 第期河北水利电力学院学报 文章编号：（）满足“一刀切”约束的单侧最低水平线法求解排样问题张鹏程，王文成，张铁壁，冯汉屏（河北省工业机械手控制与可靠性技术创新中心，河北省沧州市黄河西路 号 ；沧州市工业机械手控制与可靠性技术创新中心，河北省沧州市黄河西路 号 ；河北水利电力学院 机械工程系，河北省沧州市黄河西路 号 ）摘要：提出了满足“一刀切”约束的单侧最低水平线法，该方法以现有的最低水平线法为基础，在选择矩形件摆放顺序及摆放位置时，皆以最左侧矩形为基准，所有矩形实行分层密布，使得排样结果既满足较高的材料利用率，又使矩形摆放符合“一刀切”的工艺要求，从而缩短刀具加工行程，提高加工效率。关键词：一刀切约束；最低水平线法；排样问题；遗传算法；排样策略中图分类号：；文献标识码：钣 金冲 裁业中 材料的 费 用 约 占 制 造 成 本 的 ，板材工艺废料率平均为 。据不完全统计，材料利用率每增加，冲压件成本将会降低 。因此，设计高质量的排样方案是降低冲压零件成本的最重要途径。此外，良好的排样设计方案也是凹模、卸料板等冲裁模具设计的基础。由于件在板材上的排布方式是多种多样的，设计者仅凭经验和传统认知制定排样方案几乎不可能得到较高的材料利用率，特别是当生产规模较大，零件形状复杂、约束条件增多时，获得的排样方案的质量和效率更是难以令人满意，。排样问题属于 完全问题，就复杂程度而言，具有最高的复杂度，而设计通用性好、求解质量和效率高、易于实现的排样算法一直是该领域研究所追求的目标。根据零件的形状，二维排样问题分为规则零件排样和不规则零件排样。规则零件排样问题主要以矩形件和圆形件排样为主，其求解方法多为近似算法或者启发式算法，如：曹炬等采用背包算法，该方法能够快速地找到部分问题的近似最优解；贾志欣等提出了最低水平线排样算法，并将该算法与模拟退火算法相结合，获得了不错的排样效果；陈端兵、黄文奇针对排样空间的变化，提出了一种基于占穴思想的启发式算法；提出利用遗传算法来解决矩形件排样等。综合不同求解方法可以看出：一些算法的排样效果不错，但不满足“一刀切”约束；一些算法在设计时虽然考虑了“一刀切”问题，但整体排样效果较差，材料利用率不高。因此，设计一种优化算法，使得排样结果既满足材料利用率要求，在切割加工时，亦满足“一刀切”要求，可以使得排样方案具有更高的实用性。另外，为了进一提高排样质量，将包括遗传算法、蚁群算法、模拟退火算法等智能算法更多地引入到排样策略之中，使更优秀的求解方案的获得成为可能。文中针对矩形件排样问题，提出一种在满足“一刀切”约束的单侧最低水平线法，该方法以现有的最低水平线法为基础，在满足板材料较高利用率的同时，使矩形摆放符合“一刀切”的加工要求，从而使排样方案更加高效、便捷地应用于工程实践。最低水平线法原理最低水平线法的基本思想是矩形件的横边构造水平线集，将要摆入的矩形件优先排放在最低水收稿日期：修回日期：基金项目：河北省教育厅科学技术研究项目资助（，）；沧州市科技计划自筹经费项目（，）；河北省大学生创新创业训练计划项目（）第一作者简介：张鹏程（），男，河北泊头人，硕士研究生，高级实验师，研究方向：计算机辅助设计、机械产品布局。：通讯作者简介：张铁壁（），男，河北海兴人，教授，主要从事智能仪器仪表技术研究。：平线上，并不断更新水平线集；如果最低水平线宽度不够，矩形件无法放入，则在水平线集中搜索最低水平线左右两边相邻的水平线，选择较低的一条，同时，将最低水平线提升至该高度，继续判断更新后的最低水平线能否排入该矩形，若依然排不下则继续提升水平线位置，直至该矩形能排入为止。设矩形板材的宽度犠为一定值，高度为犎，矩形件集为（犚，犚，犚狀），零件个数为狀，其中第犻个矩形件犚犻为（犾犻，狑犻）。以板材的左上角为原点，宽度方向为狓轴，高度方向为狔轴建立直角坐标系。矩形件在板材中的位置采用其左下和右上两个顶点坐标来表示，如图所示，（为了与排样结果显示一致，将坐标系按顺时针方向旋转 摆放），矩形件犚的长为犾，宽为狑，左下角坐标值为（犪，犫），则可以用犚（犪，犫，犪犾，犫狑）来表示矩形件犚在板材中的位置。图板材坐标系及矩形的位置表示法 采用最低水平线法矩形件的排样过程 如图所示。水平线以（狓狊，狓犲，狔）表示，其中狓狊、狓犲分别表示水平线起点和终点的横坐标，狔表示水平线的纵坐标。矩形件摆放之前，水平线只有一条，为板材的底边（，犔，），如图（）所示。当第个矩形件犚放入时，其占据的位置为（，犾，狑），此时，水平线集变为（，犾，狑），（犾，犔，），如图（）所示。第个矩形件犚准备放入时，取当前最低的水平线（犾，犔，）的长度与矩形件犚的犾比较，水平线长度大于矩形件长度，故矩形可以直接放置，其占据的位置为（犾，犾犾，狑），此时，最低水平线集变为（，犾，狑），（犾，犾犾，狑），（犾犾，犔，），如图（）所示。第个矩形犚件依次放入图（）中所示位置。第个矩形件犚放入时，首先取水平线集中最低的（犾犾犾，犔，）长度犔（犾犾犾）与矩形件长度犾比较，水平线长度小于矩形件长度，因此无法放入，此时，提升水平线（犾犾犾，犔，）至（犾犾，犾犾犾，狑）的高度，如图（）所示，更新水平线集为（，犾，狑），（犾，犾犾，狑），（犾犾，犔，狑），从水平线集中找到最低水平线（犾犾，犔，狑），取其长度犔（犾犾）与矩形件犚的长度犾比较，水平线长度大于矩形件长度，矩形件可以放入，如图（）所示。后序矩形件的排样依此类推。图最低水平线法原理图 最低水平线搜索算法将待排样的矩形件按顺序及最低位置进行摆放，直到板材空间水平线集中所有水平线皆无法满足该矩形件放入为止。分析可知，按此方法排样，会产生个问题：一是不可避免会因为水平线的更新造成一些板材区域的浪费；二是由于未对已放入矩形件尺寸进行限制，其排列方式相互交错，这很大程度上增加了板材切割时的难度。生产实际要求对于排样算法的研究，既要兼顾材料利用率，又要考虑下料的效率。板材切割时，如果切割刀具以与板材宽度平行的直线刀轨贯穿或者基本贯穿整个板材，尽量减少折线方式走刀，就可以尽可能减少刀具空行程和重复走刀，提高加工效率，这就是排样时“一刀切”问题。满足“一刀切”约束的最低水平线法 算法原理通过对现有最低水平线算法排样过程进行分析，提出单侧最低水平线法以满足下料时的“一刀切”约束。该方法以最低水平线法为基础，在安排矩形件排放顺序和摆放位置时，都以现有最左侧零件为基准，使得后序矩形件高度均不超过最左侧零件的高度，这样在下料时，所有矩形件呈现类似分层摆放，呈条带式排列，加工时就可以实现一刀切。此过程也可以看作是单侧的下台阶法。第期张鹏程等：满足“一刀切”约束的单侧最低水平线法求解排样问题 算法流程采用基于“一刀切”约束的最低水平线算法流程具体步骤如下：初始化水平线集，初始状态下水平线集中只有条水平线，即板材的宽边。：在零件集中选择要排入的矩形件。：从当前水平线集中选取最低水平线，如果不止一条，则选取最靠左边的那条。：判断水平线起点横坐标是否为，如是，（说明该水平线为水平线集中最左最低的那条），将矩形件放置到水平线最左端，转 ，否则，执行 。：判断矩形件的高是否大于水平线左侧矩形的高，如是，说明该矩形件超过限高，从零件集中向后搜索一个可以放下的零件，同时交换这两个零件的位置，转 ，否则，执行 。：将该矩形件排放在最低水平线的最左端，增加条水平线，更新水平线集，转步骤 。：判断所有矩形件是否排样完毕，如是，则排样结束，否则，执行步骤 。算法流程图如图所示。图算法流程图 实例验证设原始板材 ，待排样矩形件 件，其 中 的 件，的 件，的 件。采用上述算法获得的排样结果如图所示，板材利用率 。从排样结果看，该方法可以较好地解决矩形零件的自动排样问题，而且，矩形零件在板材上呈条带状排布，满足“一刀切”约束，便于加工时实现“一刀切”操作或者分层切割。图满足“一刀切”约束的单侧最低水平线法算例 河北水利电力学院学报 利用遗传算法优化排样过程 编码及种群初始化初始种群的好坏对遗传算法的收敛速度和求解质量有很大的影响。文中采用随机生成初始种群，该方法可以将更多的可行解纳入优化范围，且思路简单，容易实现。根据矩形件优化排样问题的特点，个矩形件零件的编号对应个基因的编码。假设要排样的矩形件总数为狀，犿个矩形零件的编号构成条染色体，种群中每条染色体的长度与待排矩形零件总数相同。设犘为一种矩形排序序列，代表了一种排样结果，则犘犘，犘，犘犻，犘犿，其中犻犿，犿狀，犘犻代表任意一个矩形编号，犘犻有正负之分，正数表示零件不发生旋转，负数表示将零件从原始的状态旋转。犿个个体犘构成个种群。种群规模的大小对遗传算法的性能有一定影响：种群规模越大，群体中个体的多样性就越高，算法陷入局部解的危险性就越小，但种群的规模太大会使算法的计算量增加，从而影响算法的性能。种群的规模太小，会使遗传算法的搜索空间中分布范围有限，因而搜索可能停止在未成熟阶段。因此，为了避免早熟现象，群体的规模一般在 之间，过大或过小均影响遗传算法的综合性能。构造适应度函数工程中的排样问题，其主要目标是减少板材消耗，尽可能提高材料的利用率，故以板材利用率构造适应度函数：犳（犘）犛犛式中，犛是排入矩形件的总面积，犛是排样图高度轮廓线以下的板材面积。适应度值最高为，即代表材料利用率 。遗传算子 选择算子遗传算法中的选择操作就是用来确定如何从父代群体中按某种方法选取哪些个体遗传到下一代群体中的一种遗传运算。遗传算法使用选择算子对群体中的个体进行优胜劣汰操作：适应度较高的个体被遗传到下一代群体的概率较大；适应度较低的个体被遗传到下一代群体的概率较小。文中采用由适应度函数值来确定个体的优劣，在确定选择算子时，初始种群即父代群体经过交叉变异后形成的子代群体与原来的父代群体组成一个新的群体，对每个个体的适应度进行降序排序，保留适应度最高的一半个体作为新的父代群体进行交叉变异，循环迭代，层层选优。交叉算子交叉是指把两个父代个体的部分结构加以替换重组而生成新的个体。交叉是产生新个体的主要方法，它决定了遗传算法的全局搜索能力。将犿个父辈解群的个体进行自交叉操作，产生犿个子辈个体，具体操作方法如下：设父辈个体为犘犘，犘，犘狀，在狀范围内随机选取两个整数狆和狇，以狆为起点，狇为终点，从犘中拷贝狇狆个元素到其子辈个体犘 作为前狇狆个元素，剩余的狀狇个元素按其在犘中出现的次序依次拷贝到犘，从而产生出子辈个体犘。个体交叉过程如图所示。图个体交叉过程示意图 变异算子利用变异算子增加群体中基因模式的多样性，强化群体进化过程中自然选择的作用，避免群体进化过程过早地陷入局部最优解。交叉算子和变异算子相互配合，共同完成对搜索空间的全局搜索和局部搜索，从而使遗传算法能够以良好的搜索性能完成最优化问题的寻优过程。排样过程中的变异可以设计两种类型，一是位置变异，其方法获取狀之间的两个随机数 和 ，在矩形序列中将该位置的两个矩形对调。二是旋转变异，通过产生一个随机数，然后将该数取其相反数，即在矩形序列中，将对应的矩形进行旋转，改变其姿态。文中采用遗传算法流程图如图所示。算例与分析采用 编程，设计统一的排样系统验证算法的有效性。设板材原始尺寸为 。第期张鹏程等：满足“一刀切”约束的单侧最低水平线法求解排样问题图遗传算法流程图 算法的有效性 单一矩形件排样零件大小设为 的矩形，数量为 个，板材利用率 ，排样结果如图所示。该测试结果验证了算法稳定性，即对于简单的排样问题，算法输出结果与直观计算是一致的。图单一矩形件排样结果图 不同规格矩形件排样零件为不同规格的矩形，其尺寸及数量如表中所示，板材利用率为，排样结果如图所示。表测试矩形件数据 编号宽高数量个 图不同规格矩形件排样结果图 从排样结果看，该方法较好的完成了排样设计要求。对于长板下料问题（工程实际中板的长度可以看作无限长），零件从板材的一端开始布置，排头矩形件首先进行摆放，后序矩形件的高度以此矩形件高度为界，按事先给定的顺序依次放入，当排样过程中矩形件高度超排头矩形件高度时，则将在矩形序列中取下一个矩形件进行比较，待没有零件可放入时，则重新开始布置下一层。零件在板材上分层排布使得在板材下料分割时，便于实现“一刀切”，从而缩短走刀行程。不同规模排样问题采用多组不同尺寸、数量的组矩形零件进行测试，问题规模从小到大，零件组情况及板材利用率如表所示，排样结果图如图、图 所示。表不同规模排样问题及测试结果 组别零件种类种 零件数量个板材利用率 河北水利电力学院学报 图 个矩形零件排样图 图 个矩形零件排样图 从排样结果看，矩形件的摆放都以最左端矩形的高度为标尺，后序的矩形无论是否拼接，其高度都不会超过左端排头矩形，因此，很容易实现“一刀切”的裁切方式，减少走刀时间；也可以事先对板材进行分段，再将其分别切割成不同零件的大小。前者适合自动机床加工，后者适合人工裁剪。遗传算法的优化结果从上文算例可以看出，排样结果很大程度依赖矩形件的初始排列顺序，而且，受到最左端矩形件尺寸的影响。因此，文中采用遗传算法，结合前述单侧最低水平线排放策略，对矩形件的排样顺序进行优化，从众多的可行方案中寻找到一个最优解，以实现材料的最大利用率。以表中 个矩形件的排样问题为例，采用上述基于“一刀切”约束的最低水平线算法直接进行排样，矩形件采用原始顺序，排样结果如图 所示，板材利用率为 。表测试矩形件数据 编号宽高数量 编号宽高数量 图 个矩形零件直接排样图 采用遗传算法对于矩形件的排样顺序进行优化，其中：染色体的长度取排样矩形的数量 ，种群大小取，交叉概率取，变异概率取 ，遗传代数取，以空间利用率为适应度函数，通过编程计算，获得最终排样结果如图 所示，板材利用率为 。图 个矩形零件优化后排样图 由此可见，利用遗传算法对矩形件排样顺序进行优化，可以获得更优异的排样方案，板材利用率从 提升到 ，增加了 。实验结果表明，利用智能算法对于排样过程进行优化，可以在很大程度上提高材料的利用率，使得排样结果有明显的改善。另外，更多的实验测试及分析表明：在利用遗传算法优化排样问题的过程中，不同的初始化参数对于排样的结果会产生一定的影响；变换部分参数取值范围也可以在一定程度上增加算法搜索范围，增大解空间，进一步提高排样方案质量，增加板材利用率。结论在现有最低水平线方法的基础上，提出满足“一刀切”约束的单侧最低水平线法的求解策略，该方法以最左侧放入的矩形为标准，将最低水平线的提升第期张鹏程等：满足“一刀切”约束的单侧最低水平线法求解排样问题限制在排头矩形的单侧（右侧），避免了水平低双向提升时造成的矩形排列参差不齐的问题，使得右侧放入的矩形总高度不超过排头矩形的高度，这样在下料时，所有矩形件呈现类似分层摆放，呈条带式排列，加工时便于实现一刀切。使得排样方案既实现了高效性，也满足了实用性。文中算法是针对矩形零件排样问题提出的，但在同类问题求解中，如对于其它不同几何形状的零件排样问题，可以先通过构造零件最小包络矩形的方式，将其转化为矩形件排样问题，再应用该方法求解。而该算法的原理和思想，也可以直接应用到非矩形件排样方案的设计和优化过程中去。参考文献王金敏，王保春，朱艳华求解矩形布局问题的自适应算法图学学报，（）：张鹏程，郗艳梅，李国顺，等利用可行域的矩形布局求解方法现代制造工程，（）：，（）：，（）：曹炬，周济，余俊矩形件排样优化的背包算法中国机械工程，（）：贾志欣，殷国富，罗阳，等矩形件排样的模拟退火算法求解四川大学学报（工程科学版），（）：陈端兵，黄文奇求解矩形 问题的贪心算法计算机工程，（）：，（）：张娜，赵罘，龚堰珏，等基于动态最低水平线法和蚁群算法的排样优化计算机应用与软件，（）：刘海明，周炯，吴忻生，等基于改进最低水平线方法与遗传算法的矩形件排样优化算法图学学报，（）：黄河，许超基于优先度的改进最低水平线排样算法锻压装备与制造技术，（）：张鹏程，茹江燕基于贪心策略的单一下料问题求解研究河北水利电力学院学报，（）：王朋三类典型二维排样问题的智能算法及其应用武汉：华中科技大学，郑莹面向玻璃切割机的排样优化算法设计与实现武汉理工大学，犛 狅 犾 狏 犻 狀 犵犔 犪 狔 狅 狌 狋犘 狉 狅 犫 犾 犲 犿犫 狔犝 狀 犻 犾 犪 狋 犲 狉 犪 犾犔 狅 狑 犲 狊 狋犎 狅 狉 犻 狕 狅 狀 狋 犪 犾犔 犻 狀 犲犕 犲 狋 犺 狅 犱狅 狀犌 狌 犻 犾 犾 狅 狋 犻 狀 犲犆 狅 狀 狊 狋 狉 犪 犻 狀 狋 ，（，；，；，）犃 犫 狊 狋 狉 犪 犮 狋：，犓 犲 狔 狑 狅 狉 犱 狊：；（责任编辑：郭书俊）河北水利电力学院学报