Optimized packing multidimensional hyperspheres: a unified approach

Mathematical Biosciences and Engineering

Tatiana Romanova¹  Yuriy Stoyan¹  Georgiy Yaskov²  Sergey Yakovlev³  Igor Litvinchev⁴  José Manuel Velarde Cantú⁵ 

[1] 1. Institute for Mechanical Engineering Problems of the National Academy of Sciences of Ukraine, 2/10 Pozharskogo st., Kharkiv 61046, Ukraine 2. Kharkiv National University of Radioelectronics, 14 Nauky ave., Kharkiv 61166, Ukraine;1. Institute for Mechanical Engineering Problems of the National Academy of Sciences of Ukraine, 2/10 Pozharskogo st., Kharkiv 61046, Ukraine3. Kharkiv Aviation Institute, National Aerospace University, 17 Chkalov st., Kharkiv 61070, Ukraine;3. Kharkiv Aviation Institute, National Aerospace University, 17 Chkalov st., Kharkiv 61070, Ukraine;4. Computing Center, Russian Academy of Sciences, Vavilov 40, Moscow, Russia 5. Nuevo Leon State University, Monterrey, Nuevo Leon, CP 66455, Mexico;6. Technological Institute of Sonora (ITSON), Obregón-City, Sonora, Mexico;

关键词: packing;    hypersphere;    phi-function;    mathematical modeling;    optimization;    open dimension problem;    knapsack problem;   

DOI  :  10.3934/mbe.2020344

来源: DOAJ

【 摘 要 】

In this paper an optimized multidimensional hyperspheres packing problem (HPP) is considered for a bounded container. Additional constraints, such as prohibited zones in the container or minimal allowable distances between spheres can also be taken into account. Containers bounded by hyper- (spheres, cylinders, planes) are considered. Placement constraints (non-intersection, containment and distant conditions) are formulated using the phi-function technique. A mathematical model of HPP is constructed and analyzed. In terms of the general typology for cutting & packing problems, two classes of HPP are considered: open dimension problem (ODP) and knapsack problem (KP). Various solution strategies for HPP are considered depending on: a) objective function type, b) problem dimension, c) metric characteristics of hyperspheres (congruence, radii distribution and values), d) container's shape; e) prohibited zones in the container and/or minimal allowable distances. A solution approach is proposed based on multistart strategies, nonlinear programming techniques, greedy and branch-and-bound algorithms, statistical optimization and homothetic transformations, as well as decomposition techniques. A general methodology to solve HPP is suggested. Computational results for benchmark and new instances are presented.

【 授权许可】

Unknown