DOI: https://doi.org/10.20998/2522-9052.2019.1.09

Методологічні основи розв’язання задачі упаковки куль: перетворення задачі про рюкзак у задачу зі змінним розміром

Georgiy Yaskov, Sergiy Shekhovtsov

Анотація


Предметом статті є задача оптимальної упаковки куль різної розмірності в контейнер довільної геометричної форми. Мета полягає в тому, щоб побудувати математичну модель, в якій зв'язуються різні формулювання задачі. Задача упаковки куль (SPP) є задачею комбінаторної оптимізації, відомою як задача розкрою й упаковки. SPP полягає в розміщенні заданого набору куль із заданими радіусами в контейнері правильної або неправильної геометричної форми. Задача, яку необхідно вирішити, полягає в тому, щоб: дослідити математичні моделі двох постановок відповідно до класифікації задач розкрою й упаковки: задачі про рюкзак (KP) та задачі зі змінним розміром (ODP); побудувати математичну модель, яка дозволяє розв’язати задачу KP як задачу ODP. Використовувані методи: метод phi-функцій, збільшення розмірності задачі, гомотетичні перетворення. Задача KP формулюється як змішана задача дискретно-неперервного програмування. Пропонується новий підхід, в якому розв’язання задачі KP зводиться до розв’язання задачі ODP для упаковки нерівних і рівних куль у контейнері зі змінним коефіцієнтом гомотетії й який дозволяє використовувати jump-алгоритм для задачі KP. З цією метою задача KP для даного набору куль представляється у вигляді задачі нелінійного програмування, в якій коефіцієнт гомотетії розглядається в якості незалежної змінної, обмеженою знизу. Коефіцієнт гомотетії, який дорівнює одиниці, відповідає початковому розміру контейнера. Зображена графічна ілюстрація процесу оптимізації. Висновки. Запропонований підхід є методологічною основою для розв’язання задачі SPP. Універсальність підходу полягає в тому, що розв’язання задачі не залежить від її постановки (KP або ODP). Підхід застосовний для упаковки нерівних і рівних куль у контейнерах довільних просторових форм, для яких можуть бути побудовані phi-функції.


Ключові слова


куля; гіперкуля; упаковка куль; задача про рюкзак; задача зі змінним розміром; нелінійна оптимізація

Повний текст:

PDF (English)

Посилання


Hifi, M. and M'Hallah, R. (2009), “A literature review on circle and sphere packing problems: models and methodologies”, Advances in Operations Research, Vol. 2009, available at: http://downloads.hindawi.com/journals/aor/2009/150624.pdf DOI: https://doi.org/10.1155/2009/150624

Leary, M., Merli, L., Torti, F., Mazur, M. and Brandt, M. (2014), “Optimal topology for additive manufacture: A method for enabling additive manufacture of support-free optimal structures”, Materials and Design, Vol. 63, pp. 678–690.

Blyuss, O., Koriashkina, L., Kiseleva, E. and Molchanov, R. (2015), “Optimal Placement of Irradiation Sources in the Planning of Radiotherapy: Mathematical Models and Methods of Solving”, Computational and Mathematical Methods in Medicine, Vol. 2015, p. 8, DOI: https://doi.org/10.1155/2015/142987

Agapie, S.C. and Whitlock, P.A. (2010), “Random packing of hyperspheres and Marsaglia's parking lot test", Monte Carlo Methods and Applications, Vol. 16(3-4), pp.197–209.

Conway, J. H. and Sloane, N.J.A. (2010), Sphere Packings, Lattices, and Groups, New York, Springer-Verlag, 703 p.

Torquato, S. (2006), “Exactly solvable disordered sphere-packing model in arbitrary-dimensional Euclidean spaces”, Physical Review, vol. E 73, 031106.

Waescher, G. and Haussner, H. (2007), “An improved typology of cutting and packing problems”, European Journal of Operational Research, Vol. 183, pp. 1109–1130.

Hifi, M. and Yousef, L. (2015), “A dichotomous search-based heuristic for the three-dimensional packing problem", Cogent Engineering, Vol. 1, pp. 1–15.

Hifi, M. and Yousef, L. (2019), "A local search-based method for sphere packing problems", European Journal of Operational Research, Vol. 274, Issue 2, pp. 482-500.

Birgin, E.G. and Sobral, F.N.C. (2008), “Minimizing the object dimensions in circle and sphere packing problems” Computers & Operations Research, Vol. 35, pp. 2357–2375.

Stoyan, Yu. and Yaskov, G. (2012), "Packing congruent hyperspheres into a hypersphere", Journal of Global Optimization, Vol. 52(4), pp. 855–868.

Yakovlev, S.V., Yaskov, G.N. and Korobchinskiy, K.P. (2017), “O metodah peremennogo radiusa v zadache upakovki sharov v konteynery [About variable radius methods in problems of packing spheres into containers]”, Pytannya prikladnoyi matematyky i matematuchnogo modelyuvannya, DNU, Dnipro, Issue 17, pp. 265–272.

Stoyan, Yu.G., Scheithauer, G. and Yaskov, G.N. (2016), “Packing unequal spheres into various containers”, Cybernetics and Systems Analysis, Vol. 52(3), pp. 419–426.

Yaskov, G.N. (2014), “Packing non-equal hyperspheres into a hypersphere of minimal radius”, Problemy Mashinostroeniya, Vol. 17, No 2, pp. 48–53.

Stoyan, Yu. and Yaskov G. (2014), “Packing unequal circles into a strip of minimal length with a jump algorithm”, Optimization Letters, Vol. 8(3), pp. 949–970.

Chernov, N., Stoyan, Yu., Romanova, T. (2010), “Mathematical model and efficient algorithms for object packing problem”, Computational Geometry, Vol. 43(5), pp. 535–553.

Stoyan, Y., Pankratov, A. and Romanova, T. (2016), “Quasi-phi-functions and optimal packing of ellipses”, Journal of Global Optimization, Vol. 65(2), pp. 283–307.




Copyright (c) 2020 Georgiy Yaskov, Sergiy Shekhovtsov