Journal of Computer Applications ›› 2018, Vol. 38 ›› Issue (4): 1195-1200.DOI: 10.11772/j.issn.1001-9081.2017092230

Previous Articles     Next Articles

Heuristic packing algorithm based on forbearing stratified strategy

LIANG Lidong, JIA Wenyou   

  1. School of Mechanical and Automotive Engineering, Anhui Polytechnic University, Wuhu Anhui 241000, China
  • Received:2017-09-12 Revised:2017-11-17 Online:2018-04-10 Published:2018-04-09
  • Supported by:
    This work is partially supported by the National Natural Science Foundation of China (51576001).

基于宽容分层策略的启发式排样算法

梁利东, 贾文友   

  1. 安徽工程大学 机械与汽车工程学院, 安徽 芜湖 241000
  • 通讯作者: 梁利东
  • 作者简介:梁利东(1972-),男,山西忻州人,副教授,博士,主要研究方向:CAD/CAM、智能计算、优化算法设计;贾文友(1973-),男,安徽芜湖人,副教授,博士,主要研究方向:机电一体化、图形图像处理、数据挖掘。
  • 基金资助:
    国家自然科学基金资助项目(51576001)。

Abstract: Focusing on the balance between the best-fit method and the evaluation of packing layout, a new effective best-fit heuristic algorithm for 2D packing problem was proposed based on forbearing stratified strategy for multi-objective optimization. Firstly, the packing space and fit values were defined, and the wide and high fit values of the current part and the packing space were calculated, then the unified multi-objective optimization function model and packing priority rule were built based on the objective function values. Especially for the general placeable-fit situation, the best layout was finally achieved by setting and adjusting the tolerance values. The computational results on benchmark problems of 7 kinds of data show that the average Gap is reduced by 2% compared with Lowest-Level Left Align Best Fit (LLABF) and Lowest Skyline Best Fit (LSBF); the packing heights reach 24 and 339 respectively for two sets of random data of C1P1+C3P1 and C2-C7 (The number of rectangles is 33 and 66). This algorithm can also be used for irregular part packing optimization.

Key words: forbearing stratified method, two-dimensional packing problem, heuristic algorithm, tolerance value

摘要: 针对2D Packing排样方法中存在的择优匹配思想与排样优劣评估的平衡性问题,基于多目标优化的宽容分层策略提出一种新颖有效的择优匹配启发式排样算法。首先,定义排样空间和匹配值,计算入排零件与排样空间的宽、高匹配值,然后建立统一的多目标优化函数模型,并根据目标函数值的大小来确定排放优先规则。特别针对一般可排入匹配情况,可在目标函数模型中通过设置和调整宽容值,最后实现多种排样布局的最优化。对benchmark问题的7类数据实例的计算结果表明,该算法相对于底部左齐择优匹配(LLABF)和水平线择优匹配(LSBF)算法,Gap的平均值可降低了2%;在C1P1+C3P1以及C2~C7随机构成的两组混合数据测试中(矩形数量为33和66),排样高度达到24和339。该算法也可用于多类型异形零件的排样过程。

关键词: 宽容分层方法, 二维排样问题, 启发式算法, 宽容值

CLC Number: