Mathematical Biosciences and Engineering | |
Optimized packing multidimensional hyperspheres: a unified approach | |
Tatiana Romanova1  Yuriy Stoyan1  Georgiy Yaskov2  Sergey Yakovlev3  Igor Litvinchev4  José Manuel Velarde Cantú5  | |
[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