LAYOUT PROBLEMS FOR ARC OBJECTS IN CONVEX DOMAINS

Authors

A. Pankratov, A. Podgorny Institute of Mechanical Engineering Problems of NASU (2/10, Pozharsky St., Kharkiv, 61046, Ukraine), e-mail: impankratov@mail.ru, ORCID: 0000-0002-2958-8923

T. Romanova, A. Podgorny Institute of Mechanical Engineering Problems of NASU (2/10, Pozharsky St., Kharkiv, 61046, Ukraine), e-mail:  sherom@kharkov.ua, ORCID: 0000-0002-8618-4917

A. Kotelevskiy, A. Podgorny Institute of Mechanical Engineering Problems of NASU (2/10, Pozharsky St., Kharkiv, 61046, Ukraine)

Abstract

The optimization problem of packing arbitrary objects bounded by arcs of circles and straight line segments into convex regions is considered. A mathematical model is constructed in the form of a problem of non-differentiable optimization, whose set of realizations covers a wide class of scientific and applied problems of geometric design. A methodology for solving packaging problems is developed, taking into account technological constraints (minimum allowable distances, prohibition zones, possibility of continuous transmissions and rotation of objects). A decision space generator and a solver for automatically solving NLP problems of the class under consideration are proposed.

Keywords: packing problem, arbitrary objects, continuous rotations, allowable distances, phi- functions; decision space generator; nonlinear optimization

References

1. Wascher, G., Hauner, H., & Schuma, H. (2007). An improved typology of cutting and packing problems. European Journal of Operational Research, no. 183, pp. 1109-1130. https://doi.org/10.1016/j.ejor.2005.12.047
2. Gomes, A. M. (2013). Irregular Packing Problems: Industrial Applications and New Directions Using Computational Geometry. IFAC Proc. Volumes, vol. 46 (7), pp. 378-38311. https://doi.org/10.3182/20130522-3-BR-4036.00113
3. Chazelle, B., Edelsbrunner, H., & Guibas, L. J. (1989). The complexity of cutting complexes. Discrete & Computational Geometry, no. 4(2), pp. 139–81. https://doi.org/10.1007/BF02187720
4. Bennell, J. A. & Oliveira J. F. (2008). The geometry of packing problems: A tutorial. European Journal of Operational Research, no. 184(2), pp. 397–415. https://doi.org/10.1016/j.ejor.2006.11.038
5. Bennell, J. A. & Oliveira J. F. (2009). A tutorial in irregular shape packing problem. Journal of the Operational Research Society, vol. 60, pp. 93–105. https://doi.org/10.1057/jors.2008.169
6. Blazewicz, J., Drozdowski, M., Soniewicki, B., & Walkowiak, R. (1989). Two-dimensional cutting problem basic complexity results and algorithms for irregular shapes. Found. Cont. Eng., no. 14 (4), pp. 137–160.
7. Burke, E. K., Hellier, R. S. R., Kendall, G., & Whitwell, G. (2007). Complete and robust no-fit polygon generation for the irregular stock cutting problem. EJOR, no. 179, pp. 27–49. https://doi.org/10.1016/j.ejor.2006.03.011
8. Whitwell, G. (2005). Novel Heuristic and Metaheuristic Approaches to Cutting and Packing. PhD Thesis. School of Computer Science and Information Technology, University of Nottingham, 313 p.
9. Burke, E.K., Hellier, R., Kendall, G., & Whitwell, G. (2010). Irregular packing using the line and arc no-fit polygon. Operations Research, no. 58 (4), pp. 948–970. https://doi.org/10.1287/opre.1090.0770
10. Milenkovic, V. (1999). Rotational polygon containment and minimum enclosure using only robust 2d constructions. Computational Geometry, no. 13(1), pp. 3–19. https://doi.org/10.1016/S0925-7721(99)00006-1
11. Milenkovic, V. (1998). Rotational polygon overlap minimization and compaction. Computational Geometry, no. 10(4), pp. 305–318. https://doi.org/10.1016/S0925-7721(98)00012-1
12. Rocha, P., Rodrigues, R., Gomes, A. M., et al. (2014). Circle Covering Representation for Nesting problems with continuous rotations. Preprints of the 19th World Congress, The International Federation of Automatic Control, Cape Town, South Africa, August 24–29. https://doi.org/10.3182/20140824-6-ZA-1003.01663
13. Leung, S. C. H., Lin, Y., & Zhang, D. (2012). Extended local search algorithm based on nonlinear programming for two-dimensional irregular strip packing problem. Computers & Operations Research, vol. 39, no. 3, pp. 678–686. https://doi.org/10.1016/j.cor.2011.05.025
14. Bennell, J., Scheithauer, G., Stoyan, Yu., & Romanova, T. (2010) Tools of mathematical modelling of arbitrary object packing problems. Annals of Operations Research, Publisher Springer Netherlands, vol. 179, iss. 1, pp. 343–368. https://doi.org/10.1007/s10479-008-0456-5
15. Chernov, N., Stoyan, Y., & Romanova, T. (2010). Mathematical model and efficient algorithms for object packing problem. Computational Geometry, Theory and Applications, vol. 43, no. 5, pp. 535–553. https://doi.org/10.1016/j.comgeo.2009.12.003
16. Chernov, N., Stoyan, Y., Romanova, T., & Pankratov, A. (2012). Phi-functions for 2D objects formed by line segments and circular arcs. Advances in Operations Research, 26 p. https://doi.org/10.1155/2012/346358
17. Bennell, J., Scheithauer, G., Stoyan, Y., Romanova, T., & Pankratov, A. (2015). Optimal clustering of a pair of irregular objects. Journal of Global Optimization, no. 61(3), pp. 497–524. https://doi.org/10.1007/s10898-014-0192-0
18. Pankratov, A. V. & Stoyan, Yu. G. (2005). Placement of non-convex polygons with rotations into a non-convex polygon. Proc. Workshop Cutting Stock Problems, Alutus, Miercurea-Ciuc, Romania, pp. 29–36.
19. Wachter, A. & Biegler, L. T. (2006). On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Mathematical Programming, no. 106(1), pp. 25–57. https://doi.org/10.1007/s10107-004-0559-y
20. Stoyan, Yu., Pankratov, A., & Romanova, T. (2015). Cutting and Packing problems for irregular objects with continuous rotations: mathematical modeling and nonlinear optimization. Journal of Operational Research Society, no. 67(5), pp. 786–800. https://doi.org/10.1057/jors.2015.94
21. Kallrath, J. & Rebennack, S. (2013). Cutting Ellipses from Area-Minimizing Rectangles. Journal of Global Optimization, no. 59(2–3), pp. 405–437. https://doi.org/10.1007/s10898-013-0125-3

Received 06 September 2016

Published 30 September 2016