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

doi:10.11772/j.issn.1001-9081.2017092230

计算机应用 ›› 2018, Vol. 38 ›› Issue (4): 1195-1200.DOI: 10.11772/j.issn.1001-9081.2017092230

• 应用前沿、交叉与综合 • 上一篇下一篇

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

梁利东, 贾文友

安徽工程大学机械与汽车工程学院, 安徽芜湖 241000

收稿日期:2017-09-12 修回日期:2017-11-17 出版日期:2018-04-10 发布日期:2018-04-09
通讯作者: 梁利东
作者简介:梁利东(1972-),男,山西忻州人,副教授,博士,主要研究方向:CAD/CAM、智能计算、优化算法设计;贾文友(1973-),男,安徽芜湖人,副教授,博士,主要研究方向:机电一体化、图形图像处理、数据挖掘。
基金资助:
国家自然科学基金资助项目（51576001）。

Heuristic packing algorithm based on forbearing stratified strategy

LIANG Lidong, JIA Wenyou

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).

摘要/Abstract

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

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

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

中图分类号:

TP391.9

梁利东, 贾文友. 基于宽容分层策略的启发式排样算法[J]. 计算机应用, 2018, 38(4): 1195-1200.

LIANG Lidong, JIA Wenyou. Heuristic packing algorithm based on forbearing stratified strategy[J]. Journal of Computer Applications, 2018, 38(4): 1195-1200.

参考文献

[1] LODI A, MARTELLO S, MONACI M. Two-dimensional packing problems:a survey[J]. European Journal of Operational Research, 2002, 141(2):241-252.
[2] LESH N, MARKS J, MAHON A, et al. Exhaustive approaches to 2D-rectangular perfect packings[J]. Information Processing Letters, 2004, 90(1):7-14.
[3] MARTELLO S, MONACI M, VIGO D. An exact approach to the strip-packing problem[J]. INFORMS Journal of Computing, 2003, 15(3):310-319.
[4] BAKER B, COFFMAN E, RIVEST L. Orthogonal packings in two dimensions[J]. SIAM Journal on Computing, 1980, 9(4):846-855.
[5] CHAZELLE B. The bottom left bin packing heuristic:an efficient implementation[J]. IEEE Transactions on Computers, 1983, C-32(8):697-707.
[6] HOPPER E, TURTON B. An empirical investigation of meta-heuristic and heuristic algorithms for a 2D packing problem[J]. European Journal of Operational Research, 2001, 128(1):34-57.
[7] LESH N, MITZENMACHER M. BubbleSearch:a simple heuristic for improving priority-based greedy algorithms[J]. Information rocessing Letters, 2006, 97(4):161-169.
[8] BURKE E, KENDALL G, WHITWELL G. A new placement heuristic for the orthogonal stock-cutting problem[J]. Operations Research, 2004, 52(4):655-671.
[9] BORTFELDT A, GEHRING H. New large benchmark instances for the two-dimensional strip-packing problem with rectangular pieces[C]//Proceedings of the 39th Hawaii International Conference on Systems Sciences. Washington, DC:IEEE Computer Society, 2006:30.
[10] 张德富, 韩水华, 叶卫国.求解矩形Packing问题的砌墙式启发式算法[J]. 计算机学报, 2008, 31(3):509-515.(ZHANG D F, HAN S H, YE W G. A bricklaying heuristic algorithm for the orthogonal rectangular packing problem[J]. Chinese Journal of Computers, 2008, 31(3):509-515.)
[11] 姚怡, 吴金波, 赖朝安. 采用分层搜索填充策略的启发式带排样算法[J]. 武汉大学学报(工学版), 2014, 47(6):854-859.(YAO Y, WU J B, LAI C A. Heuristics for rectangular strip packing problem based on hierarchical search filled strategy[J]. Engineering Journal of Wuhan University, 2014, 47(6):854-859.)
[12] 何琨, 姬朋立. 求解二维矩形Packing面积最小化问题的动态规约算法[J]. 软件学报, 2013, 24(9):2078-2087.(HE K, JI P L. Heuristics for solving the 2D rectangle packing area minimization problem basing on a dynamic reduction method[J]. Journal of Software, 2013, 24(9):2078-2087.)
[13] HUANG W, CHEN D, XU R. A new heuristic algorithm for rectangle packing[J]. Computer & Operations Research, 2007, 34(11):3270-3280.
[14] CHEN M, HUANG W. A two-level search algorithm for 2D rectangular packing problem[J]. Computer & Industrial Engineering, 2007, 53(1):123-136.
[15] 张怀宇, 杨根科, 白杰. 二维Strip Packing问题的嵌套启发式算法[J]. 系统仿真学报, 2012, 24(8):1601-1605, 1623.(ZHANG H Y, YANG G K, BAI J. Nested heuristic algorithm for two-dimensional strip packing problem[J]. Journal of System Simulation, 2012, 24(8):1601-1605, 1623.)
[16] JIANG X, LU X, LIU C. Lowest-level left align best-fit algorithm for the 2D rectangular strip packing problem[J]. Journal of Software, 2009, 20(6):1528-1538.
[17] LIU D, TENG H. An improved BL-algorithm for genetic algorithm of the orthogonal packing of rectangles[J]. European Journal of Operation Research, 2006, 172(3):814-837.
[18] ZHANG D, CHEN S, LIU Y. An improved heuristic recursive strategy based on genetic algorithm for the strip rectangular packing problem[J]. Acta Automatica Sinica, 2007, 33(9):911-916.
[19] HOPPER E, TURTON B. An empirical investigation of meta-heuristic and heuristic algorithms for a 2D packing problem[J]. European Journal of Operational Research, 2001, 128(1):34-57.
[20] BURKE E, KENDALL G, WHITWELL G. Metaheuristic enhancements of the best-fit heuristic for the orthogonal stocking cutting problem:NOTTCS-TR-2006-3[R]. Nottingham:University of Nottingham, 2006.
[21] BORTFELDT A. A genetic algorithm for the two-dimensional strip packing problem with rectangular pieces[J]. European Journal of Operational Research, 2006, 172(3):814-837.

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

