УПАКОВКА БАГАТОГРАННИКІВ В ОПУКЛИЙ КОНТЕЙНЕР МІНІМАЛЬНОГО ОБСЯГУ
Ключові слова:
упаковка, багатогранники, безперервне обертання, опуклий контейнер, математичне моделювання, нелінійна оптимізація
Анотація
Розглядається задача упаковки заданого набору довільних багатогранників в опуклий контейнер мінімального обсягу. Допускаються безперервні обертання і трансляції багатогранників. Враховуються мінімально допустимі відстані між многогранниками і обмеження балансу. Побудовано математичну модель у вигляді задачі нелінійного програмування з використанням phi-функцій і квазі phi-функцій. Запропоновано ефективний метод рішення, який включає в себе швидкий алгоритм пошуку допустимої стартової точки і процедуру локальної оптимізації. Перевага запропонованого методу підтверджується результатами численних експериментів.Завантаження
Дані про завантаження поки що недоступні.
Посилання
1. Bennell, J., Oliveira, J. (2008). The geometry of packing problems:A tutorial.European Journal of Operational packing problems:A tutorial.European Journal of Operational Research184:397–415.
2. Gomes, A. Miguel Irregular Packing Problems: Industrial Applications and New Directions Using Computational Geometry. (2014) Paper in special issue on “Cutting and Packing". Vol 11 | Part 1, 378-383. DOI: 10.3182/20130522-3-BR-4036.00113.
3. Wаscher, G., Hauner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. Eur. J. Oper. Res., 183(3), 1109–1130.
4. Chazelle, B., Edelsbrunner, H., Guibas, L. J. (1989). The complexity of cutting complexes. Discr. & Comput. Geom., 4(2), 139–181. DOI: 10.1007/BF02187720.
5. Chen, E. R., Klotsa, D., Engel, M., Damasceno, P. F., Glotzer, S. C. (2014). Complexity in surfaces of densest packings for families of polyhedra. Phys Rev X 4(1), DOI:10.1103/PhysRevX.4.011024.
6. Galrão, R. A., Oliveira J. F., Gonçalves J. F., Lopes M. P. (2016) A container loading algorithm with static mechanical equilibrium stability constraints. Transportation Research, (Part B), 91, 565-581. DOI: 10.1016/j.trb.2016.06.003.
7. Smeets, B., Odenthal, T., Vanmaercke, S., Ramon, H. (2015). Polygon-based contact description for modeling arbitrary polyhedra in the Discrete Element Method. Computer Methods in Applied Mechanics and Engineering, 290, 277-289. DOI: 10.1016/j.cma.2015.03.004.
8. Tasios, N., Gantapara, A. P., Dijkstra M. (2014). Glassy dynamics of convex polyhedra. The Journal of Chemical Physics. 141: 224502. PMID 25494755 DOI: 10.1063/1.49029922.
9. Egeblad, J., Nielsen, B. K., Brazil, M. (2009). Translational packing of arbitrary polyhedra. Comp. Geom., 42(4), 269–288. DOI:10.1016/j.comgeo.2008.06.003.
10. Fasano, G. A. (2013). Global Optimisation point of view for non-standard packing problems. J. Glob. Optim., 55(2), 279–299. DOI: 10.1007/s10898-012-9865-8.
11. Torquato, S., Jiao, Y. (2009). Dense polyhedral packings: Platonic and Archimedean solids. Phys. Rev., 80, 041104. DOI: 10.1103/PhysRevE.80.041104.
12. Chernov, N., Stoyan, Y., Romanova, T. (2010). Mathematical model and efficient algorithms for object packing problem. Comput. Geom.: Theory and Appl., 43(9), 535–553. DOI:10.1016/j.comgeo.2009.12.003.
13. Fischer, K., Gärtner, B. and Kutz, M. (2003). Fast Smallest-Enclosing-Ball Computation in High Dimensions. Algorithms - ESA 2003, 2832, 630–641. DOI:10.1007/978-3- 540-39658-1_57.
14. Stoyan, Y., Pankratov, A., Romanova, T. (2016). Quasi phi-functions and optimal packing of ellipses. J. of Glob. Optim., 65 (2), 283–307. DOI: 10.1007/s10898-015- 0331-2.
15. Wachter, A., Biegler, L. T. (2006). On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Math. Program., 106 (1), 25–57. DOI: 10.1007/s10107-004-0559-y.
16. Stoyan, Y. G., Gil, N. I., Pankratov, A. V., et al., (2004). Packing Non-convex Polyhedra into a Parallelepiped. Technische Universitat Dresden. Mode of access: http://www.math.tu-dresden.de/~scheith/ABSTRACTS/ PREPRINTS/04-non-conv.pdf
17. Romanova, T., Bennell, J., Stoyan, Y., Pankratov, A. (2018) Packing of concave polyhedra with continuous rotations using nonlinear optimization. European Journal of Operational Research 268 (1), 37-53. https://doi.org/10.1016/j.ejor.2018.01.025
18. Панкратов, А.В., Романова, Т.Е., Стоян, Ю.Е., Чугай, А.М. (2016). Задача оптимизации упаковки многогранников в сферическом и цилиндрическом контейнерах. Eastern-European J. of Entrepr. Tech., 1/4 (79), 39–47.
2. Gomes, A. Miguel Irregular Packing Problems: Industrial Applications and New Directions Using Computational Geometry. (2014) Paper in special issue on “Cutting and Packing". Vol 11 | Part 1, 378-383. DOI: 10.3182/20130522-3-BR-4036.00113.
3. Wаscher, G., Hauner, H., Schumann, H. (2007). An improved typology of cutting and packing problems. Eur. J. Oper. Res., 183(3), 1109–1130.
4. Chazelle, B., Edelsbrunner, H., Guibas, L. J. (1989). The complexity of cutting complexes. Discr. & Comput. Geom., 4(2), 139–181. DOI: 10.1007/BF02187720.
5. Chen, E. R., Klotsa, D., Engel, M., Damasceno, P. F., Glotzer, S. C. (2014). Complexity in surfaces of densest packings for families of polyhedra. Phys Rev X 4(1), DOI:10.1103/PhysRevX.4.011024.
6. Galrão, R. A., Oliveira J. F., Gonçalves J. F., Lopes M. P. (2016) A container loading algorithm with static mechanical equilibrium stability constraints. Transportation Research, (Part B), 91, 565-581. DOI: 10.1016/j.trb.2016.06.003.
7. Smeets, B., Odenthal, T., Vanmaercke, S., Ramon, H. (2015). Polygon-based contact description for modeling arbitrary polyhedra in the Discrete Element Method. Computer Methods in Applied Mechanics and Engineering, 290, 277-289. DOI: 10.1016/j.cma.2015.03.004.
8. Tasios, N., Gantapara, A. P., Dijkstra M. (2014). Glassy dynamics of convex polyhedra. The Journal of Chemical Physics. 141: 224502. PMID 25494755 DOI: 10.1063/1.49029922.
9. Egeblad, J., Nielsen, B. K., Brazil, M. (2009). Translational packing of arbitrary polyhedra. Comp. Geom., 42(4), 269–288. DOI:10.1016/j.comgeo.2008.06.003.
10. Fasano, G. A. (2013). Global Optimisation point of view for non-standard packing problems. J. Glob. Optim., 55(2), 279–299. DOI: 10.1007/s10898-012-9865-8.
11. Torquato, S., Jiao, Y. (2009). Dense polyhedral packings: Platonic and Archimedean solids. Phys. Rev., 80, 041104. DOI: 10.1103/PhysRevE.80.041104.
12. Chernov, N., Stoyan, Y., Romanova, T. (2010). Mathematical model and efficient algorithms for object packing problem. Comput. Geom.: Theory and Appl., 43(9), 535–553. DOI:10.1016/j.comgeo.2009.12.003.
13. Fischer, K., Gärtner, B. and Kutz, M. (2003). Fast Smallest-Enclosing-Ball Computation in High Dimensions. Algorithms - ESA 2003, 2832, 630–641. DOI:10.1007/978-3- 540-39658-1_57.
14. Stoyan, Y., Pankratov, A., Romanova, T. (2016). Quasi phi-functions and optimal packing of ellipses. J. of Glob. Optim., 65 (2), 283–307. DOI: 10.1007/s10898-015- 0331-2.
15. Wachter, A., Biegler, L. T. (2006). On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Math. Program., 106 (1), 25–57. DOI: 10.1007/s10107-004-0559-y.
16. Stoyan, Y. G., Gil, N. I., Pankratov, A. V., et al., (2004). Packing Non-convex Polyhedra into a Parallelepiped. Technische Universitat Dresden. Mode of access: http://www.math.tu-dresden.de/~scheith/ABSTRACTS/ PREPRINTS/04-non-conv.pdf
17. Romanova, T., Bennell, J., Stoyan, Y., Pankratov, A. (2018) Packing of concave polyhedra with continuous rotations using nonlinear optimization. European Journal of Operational Research 268 (1), 37-53. https://doi.org/10.1016/j.ejor.2018.01.025
18. Панкратов, А.В., Романова, Т.Е., Стоян, Ю.Е., Чугай, А.М. (2016). Задача оптимизации упаковки многогранников в сферическом и цилиндрическом контейнерах. Eastern-European J. of Entrepr. Tech., 1/4 (79), 39–47.
Опубліковано
2018-04-11
Як цитувати
Stoyan Yu.E. Упаковка багатогранників в опуклий контейнер мінімального обсягу / Yu.E. Stoyan, A.V. Pankratov, RomanovaТ.Ye. // Системи управління, навігації та зв’язку. Збірник наукових праць. – Полтава: ПНТУ, 2018. – Т. 2 (48). – С. 48-54. – doi:https://doi.org/10.26906/SUNZ.2018.2.048.
Розділ
Математичні моделі та методи
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
