PACKAGING POLYHEDRONS INTO A CONVENIENT CONTAINER OF MINIMUM VOLUME
DOI:
https://doi.org/10.26906/SUNZ.2018.2.048Keywords:
packing, polyhedron, continuous rotation, convex container, mathematical modeling, nonlinear optimizationAbstract
The problem of packing a given set of arbitrary polyhedron into a convex container of minimal volume is considered. Continuous rotations and translations of polyhedron are allowed. Minimum distances between polyhedron and balance constraints are taken into account. A mathematical model is constructed in the form of a non-linear programming problem using phifunctions and quasi-phi-functions. An effective method of solution is proposed that includes a fast algorithm for finding an acceptable starting point and a procedure for local optimization. The advantage of the proposed method is confirmed by the results of numerical experiments.Downloads
References
Bennell, J., Oliveira, J. (2008). The geometry of packing problems:A tutorial.European Journal of Operational packing problems:A tutorial.European Journal of Operational Research184:397–415.
Gomes, A. Miguel Irregular Packing Problems: Industrial Applications and New Directions Using Computational Geometry. (2014) Paper in special issue on “Cutting and Packing". Vol 11 | Part 1, 378-383. DOI: 10.3182/20130522-3-BR-4036.00113.
Wаscher, G., Hauner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. Eur. J. Oper. Res., 183(3), 1109–1130.
Chazelle, B., Edelsbrunner, H., Guibas, L. J. (1989). The complexity of cutting complexes. Discr. & Comput. Geom., 4(2), 139–181. DOI: 10.1007/BF02187720.
Chen, E. R., Klotsa, D., Engel, M., Damasceno, P. F., Glotzer, S. C. (2014). Complexity in surfaces of densest packings for families of polyhedra. Phys Rev X 4(1), DOI:10.1103/PhysRevX.4.011024.
Galrão, R. A., Oliveira J. F., Gonçalves J. F., Lopes M. P. (2016) A container loading algorithm with static mechanical equilibrium stability constraints. Transportation Research, (Part B), 91, 565-581. DOI: 10.1016/j.trb.2016.06.003.
Smeets, B., Odenthal, T., Vanmaercke, S., Ramon, H. (2015). Polygon-based contact description for modeling arbitrary polyhedra in the Discrete Element Method. Computer Methods in Applied Mechanics and Engineering, 290, 277-289. DOI: 10.1016/j.cma.2015.03.004.
Tasios, N., Gantapara, A. P., Dijkstra M. (2014). Glassy dynamics of convex polyhedra. The Journal of Chemical Physics. 141: 224502. PMID 25494755 DOI: 10.1063/1.49029922.
Egeblad, J., Nielsen, B. K., Brazil, M. (2009). Translational packing of arbitrary polyhedra. Comp. Geom., 42(4), 269–288. DOI:10.1016/j.comgeo.2008.06.003.
Fasano, G. A. (2013). Global Optimisation point of view for non-standard packing problems. J. Glob. Optim., 55(2), 279–299. DOI: 10.1007/s10898-012-9865-8.
Torquato, S., Jiao, Y. (2009). Dense polyhedral packings: Platonic and Archimedean solids. Phys. Rev., 80, 041104. DOI: 10.1103/PhysRevE.80.041104.
Chernov, N., Stoyan, Y., Romanova, T. (2010). Mathematical model and efficient algorithms for object packing problem. Comput. Geom.: Theory and Appl., 43(9), 535–553. DOI:10.1016/j.comgeo.2009.12.003.
Fischer, K., Gärtner, B. and Kutz, M. (2003). Fast Smallest-Enclosing-Ball Computation in High Dimensions. Algorithms - ESA 2003, 2832, 630–641. DOI:10.1007/978-3- 540-39658-1_57.
Stoyan, Y., Pankratov, A., Romanova, T. (2016). Quasi phi-functions and optimal packing of ellipses. J. of Glob. Optim., 65 (2), 283–307. DOI: 10.1007/s10898-015- 0331-2.
Wachter, A., Biegler, L. T. (2006). On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Math. Program., 106 (1), 25–57. DOI: 10.1007/s10107-004-0559-y.
Stoyan, Y. G., Gil, N. I., Pankratov, A. V., et al., (2004). Packing Non-convex Polyhedra into a Parallelepiped. Technische Universitat Dresden. Mode of access: http://www.math.tu-dresden.de/~scheith/ABSTRACTS/ PREPRINTS/04-non-conv.pdf
Romanova, T., Bennell, J., Stoyan, Y., Pankratov, A. (2018) Packing of concave polyhedra with continuous rotations using nonlinear optimization. European Journal of Operational Research 268 (1), 37-53. https://doi.org/10.1016/j.ejor.2018.01.025
Панкратов, А.В., Романова, Т.Е., Стоян, Ю.Е., Чугай, А.М. (2016). Задача оптимизации упаковки многогранников в сферическом и цилиндрическом контейнерах. Eastern-European J. of Entrepr. Tech., 1/4 (79), 39–47.
