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.
LIU Xiao,YE Jiawei,LIU Jiamin
. Two-Dimensional Constructive Packing Algorithm
Based on Hybrid Representation Graphics[J]. Journal of Shanghai Jiaotong University, 2018
, 52(7)
: 825
-830
.
DOI: 10.16183/j.cnki.jsjtu.2018.07.010
［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.
