A problem of packing of homothetic convex polytopes

1Stoyan, Yu.G, 1Chugay, AM
1A. N. Podgorny Institute for Mechanical Engineering Problems of the NAS of Ukraine, Kharkiv
Dopov. Nac. akad. nauk Ukr. 2017, 10:28-33
Section: Information Science and Cybernetics
Language: Ukrainian

On the ground of an Φ-function for two convex polytopes, a mathematical model of the problem of packing of homothetic convex polytopes into a cuboid of a minimum volume is constructed. A number of characteristics of the mathematical model are pointed out. Based on the characteristics, a way of construction of starting points, a rapid algorithm of searching for local minima, and an original approach to the directed non-exhaustive search for local extrema to obtain a good approximation to a global extremum are offered. Numerical results are given.

Keywords: homothetic polytopes, optimization, packing, rotations
  1. Wang, Y., Lin, C. L. & Miller, J. D. (2016) 3D image segmentation for analysis of multisize particles in a packed particle bed. Powder Technology. 301, pp. 160-168. https://doi.org/10.1016/j.powtec.2016.05.012
  2. Liu, X., Liu, J. & Cao, A. (2015) HAPE3D-a new constructive algorithm for the 3D irregular packing problem. Frontiers Inf. Technol. Electronic Eng., No. 16. pp. 380-390. https://doi.org/10.1631/FITEE.1400421
  3. Verkhoturov, M., Petunin, A., Verkhoturova, G., Danilov, K. & Kurennov, D. (2016) The 3D Object Packing Problem into a Parallelepiped Container Based on Discrete-Logical Representation. IFAC-PapersOnLine, 49, No. 12, pp. 001-005. https://doi.org/10.1016/j.ifacol.2016.07.540
  4. Fasano, G. & Pinter, J. (Eds.) (2015). Optimized packings with applications. New York: Springer. https://doi.org/10.1007/978-3-319-18899-7
  5. Youn-Kyoung, Joung, Sang, & Do, Noh. (2014). Intelligent 3D packing using a grouping algorithm for automotive container engineering. J. Computational Design and Engineering, 1, No. 2, pp. 140-151. https://doi.org/10.7315/JCDE.2014.014
  6. Stoyan, Yu. & Chugay, A. (2012). Mathematical modeling of the interaction of non-oriented convex polytopes. Cybern. Syst Anal.. No. 48, pp. 837-845. https://doi.org/10.1007/s10559-012-9463-2