УПАКОВКА МНОГОГРАННИКОВ В ВЫПУКЛЫЙ КОНТЕЙНЕР МИНИМАЛЬНОГО ОБЪЕМА

Yu. E. Stoyan; A. V. Pankratov; Т. Ye. Romanova

doi:10.26906/SUNZ.2018.2.048

Автор(и)

Yu. E. Stoyan
A. V. Pankratov
Т. Ye. Romanova

DOI:

https://doi.org/10.26906/SUNZ.2018.2.048

Ключові слова:

упаковка, багатогранники, безперервне обертання, опуклий контейнер, математичне моделювання, нелінійна оптимізація

Анотація

Розглядається задача упаковки заданого набору довільних багатогранників в опуклий контейнер мінімального обсягу. Допускаються безперервні обертання і трансляції багатогранників. Враховуються мінімально допустимі відстані між многогранниками і обмеження балансу. Побудовано математичну модель у вигляді задачі нелінійного програмування з використанням phi-функцій і квазі phi-функцій. Запропоновано ефективний метод рішення, який включає в себе швидкий алгоритм пошуку допустимої стартової точки і процедуру локальної оптимізації. Перевага запропонованого методу підтверджується результатами численних експериментів.

Завантаження

Дані завантаження ще не доступні.

Посилання

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.