ОПТИМАЛЬНЕ КЛАСТЕРИЗУВАННЯ ПОЛІЕДРІВ
Ключові слова:
МІНІМАЛЬНЄ ВКЛЮЧЕННЯ, КЛАСТЕРИЗАЦИЯ БАГАТОГРАННИКІВ, МАТЕМАТИЧНЕ МОДЕЛЮВАННЯАнотація
Задачі упаковки і розкрою мають широкий спектр застосування. При розміщенні багатогранників важливою задачею є знаходження оптимальної кластеризації двох об’єктів. У статті розглядається контейнер (кубоід, куля, циліндр) зі змінними метричними характеристиками та два багатогранника, які допускають безперервні трансляції та обертання. Враховуються обмеження на мінімально допустимі відстані між об’єктами і між кожним об’єктом і границею області. Об’єкти повинні бути розташовані в контейнері таким чином, щоб задана функція мети досягала мінімального значення. як функція мети розглядається об’єм або метричні характеристики контейнера. функція мети залежить від змінних параметрів, залежних від об’єктів і типу контейнера. У статті представлена математична модель у вигляді задачі нелінійної оптимізації яка заснована на методі phi-функцій. Запропоновано алгоритм розв’язання та наведено нові результати пошуку контейнеру мінімального об’єму або з мінімальним коефіцієнтом гомотетії.
Посилання
Bennell, J., Scheithauer, G., Stoyan, Y., Romanova, T.: Tools of mathematical modeling of arbitrary object packing problems. Annals of OR, 179:343-368 (2008)
Chernov,N., Stoyan, Yu., Romanova,T.: Mathematical model and efficient algorithms for object packing problem. Comput. Geometry: Theory & Appl. 43, 535-553 (2010)
Stoyan, Y., Pankratov, A., Romanova, T.: Quasi-phi- functions and optimal packing of ellipses. J. of Glob. Optim. (2015) DOI: 10.1007/s10898-015-0331-2
Birgin, E.G., Martinez, J.M., Nishihara, F.H., Ronconi, D.P.: Orthogonal packing of rectagular items within arbitrary convex regions by nonlinear optimization. Comput. Oper. Res. 33: 3535–3548 (2006).
Birgin, E., Martínez, J., Ronconi, D.: Optimizing the packing of cylinders into a rectangular containing region: A nonlinear approach. Eur. J. of Oper. Res. 160 (1), 19–33 (2005).
Egeblad, J., Nielsen, B.K., Brazil, M.: Translational packing of arbitrary polyhedra. Comp. Geom. 42(4), 269–288 (2009).
Fasano, G. A.: Global Optimization point of view for non-standard packing problems. J. Glob. Optim. 55(2), 279–299 (2013).
Petrov, M.S., Gaidukov,V.V.,Kadushnikov, R.M.: Numerical method for modelling the microstructure of granular materials. Powder Metall. and Metal Ceram. 43 (7-8), 330–335, (2004).
Torquato, S., Jiao, Y.: Dense polyhedral packings: Platonic and Archimedean solids. Phys. Rev. 80, 041104, (2009).
Y. Stoyan, N. Gil, G. Scheithauer, A. Pankratov, I Magdalina, Packing of convex polyhedra into a parallelepiped // Optimization. –2005. – Vol. 54, No. 2. – P. 215 – 235
Xiao Liu, Jia-min Liu, Anxi Cao, Zhuangle Yao, 2015. HAPE3D – a new constructive algorithm for the 3D irregular packing problem. Frontiers of Information Technology & Electronic Engineering. 16(5), 380–390
Pasha, A.: Geometric bin packing algorithm for arbitrary shapes. Master thesis (2008)
Vivek, A., Dobowsky, S.: Application of a Model-free Algorithm for the Packing of Irregular Shaped Objects in Semiconductor Manufacture. IEEE International Conference on Robotics and Automation. 2: 1545-1550 · (2000)
Vanek, J., Garcia Galicia, J. A., Benes, B., Mech, R., Carr, N., Stava, O., Miller, G. S.: PackMerger: A 3D Print Volume Optimizer. Computer graphics forum. 00: 1–11 (2014)
Kreher D. L., Stinson D. R.: Combinatorial Algorithms: Generation, Enumeration, and Search. CRC Press, Florida, 1998
Adamowicz, M., Albano, A.: Nesting two-dimensional shapes in rectanglular modules. Computer Aided Design. 8, 1, 27-33 (1976)
Belov, Gleb, 2002. A Modified Algorithm for Convex Decomposition of3D Polyhedra,” Technical report MATH- NM-03-2002, Institut für Numerische Mathematik, Technische Universität, Dresden, http://www.math.tudresden.de/belov/cd3/ cd3.ps
Stoyan, Y.G., Gil, N.I., Pankratov, A., et al., 2004. Packing Non-convex Polyhedra into a Parallelepiped. Technische Universitat Dresden http://www.math.tu-dresden. de/scheith/ABSTRACTS/PREPRINTS/04-non-conv.pdf
Wachter, A., Biegler, L.T.: On the implementation of an interior-point filter line-search algorithm for large-scale non- linear programming. Math. Program. 106 (1), 25–57, (2006).