Heuristic packing algorithm based on forbearing stratified strategy

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	韦铭燕, 陈彧, 张亮. 针对混合变量优化问题的协同进化蚁群优化算法[J]. 计算机应用, 2021, 41(5): 1412-1418.
[2]	隗千千, 董兴业, 王焕政. 染缸排产建模及滑动时间窗启发式调度算法[J]. 计算机应用, 2020, 40(1): 292-298.
[3]	张宪立, 唐建新, 曹来成. 基于反向PageRank的影响力最大化算法[J]. 计算机应用, 2020, 40(1): 96-102.
[4]	吴斌, 王超, 董敏. 基于混合果蝇优化算法的现场服务调度问题[J]. 计算机应用, 2018, 38(9): 2706-2711.
[5]	郭羽含, 张美琪, 周楠. 基于偏好矩阵遗传算法求解长期车辆合乘问题[J]. 计算机应用, 2017, 37(2): 602-607.
[6]	陈闯, Ryad Chellali, 邢尹. 采用动态权重和概率扰动策略改进的灰狼优化算法[J]. 计算机应用, 2017, 37(12): 3493-3497.
[7]	徐达宇, LIU Renping. 基于改进自组织临界优化的元启发式灰狼优化算法[J]. 计算机应用, 2016, 36(6): 1588-1593.
[8]	向婷, 潘大志. 求解需求可拆分车辆路径问题的聚类算法[J]. 计算机应用, 2016, 36(11): 3141-3145.
[9]	陈娟. 传感环境下基于局部Voronoi图的启发式反监控路径发现算法[J]. 计算机应用, 2015, 35(1): 15-18.
[10]	王永, 胥冬川, 农兰晶. 震后过渡阶段应急物流系统的定位运输路线安排问题研究[J]. 计算机应用, 2015, 35(1): 243-246.
[11]	徐雪松舒俭. 多模型数据集的免疫鲁棒回归分析[J]. 计算机应用, 2014, 34(8): 2285-2290.
[12]	路静顾军华. 改进和声搜索算法及其在连续函数优化中的应用[J]. 计算机应用, 2014, 34(1): 194-198.
[13]	郭新明. 高效无线传感器网络强k-栅栏覆盖节能算法[J]. 计算机应用, 2013, 33(08): 2104-2107.
[14]	张良徐成田峥李涛. 基于贪心算法和模拟退火算法的软硬件划分[J]. 计算机应用, 2013, 33(07): 1898-1902.
[15]	秦志光柯涛刘梦娟王聪. 面向云平台的资源分配策略研究[J]. 计算机应用, 2013, 33(02): 299-307.