Optimization of two-dimensional irregular bin packing problem considering slit distance and free rotation of pieces

Wang, Z.; Chang, D.; Man, X.

Growing Science » International Journal of Industrial Engineering Computations » Optimization of two-dimensional irregular bin packing problem considering slit distance and free rotation of pieces

Journals

IJIEC Volumes

Volume 1 (17)
- Issue 1 (9)
- Issue 2 (8)

Volume 2 (68)
- Issue 1 (12)
- Issue 2 (20)
- Issue 3 (20)
- Issue 4 (16)

Volume 3 (76)
- Issue 1 (9)
- Issue 2 (15)
- Issue 3 (20)
- Issue 4 (12)
- Issue 5 (20)

Volume 4 (50)
- Issue 1 (14)
- Issue 2 (10)
- Issue 3 (12)
- Issue 4 (14)

Volume 5 (47)
- Issue 1 (13)
- Issue 2 (12)
- Issue 3 (12)
- Issue 4 (10)

Volume 6 (39)
- Issue 1 (7)
- Issue 2 (12)
- Issue 3 (10)
- Issue 4 (10)

Volume 7 (47)
- Issue 1 (10)
- Issue 2 (14)
- Issue 3 (10)
- Issue 4 (13)

Volume 8 (30)
- Issue 1 (9)
- Issue 2 (7)
- Issue 3 (8)
- Issue 4 (6)

Volume 9 (32)
- Issue 1 (9)
- Issue 2 (6)
- Issue 3 (7)
- Issue 4 (10)

Volume 10 (34)
- Issue 1 (8)
- Issue 2 (10)
- Issue 3 (8)
- Issue 4 (8)

Volume 11 (36)
- Issue 1 (9)
- Issue 2 (8)
- Issue 3 (9)
- Issue 4 (10)

Volume 12 (29)
- Issue 1 (9)
- Issue 2 (6)
- Issue 3 (8)
- Issue 4 (6)

Volume 13 (41)
- Issue 1 (10)
- Issue 2 (8)
- Issue 3 (10)
- Issue 4 (13)

Volume 14 (50)
- Issue 1 (11)
- Issue 2 (15)
- Issue 3 (9)
- Issue 4 (15)

Volume 15 (55)
- Issue 1 (19)
- Issue 2 (15)
- Issue 3 (12)
- Issue 4 (9)

Volume 16 (12)
- Issue 1 (12)

Countries

International Journal of Industrial Engineering Computations

ISSN 1923-2934 (Online) - ISSN 1923-2926 (Print) Quarterly Publication Volume 13 Issue 4 pp. 491-506 , 2022

Optimization of two-dimensional irregular bin packing problem considering slit distance and free rotation of pieces Pages 491-506 Download PDF

Authors: Zi Wang, Daofang Chang, Xingyu Man

DOI: 10.5267/j.ijiec.2022.8.001

Keywords: 2DIBPP, Slit distance, Free rotation, Equidistant edge expansion approach, Overlap minimization method, LS algorithm

Abstract: In this paper, we present a two-dimensional irregular bin packing problem (2DIBPP) that takes into account the slit distance and allows the pieces to rotate freely. The target is to arrange a specified collection of pieces with irregular shapes into a minimal number of bins. Firstly, we develop a mathematical model for the 2DIBPP that considers slit distance and free rotation of the pieces, and an equidistant edge expansion approach is then proposed to handle the slit distance. Secondly, a two-stage method is implemented to get a finite collection of promising rotation angles, effectively decreasing the search neighbourhood. Thirdly, we decompose the 2DIBPP into two sub-problems: piece assignment and packing. The Partial Bin Packing (PBP) strategy is employed in the allocation stage, and we adopt an overlap minimization method to pack the pieces into an individual bin. Finally, we use a local search (LS) algorithm to advance the quality of the solutions by adjusting the piece assignment across bins. Experimental evidence exhibits that our approach is competitive in most instances of the literature, with four better results in five benchmark instances.

How to cite this paper

 Wang, Z., Chang, D & Man, X. (2022). Optimization of two-dimensional irregular bin packing problem considering slit distance and free rotation of pieces.International Journal of Industrial Engineering Computations , 13(4), 491-506.

Refrences

