Cybernetics And Systems Analysis logo
Editorial Board Announcements Abstracts Authors Archive
Cybernetics And Systems Analysis
International Theoretical Science Journal
UDC 519.85
Y.G. Stoyan1, A.M. Chugay2


1 Pidgorny Institute for Mechanical Engineering Problems
of National Academy of Sciences of Ukraine, Kyiv, Ukraine

stoyan@ipmach.kharkov.ua

2 Pidgorny Institute for Mechanical Engineering Problems
of National Academy of Sciences of Ukraine, Kyiv, Ukraine

chugay.andrey80@gmail.com

MULTISTAGE APPROACH TO SOLVING THE OPTIMIZATION PACKING PROBLEM
FOR CONCAVE POLYHEDRA

Abstract. The paper considers the problem of packing concave polyhedra into a container of minimal volume. The aim of our investigations is construction of an exact mathematical model of the packing problem of concave polyhedra with continuous translations and rotations. Characteristics of the mathematical model are analyzed and are used as the basid to develop a multistage solution approach to obtain a nearly optimal solution which is not a global minimum solution but a proved local minimum. Numerical examples are given.

Keywords: packing, concave polytopes, Ф-function, nonlinear optimization.



FULL TEXT

REFERENCES

  1. Wang Y., Lin C.L., Miller J.D. 3D image segmentation for analysis of multisize particles in a packed particle bed. Powder Technology. 2016. Vol. 301. P. 160–168.

  2. Korte A.C.J., Brouwers H.J.H. Random packing of digitized particles. Powder Technology. 2013. Vol. 233. P. 319–324.

  3. Li S.X., Zhao J., Lu P., Xie Y. Maximum packing densities of basic 3D objects. China Science Bulletin. 2010. Vol. 55, Iss. 2. P. 114–119.

  4. Karabulut K., Жnceolu M. A hybrid genetic algorithm for packing in 3D with deepest bottom left with fill method. In: Advances in Information Systems. ADVIS 2004. Lecture Notes in Computer Science. T. Yakhno (Eds.). 2004. Vol 3261. Berlin; Heidelberg: Springer, 2004. P. 441–450.

  5. Pei Cao, Zhaoyan Fan, Robert Gao, Jiong Tang. A multi-objective simulated annealing approach towards 3D packing problems with strong constraints. ASME 2015. International Design Engineering Technical Conferences and Computers and Information in Engineering Conference. Vol. 2A. Paper No DETC2015-47670, V02AT03A052; 12 p. https://doi.org/10.1115/DETC2015-47670.

  6. Guangqiang Li, Fengqiang Zhao, Rubo Zhang, Jialu Du, Chen Guo, Yiran Zhou. A parallel particle bee colony algorithm approach to layout optimization. Journal of Computational and Theoretical Nanoscience. 2016. Vol. 13, N 7. P. 4151–4157.

  7. Torczon V., Trosset M. From evolutionary operation to parallel direct search: Pattern search algorithms for numerical optimization. Computing Science and Statistics. 1998. Vol. 29. P. 396–401.

  8. Birgin E.G., Lobato R.D., Martіnez J.M. Packing ellipsoids by nonlinear optimization. Journal of Global Optimization. 2016. Vol. 65. P. 709–743.

  9. Fasano G.A. Global optimization point of view for non-standard packing problems. Journal of Global Optimization. 2013. Vol. 55. P. 279–299.

  10. Stoyan Y.G., Semkin V.V., Chugay A.M. Optimization of 3D objects layout into a multiply connected domain with account for shortest distances. Cybernetics and Systems Analysis. 2014. Vol. 50, N 3. P. 374–385.

  11. Grebennik I.V., Pankratov A.V., Chugay A.M., Baranov A.V. Packing n-dimensional parallelepipeds with the feasibility of changing their orthogonal orientation in an n-dimensional parallelepiped. Cybernetics and Systems Analysis. 2010. Vol. 46, N 5. P. 393–802.

  12. Liu X., Liu J., Cao A. HAPE3D-a new constructive algorithm for the 3D irregular packing problem. Frontiers Inf. Technol. Electronic Eng. 2015. Vol. 16. P. 380–390.

  13. Chernov N., Stoyan Y., Romanova T. Mathematical model and efficient algorithms for object packing problem. Computational Geometry. Theory and Application. 2010. Vol. 43, Iss. 5. P. 535–553.

  14. Stoyan Y., Chugay А. Mathematical modeling of the interaction of non-oriented convex polytopes. Cybernetics and Systems Analysis. 2012. Vol. 48, N 6. P. 837–845.

  15. Stoyan Y.G., Chugay A.M. Packing different cuboids with rotations and spheres into a cuboid. In: Advances in Decision Sciences, 2014. URL: https://www.hindawi.com/journals/ads/2014/571743.

  16. Stoyan Y.G., Semkin V.V., Chugay A.M. Modeling close packing of 3D objects. Cybernetics and Systems Analysis. 2016. Vol. 52, N 2. P. 296–304.

  17. Stoian Y.E., Chugay A.M., Pankratov A.V., Romanova T.E. Two approaches to modeling and solving the packing problem for convex polytopes. Cybernetics and Systems Analysis. 2018. Vol. 54, N 4. P. 585–593.

  18. Wachter A., Biegler L.T. On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Mathematical Programming. 2006. Vol. 106, Iss. 1. P. 25–57.
© 2020 Kibernetika.org. All rights reserved.