Discrete no-fit polygon, a simple structure for the 2-D irregular packing problem

被引：7
作者：
Zhang, De-Fu [1 ,2 ]
Chen, Jing-Chi [1 ]
Liu, Yong-Kai [1 ]
Chen, Huo-Wang [2 ,3 ]
机构：
[1] Department of Computer Science, Xiamen University
[2] Longtop Group Post-Doctoral Research Center
[3] School of Computer, National University of Defense Technology
来源：
Ruan Jian Xue Bao/Journal of Software | 2009年 / 20卷 / 06期
关键词：
Discrete no-fit polygon; Infeasible interval; Irregular packing problem; No-fit polygon;
D O I：
10.3724/SP.J.1001.2009.03331
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
This paper presents a model based on discrete no-fit polygon for the two-dimensional irregular packing problem. Burke et al. have presented an effective BLF algorithm to solve the irregular packing problem, however, their algorithm might generate invalid results for some special cases. To solve this problem, a model based on discrete no-fit polygon is proposed, and its correctness has been strictly proved. Only points and intervals are only considered by this model, which greatly decreases the geometry complexity of the original problem and makes the problem easily solved by many heuristic strategies. Computational results show that the algorithm based on discrete no-fit polygon model is very efficient. © by Institute of Software, the Chinese Academy of Sciences. All rights reserved.
引用
收藏
页码：1511 / 1520
页数：9
相关论文
共 16 条
  • [11] Gomes A.M., Oliveira J.F., Solving irregular strip packing problems by hybridising simulated annealing and linear programming, European Journal of Operational Research, 171, 3, pp. 811-829, (2006)
  • [12] Liu H.Y., He Y.J., Algorithm for 2-D irregular-shaped nesting problem based on the NFP algorithm and lowest-gravity-center princlple, Journal of Zhejiang University-Science A, 7, 4, pp. 570-576, (2006)
  • [13] Bennell J.A., Song X., A comprehensive and robust procedure for obtaining the nofit polygon using Minkowski sums, Computers and Operations Research, 35, pp. 267-281, (2008)
  • [14] Egeblad J., Nielsen B.K., Odgaard A., Fast neighborhood search for two- and three-dimensional nesting problems, European Journal of Operational Research, 183, 3, pp. 1249-1266, (2007)
  • [15] Burke E., Hellier R., Kendall G., Whitwell G., A new bottom-left-fill heuristic algorithm for the two-dimensional irregular packing problem, Operations Research, 54, 3, pp. 587-601, (2006)
  • [16] Burke E., Hellier R., Kendall G., Whitwell G., Complete and robust no-fit polygon generation for the irregular stock cutting problem, European Journal of Operational Research, 179, 1, pp. 27-49, (2007)
12