A hybrid approach of simulation and metaheuristic for the polyhedra packing problem

Abstract: This document presents a simulation-based method for the polyhedra packing problem (PPP). This problem refers to packing a set of irregular polyhedra (convex and concave) into a cuboid with the objective of minimizing the cuboid’s volume, considering non-overlapping and containment constraints. The PPP has applications in additive manufacturing and packing situations where volume is at a premium. The proposed approach uses Unity® as the simulation environment and considers nine intensification and two diversification movements. The intensification movements induce the items within the cuboid to form packing patterns allowing the cuboid to decrease its size with the help of gravity-like accelerations. On the other hand, the diversification movements are classic transition operators such as removal and filling of pieces and enlargement of the container, which allow searching on different solution neighborhoods. All simulated movements were hybridized with a probabilistic tabu search. The proposed methodology (with and without the hybridization) was compared by benchmarking with all previous works solving the PPP with irregular items. Results show that satisfactory solutions were reached in a short time; even a few published results were improved.

How to cite this paper

 Pantoja-Benavides, G & Álvarez-Martínez, D. (2022). A hybrid approach of simulation and metaheuristic for the polyhedra packing problem.International Journal of Industrial Engineering Computations , 13(1), 81-100.

Refrences

Allen, S. D., Burke, E. K., & Kendall, G. (2011). A hybrid placement strategy for the three-dimensional strip packing problem. European Journal of Operational Research, 209(3), 219-227.
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.
Alvarez-Valdés, R., Parreño, F., & Tamarit, J. M. (2008). Reactive GRASP for the strip-packing problem. Computers & Operations Research, 35(4), 1065-1083.
Araújo, L. J., Özcan, E., Atkin, J. A., & Baumers, M. (2019). Analysis of irregular three-dimensional packing problems in additive manufacturing: a new taxonomy and dataset. International Journal of Production Research, 57(18), 5920-5934.
Araújo, L. J., Panesar, A., Özcan, E., Atkin, J., Baumers, M., & Ashcroft, I. (2020). An experimental analysis of deepest bottom-left-fill packing methods for additive manufacturing. International Journal of Production Research, 58(22), 6917-6933.
Barber, C. B., Dobkin, D. P., & Huhdanpaa, H. (1996). The quickhull algorithm for convex hulls. ACM Transactions on Mathematical Software (TOMS), 22(4), 469-483.
Bennell, J. A., & Oliveira, J. F. (2008). The geometry of nesting problems: A tutorial. European Journal of Operational Research, 184(2), 397-415.
Bortfeldt, A. (2006). A genetic algorithm for the two-dimensional strip packing problem with rectangular pieces. European Journal of Operational Research, 172(3), 814-837.
Bortfeldt, A., & Mack, D. (2007). A heuristic for the three-dimensional strip packing problem. European Journal of Operational Research, 183(3), 1267-1279.
Chazelle, B., Edelsbrunner, H., & Guibas, L. J. (1989). The complexity of cutting complexes. Discrete & Computational Geometry, 4(2), 139-181.
Chernov, N., Stoyan, Y., & Romanova, T. (2010). Mathematical model and efficient algorithms for object packing problem. Computational Geometry, 43(5), 535-553.
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.
Chica, M., Juan Pérez, A. A., Cordon, O., & Kelton, D. (2017). Why simheuristics? Benefits, limitations, and best practices when combining metaheuristics with simulation. Benefits, Limitations, and Best Practices When Combining Metaheuristics with Simulation (January 1, 2017). doi: 10.2139/ssrn.2919208.
Dyckhoff, H. (1990). A typology of cutting and packing problems. European Journal of Operational Research, 44(2), 145-159.
Egeblad, J., Garavelli, C., Lisi, S., & Pisinger, D. (2010). Heuristics for container loading of furniture. European Journal of Operational Research, 200(3), 881-892.
Egeblad, J., Nielsen, B. K., & Brazil, M. (2009). Translational packing of arbitrary polytopes. Computational Geometry, 42(4), 269-288.
Egeblad, J., Nielsen, B. K., & Odgaard, A. (2007). Fast neighborhood search for two-and three-dimensional nesting problems. European Journal of Operational Research, 183(3), 1249-1266.
Fischer, K., Gärtner, B., & Kutz, M. (2003, September). Fast smallest-enclosing-ball computation in high dimensions. In European Symposium on Algorithms (pp. 630-641). Springer, Berlin, Heidelberg.
Gebhardt, A., & Hötter, J. S. (2016). Additive manufacturing: 3D printing for prototyping and manufacturing. Carl Hanser Verlag GmbH Co KG.
Gendreau, M., & Potvin, J. Y. (Eds.). (2010). Handbook of metaheuristics (Vol. 2, p. 9). New York: Springer.
Gogate, A. S., & Pande, S. S. (2008). Intelligent layout planning for rapid prototyping. International Journal of Production Research, 46(20), 5607-5631.
Gomes, A. M., & Oliveira, J. F. (2006). Solving irregular strip packing problems by hybridising simulated annealing and linear programming. European Journal of Operational Research, 171(3), 811-829.
Hague*, R., Mansour, S., & Saleh, N. (2004). Material and design considerations for rapid manufacturing. International Journal of Production Research, 42(22), 4691-4708.
LaValle, S. M. (2006). Planning algorithms. Cambridge university press.
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, X., Liu, J. M., & Cao, A. X. (2015). HAPE3D—a new constructive algorithm for the 3D irregular packing problem. Frontiers of Information Technology & Electronic Engineering, 16(5), 380-390.
Liu, X., & Ye, J. W. (2011). Heuristic algorithm based on the principle of minimum total potential energy (HAPE): a new algorithm for nesting problems. Journal of Zhejiang University-SCIENCE A, 12(11), 860-872.
Lucas, T. W., Kelton, W. D., Sanchez, P. J., Sanchez, S. M., & Anderson, B. L. (2015). Changing the paradigm: Simulation, now a method of first resort. Naval Research Logistics (NRL), 62(4), 293-303.
Ma, Y., Chen, Z., Hu, W., & Wang, W. (2018, August). Packing irregular objects in 3D space via hybrid optimization. In Computer Graphics Forum (Vol. 37, No. 5, pp. 49-59).
Martello, S., Monaci, M., & Vigo, D. (2003). An exact approach to the strip-packing problem. INFORMS Journal on Computing, 15(3), 310-319.
Martínez, D. A., Alvarez-Valdes, R., & Parreño, F. (2015). A grasp algorithm for the container loading problem with multi-drop constraints. Pesquisa Operacional, 35, 1-24.
Martínez-Franco, J. C., & Álvarez-Martínez, D. (2018, December). Physx as a middleware for dynamic simulations in the container loading problem. In 2018 Winter Simulation Conference (WSC) (pp. 2933-2940). IEEE.
Martínez, J. C., Cuellar, D., & Álvarez-Martínez, D. (2018). Review of Dynamic Stability Metrics and a Mechanical Model Integrated with Open Source Tools for the Container Loading Problem. Electronic Notes in Discrete Mathematics, 69, 325-332.
Martínez, J. C., Cuellar, D., Céspedes, E., & Martínez, D. (2018). Packagecargo-open source tool based on optimization and simulation for the container loading problem with dynamic stability. In 2018 International Conference on Industrial Engineering and Operations Management (pp. 2363-2370).
Milenkovic, V. J., & Daniels, K. (1999). Translational polygon containment and minimal enclosure using mathematical programming. International Transactions in Operational Research, 6(5), 525-554.
Romanova, T., Bennell, J., Stoyan, Y., & Pankratov, A. (2018). Packing of concave polyhedra with continuous rotations using nonlinear optimisation. European Journal of Operational Research, 268(1), 37-53.
Stoyan, Y., Pankratov, A., & Romanova, T. (2016). Quasi-phi-functions and optimal packing of ellipses. Journal of Global Optimization, 65(2), 283-307.
Stoyan, Y., Gil, M., Romanova, T., Ternoy, J., & Scheithauer, G. (2002). Construction of a-function for two convex polytopes. Applicationes Mathematicae, 29(2), 199-218.
Stoyan, Y. G., Gil, M., Pankratov, A., & Scheithauer, G. (2004). Packing non-convex polytopes into a parallelepiped. Preprint MATH-NM-06-2004: Technische Universität of Dresden.
Stoyan, Y. G., Gil, N. I., Scheithauer, G., Pankratov, A., & Magdalina, I. (2005). Packing of convex polytopes into a parallelepiped. Optimization, 54(2), 215-235.
Talbi, E. G. (2009). Metaheuristics: from design to implementation (Vol. 74). John Wiley & Sons.
Wäscher, G., Haußner, H., & Schumann, H. (2007). An improved typology of cutting and packing problems. European journal of operational research, 183(3), 1109-1130.
Wei, L., Oon, W. C., Zhu, W., & Lim, A. (2012). A reference length approach for the 3D strip packing problem. European Journal of Operational Research, 220(1), 37-47.
Wong, K.V., & Hernandez, A. (2012). A review of additive manufacturing. ISRN Mechanical Engineering, 1.
Zhang, C., & Chen, T. (2001). Efficient feature extraction for 2d/3d objects in mesh representation. In Proceedings 2001 International Conference on Image Processing (Cat. No. 01CH37205), Vol. 3, IEEE, pp. 935–938.