Задачи упаковки, как определено в работе [4], состоят в расположении набора геометрических объектов фиксированных размеров и/или формы в заданной области. При этом, как правило, либо максимизируется число упаковываемых объектов при фиксированном размере, либо их размеры (площадь поверхности, объем, радиус и др.) при заданном количестве, также можно рассматривать задачу минимизации объема контейнера. В настоящей статье мы рассматриваем объекты, имеющие вид шаров.
Хотя проблема упаковки равных шаров в бесконечное пространство решена — показано, что плотнейшими упаковками являются гранецентрированная кубическая (ГЦК) и гексагональная плотная (ГП) с плотностью π/(3√ 2), однако для случая ограниченного контейнера эта проблема остается открытой [5]. Следует отметить, что в большинстве работ в качестве контейнеров выступают множества простой формы: сфера, куб, тетраэдр и др. Приведем краткий обзор известных научных результатов по данной тематике.
В работах [6, 7] рассмотрена задача упаковки одинаковых шаров заданного радиуса в параллелепипед минимальной высоты (длина и ширина известны) и в цилиндр с известным радиусом и минимальной высотой, предложена стратегия ее решения, которая включает в себя построение специального дерева поиска, модификацию метода возможных направлений для вычисления локальных минимумов и модификацию метода сужающихся окрестностей для поиска приближения к глобальному минимуму.
Для решения задачи упаковки равных шаров в [8] предложен алгоритм последовательного симметричного перемещения, представлены плотные упаковки до 200 шаров в сферу и до 150 шаров в куб. В [9] решается задача упаковки шаров в бесконечно длинный цилиндр с заданным радиусом с использованием метода имитации отжига. Проблема нахождения плотнейшей упаковки шаров в цилиндр рассматривается и в [10], где она решается с помощью адаптивно-сжимающейся ячейки и метода последовательного линейного программирования.
