Optimal packing of convex polytopes using quasi-phi-functions
Ключові слова:
упаковка, багатогранники, безперервні повороти, неперетинання, припустимі відстані, квазі-phi-функції, математична модель, нелінійна оптимізаціяАнотація
Розглядається задача упаковки опуклих багатогранників у прямокутний контейнер мінімального об’єму. При цьому багатогранники припускають безперервні повороти та трансляції. Крім того, враховуються мінімально припустимі відстані між багатогранниками. Для побудови математичної моделі задачі як задачі нелінійного програмування використовуються вільні від радикалів квазі-phi-функції. Розроблено ефективний алгоритм розв’язання, який дозволяє зменшити розмірність задачі і обчислювальні витрати. Наведено числові приклади.Посилання
Wаscher, G., Hauner, H., Schumann, H. (2007).”An improved typology of cutting and packing problems”. Eur. J. Oper. Res. 183(3,16): 1109–1130.
Chazelle, B., Edelsbrunner, H., Guibas, L.J. (1989). “The complexity of cutting complexes.” Discr. & Comput. Geom. 4(2): 139–81.
Aladahalli, C., Cagan, J., Shimada, K. (2007). “Objective function effect based pattern search – theoretical framework inspired by 3D component layout.” J. Mech. Design. 129: 243–254.
Cagan, J., Shimada, K., Yin, S. (2002). “A survey of computational approaches to three-dimensional layout problems.” Comp.-Aided Des. 34: 597–611.
Egeblad, J. (2008). “Heuristics for multidimensional packing problems.” PhD Thesis.
Egeblad, J., Nielsen, B.K., Odgaard, A. (2007). “Fast neighborhood search for two- and three-dimensional nesting problems.” Eur. J. Oper. Res. 183(3):1249–1266.
Fasano, G. (2008). “MIP-based heuristic for non-standard 3D-packing problems.” 4OR: Quart. J. Belgian, French and Italian Oper. Res. Soc. 6(3): 291–310.
Gan, M., Gopinathan, N., Jia, X., Williams, R.A. (2004). “Predicting Packing Characteristics of Particles of Arbitrary Shapes.” KONA, 22: 82–93.
Jia, X., Gan, M., Williams, R.A., Rhodes, D. (2007). “Validation of a digital packing algorithm in predicting powder packing densities.” Powder Tech. 174: 10–13.
Korte, A.C.J, Brouwers H.J.H. (2013). “Random packing of digitized particles.” Powder Techn. 233: 319–324.
Li, S.X., Zhao, J. (2009). “Sphere assembly model and relaxation algorithm for packing of non-spherical particles.” Chin. J. Comp. Phys. 26(3): 167–173.
Li, S.X., Zhao, J., Lu, P., Xie, Y. (2010). “Maximum packing densities of basic 3D objects.” Chin. Scien. Bull. 55(2): 114–119.
Sriramya, P., Varthini, P.B. (2012). “A State-of-the -Art Review of Bin Packing Techniques.” Eur. J. Scien. Res. 86(3): 360–364.
Birgin, E.G., Martinez, J.M., Nishihara, F.H., Ronconi, D.P. (2006). “Orthogonal packing of rectagular items within arbitrary convex regions by nonlinear optimization.” Comput. Oper. Res. 33: 3535–3548.
Birgin, E., Martínez, J., Ronconi, D. (2005). “Optimizing the packing of cylinders into a rectangular container: A nonlinear approach.” Eur. J. of Oper. Res. 160 (1): 19–33.
Egeblad, J., Nielsen, B.K., Brazil, M. (2009). “Translational packing of arbitrary polytopes.” http://www.sciencedirect.com/science/journal/09257721">Comp. Geom.http://www.sciencedirect.com/science/journal/09257721/42/4"> 42(4): 269–288.
Fasano, G. A. (2013). “Global Optimization point of view for non-standard packing problems.” J. Glob. Optim. 55(2): 279–299.
Petrov, M.S., Gaidukov, V.V., Kadushnikov, R.M. (2004). ”Numerical method for modelling the microstructure of granular materials.” Powder Metall. and Metal Ceram. 43 (7-8): 330–335.
Torquato, S., Jiao, Y. (2009). “Dense polyhedral packings: Platonic and Archimedean solids.” Phys. Rev. 80: 041104.
Y. Stoyan, N. Gil, G. Scheithauer, A. Pankratov, I. Magdalina (2005). “Packing of convex polytopes into a parallelepiped.” Optimization. 54(2): 215 – 235.
Chernov, N., Stoyan, Y., Romanova, T. (2010). “Mathematical model and efficient algorithms for object packing problem”. Comput. Geom.: Theory and Appl. 43(5): 535–553.
Stoyan, Y., Chugay, А. (2012). “Mathematical modeling of the interaction of non-oriented convex polytopes”. Cyber. and Syst. Anal. 48 (6): 837–845.
StoyanYu., Chugay A. (2011). “Construction of radical free phi-functions for spheres and non-oriented polytopes.” Rep. of NAS of Ukraine. №12: 35-40.
Stoyan Yu,. Pankratov А., Romanova Т., Chernov N. (2014). “Quasi-phi-function for mathematical modelling of geometric objects interactions.” Rep. of NAS of Ukraine 9: 53–57.
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.
Stoyan, Y., Yaskov, G. (2012). “Packing congruent hyperspheres into a hypersphere” Journal of Global Optimization, 52(4): 855–868 .
Chernov, N., Stoyan, Y., Pankratov, A., Romanova, T. (2014). “Quasi-phi-functions and optimal packing of ellipses.” Subm. to J. of Glob. Optim.
##submission.downloads##
Опубліковано
Номер
Розділ
Ліцензія
Авторське право (c) 2015 A. V. Pankratov, T. E. Romanova, A. M. Chugay
Ця робота ліцензується відповідно до Creative Commons Attribution-NoDerivatives 4.0 International License.
Автори, які публікуються в цьому журналі, погоджуються з наступними умовами:
- Автори залишають за собою право на авторство своєї роботи і передають журналу право першої публікації цієї роботи на умовах ліцензійного договору (угоди).
- Автори мають право самостійно укладати додаткові договори (угоди) з неексклюзивного поширення роботи в тому вигляді, в якому вона була опублікована цим журналом (наприклад, розміщувати роботу в електронному сховищі установи або публікувати в складі монографії), за умови збереження посилання на першу публікацію роботи в цьому журналі.
- Політика журналу дозволяє розміщення авторами в мережі Інтернет (наприклад, у сховищах установи або на персональних веб-сайтах) рукопису роботи як до подачі цього рукопису в редакцію, так і під час її редакційної обробки, оскільки це сприяє виникненню продуктивної наукової дискусії і позитивно позначається на оперативності та динаміці цитування опублікованої роботи (див. The Effect of Open Access).
