提出了一种基于矢量图与像素图混合表达的二维不规则排样构造算法.在算法的初始阶段，零件信息采用矢量方式输入，在寻找最优排样姿态阶段则采用像素化表达，最后为了消除零件之间的缝隙并输出精确的排样图，零件恢复为矢量图表达.算例分析表明，该算法具有复杂度低、执行速度快和排样效果好的优点，有望推广为一种新型三维不规则排样构造算法,并基于图形处理器(GPU)的并行计算技术对其进行性能升级.
A two-dimensional constructive packing algorithm is proposed, which is based on hybrid representation of vector graphics and bitmaps. The shapes are input in form of vector graphics in the primary procedure of packing, and then they are represented by the pixels before seeking the optimal packing attitude. In order to eliminate gaps between the shapes and export the accurate packing layout, the shapes are represented again by the vector graphics. The computational experiments have proved that this algorithm has advantages of low complexity, high execution speed and good packing performance. These advantages make it possible to transform this algorithm into a new constructive algorithm for 3D packing problems. In addition, the parallel computing technology based on GPU is expected to be used to upgrade its computing performance.
［1］MARTINEZ-SYKORA A, ALVAREZ-VALDES R, BENNELL J A, et al. Matheuristics for the irregular bin packing problem with free rotations［J］. European Journal of Operational Research, 2017, 258(2): 440-455.
［2］GOMES A M. Irregular packing problems: Industrial applications and new directions using computational geometry［J］. IFAC Proceedings Volumes, 2013: 46(7): 378-383.
［3］ROCHA P, RODRIGUES R, GOMES A M, et al. Circle covering representation for nesting problems with continuous rotations［J］. IFAC Proceedings Vo-lumes, 2014, 47(3): 5235-5240.
［4］JUNIOR B A, PINHEIRO P R, SARAIVA R D. A hybrid methodology for nesting irregular shapes: Case study on a textile industry［J］. IFAC Proceedings Volumes, 2013, 46(24): 15-20.
［5］BURKE E K, HELLIER R S R, KENDALL G, et al. Complete and robust no-fit polygon generation for the irregular stock cutting problem［J］. European Journal of Operational Research, 2007, 179(1): 27-49.
［6］LIU X, YE J W. Heuristic algorithm based on the principle of minimum total potential energy (HAPE): A new algorithm for nesting problems［J］. Journal of Zhejiang University-Science A (Applied Physics & Engineering), 2011, 12(11): 860-872.
［7］TOLEDO F M B, CARRAVILLA M A, RIBEIRO C, et al. The dotted-board model: A new MIP model for nesting irregular shapes［J］. International Journal of Production Economics, 2013, 145(2): 478-487.
［8］COOK S. CUDA programming: A developer’s guide to parallel computing with GPUs［M］. Burlington: Morgan Kaufmann Publishers Inc, 2012: 19-34.
［9］VERKHOTUROV M, PETUNIN A, VERKHOTUROVA G, et al. The 3D object packing problem into a parallelepiped container based on discrete-logical representation［J］. IFAC-PapersOnLine, 2016, 49(12): 1-5.
［10］刘虓, 操安喜, 叶家玮.一种新型不规则三维排样构造算法［J］.上海交通大学学报, 2013, 47(7): 1060-1064.
LIU Xiao, CAO Anxi, YE Jiawei. A novel constructive algorithm for irregular three-dimensional packing problems［J］. Journal of Shanghai Jiao Tong University, 2013, 47(7): 1060-1064.