Abeysooriya, R. P., Bennell, J. A., & Martinez-Sykora, A. (2018). Jostle heuristics for the 2D-irregular shapes bin packing problems with free rotation. International Journal of Production Economics, 195, 12-26.
Alvarez-Valdes, R., Martinez, A., & Tamarit, J. M. (2013). A branch & bound algorithm for cutting and packing irregularly shaped pieces. International Journal of Production Economics, 145(2), 463-477.
Anand, K. V., & Babu, A. R. (2015). Heuristic and genetic approach for nesting of two-dimensional rectangular shaped parts with common cutting edge concept for laser cutting and profile blanking processes. Computers & Industrial Engineering, 80, 111-124.
Bennell, J. A., Cabo, M., & Martinez-Sykora, A. (2018). A beam search approach to solve the convex irregular bin packing problem with guillotine cuts. European Journal of Operational Research, 270(1), 89-102.
Bennell, J. A., & Oliveira, J. F. (2009). A tutorial in irregular shape packing problems. Journal of the Operational Research Society, 60(sup1), S93-S105.
Boggs, P. T., & Byrd, R. H. (2019). Adaptive, limited-memory BFGS algorithms for unconstrained optimization. SIAM Journal on Optimization, 29(2), 1282-1299.
Burke, E., Hellier, R., Kendall, G., & Whitwell, G. (2006). A new bottom-left-fill heuristic algorithm for the two-dimensional irregular packing problem. Operations Research, 54(3), 587-601.
Cherri, L. H., Mundim, L. R., Andretta, M., Toledo, F. M., Oliveira, J. F., & Carravilla, M. A. (2016). Robust mixed-integer linear programming models for the irregular strip packing problem. European Journal of Operational Research, 253(3), 570-583.
Elkeran, A. (2013). A new approach for sheet nesting problem using guided cuckoo search and pairwise clustering. European Journal of Operational Research, 231(3), 757-769.
Han, W., Bennell, J. A., Zhao, X., & Song, X. (2013). Construction heuristics for two-dimensional irregular shape bin packing with guillotine constraints. European Journal of Operational Research, 230(3), 495-504.
Hansen, A., & Arbab, F. (1992). An algorithm for generating NC tool paths for arbitrarily shaped pockets with islands. ACM Transactions on Graphics, 11(2), 152-182.
Jakobs, S. (1996). On genetic algorithms for the packing of polygons. European Journal of Operational Research, 88(1), 165-181.
Kang, J., & Park, S. (2003). Algorithms for the variable sized bin packing problem. European Journal of Operational Research, 147(2), 365-372.
Leao, A. A., Toledo, F. M., Oliveira, J. F., & Carravilla, M. A. (2016). A semi-continuous MIP model for the irregular strip packing problem. International Journal of Production Research, 54(3), 712-721.
Leao, A. A., Toledo, F. M., Oliveira, J. F., Carravilla, M. A., & Alvarez-Valdés, R. (2020). Irregular packing problems: A review of mathematical models. European Journal of Operational Research, 282(3), 803-822.
Leung, S. C., Lin, Y., & Zhang, D. (2012). Extended local search algorithm based on nonlinear programming for two-dimensional irregular strip packing problem. Computers & Operations Research, 39(3), 678-686.
Liu, Q., Zeng, J., Zhang, H., & Wei, L. (2020, September). A heuristic for the two-dimensional irregular bin packing problem with limited rotations. In International Conference on Industrial, Engineering and Other Applications of Applied Intelligent Systems (pp. 268-279). Springer, Cham.
López-Camacho, E., Ochoa, G., Terashima-Marín, H., & Burke, E. K. (2013). An effective heuristic for the two-dimensional irregular bin packing problem. Annals of Operations Research, 206(1), 241-264.
Martinez-Sykora, A., Alvarez-Valdés, R., Bennell, J. A., Ruiz, R., & Tamarit, J. M. (2017). Matheuristics for the irregular bin packing problem with free rotations. European Journal of Operational Research, 258(2), 440-455.
Parreño, F., Alvarez-Valdés, R., Oliveira, J. F., & Tamarit, J. M. (2010). A hybrid GRASP/VND algorithm for two-and three-dimensional bin packing. Annals of Operations Research, 179(1), 203-220.
Pinheiro, P. R., Amaro Júnior, B., & Saraiva, R. D. (2016). A random-key genetic algorithm for solving the nesting problem. International Journal of Computer Integrated Manufacturing, 29(11), 1159-1165.
Quader, M. A., Ahmed, S., Dawal, S. Z., & Nukman, Y. (2016). Present needs, recent progress and future trends of energy-efficient Ultra-Low Carbon Dioxide (CO2) Steelmaking (ULCOS) program. Renewable and Sustainable Energy Reviews, 55, 537-549.
Rodrigues, M. O., & Toledo, F. M. (2017). A clique covering MIP model for the irregular strip packing problem. Computers & Operations Research, 87, 221-234.
Sato, A. K., Martins, T. C., Gomes, A. M., & Tsuzuki, M. S. G. (2019). Raster penetration map applied to the irregular packing problem. European Journal of Operational Research, 279(2), 657-671.
Umetani, S., & Murakami, S. (2022). Coordinate descent heuristics for the irregular strip packing problem of rasterized shapes. European Journal of Operational Research.
Zhang, H., Liu, Q., Wei, L., Zeng, J., Leng, J., & Yan, D. (2022). An iteratively doubling local search for the two-dimensional irregular bin packing problem with limited rotations. Computers & Operations Research, 137, 105550.