Layout problems for arc objects in convex domains
Keywords:
irregular shapes, convex domains, phi-functions, object rotations, allowable distances, solution tree, solution algorithms, local optimisationAbstract
We introduce a new methodology for solving layout problems. Our objects and containers are bounded by circular arcs and line segments. We allow continuous object translations and rotations as well as minimal allowable distances between objects. For describing non-overlapping, containment and distance constraints the phi-function technique is used. We provide a general mathematical model as nonlinear programming problem with nonsmooth functions. We propose here the automatic feasible region generator, using phi-trees. The generator allows us to form ready-to-use systems of inequalities with smooth functions in order to apply efficient nonlinear optimisation procedures. We develop an efficient solution algorithm and original solver for layout problems which uses the core representation of inequlities in a sybmol form and provides exact calculation of Jacobian and Hessian matrixes. The search for local minima of NLP-problems is performed by IPOPT algorithm. An essential part of our local optimisation scheme is LORA algorithm that simplifies description of feasible region of the problem and reduces the runtime of local optimisation. It is due to this reduction our strategy can work efficiently with collections of composed objects and search for “good” local-optimal solutions for layout problems in reasonable time.
References
Wascher, G., Hauner, H., Schuma, H.: An improved typology of cutting and packing problems. European Journal of Operational Research. 183, 1109-1130 (2007).
Gomes, A. M. Irregular Packing Problems: Industrial Applications and New Directions Using Computational Geometry Volume 11 (2014)| Part 1 (DOI) 10.3182/20130522-3-BR-4036.00113, – P. 378-383.
Chazelle, B., Edelsbrunner, H., Guibas, L.J.: The complexity of cutting complexes. Discrete & Computational Geometry. 4(2), 139–81 (1989).
ennell J.A., Oliveira J.F.: The geometry of packing problems: A tutorial. European Journal of Operational Research. 184:397–415 (2008).
Bennell, J.A., Oliveira J.F, A tutorial in irregular shape packing problem, Journal of the Operational Research Society, 60:s93-s105 (2009).
Blazewicz, J., Drozdowski, M., Soniewicki, B., Walkowiak, R.: Two-dimensional cutting problem basic complexity results and algorithms for irregular shapes. Found. Cont. Eng., 14(4), 137-60 (1989).
Burke E.K. Complete and robust no-fit polygon generation for the irregular stock cutting problem / E.K. Burke, R. S. R. Hellier, G. Kendall, G. Whitwell. EJOR 2007 27-49.
Whitwell G. Novel Heuristic and Metaheuristic Approaches to Cutting and Packing. School of Computer Science and Information Technology. University of Nottingham; 2005, PhD Thesis, 313 p.
Burke, E.K., Hellier, R., Kendall, G., Whitwell, G.: Irregular packing using the line and arc no-fit polygon. Operations Research. 58(4), 948–970 (2010).
Milenkovic, V.: Rotational polygon containment and minimum enclosure using only robust 2d constructions. Computational Geometry. 13(1), 3–19 (1999).
Milenkovic, V.: Rotational polygon overlap minimization and compaction. Computational Geometry. 10(4), 305–318 (1998).
Pedro Rocha, Rui Rodrigues, A. Miguel Gomes, Franklina M.B. Toledo, Marina Andretta 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, 2014.
Leung, Stephen C.H. Lin, Yangbin Zhang, Defu Extended local search algorithm based on nonlinear programming for two-dimensional irregular strip packing problem Computers & Operations Research, v.39, no.3, 2012 March, p.678(9) (ISSN: 0305-0548).
J. Bennell, G. Scheithauer, Yu. Stoyan, and T. Romanova (2010) Tools of mathematical modelling of arbitrary object packing problems// J. Annals of Operations Research, Publisher Springer Netherlands: V 179, Issue 1, pp. 343-368.
Chernov N., Stoyan Y., Romanova T. (2010) Mathematical model and efficient algorithms for object packing problem// Computational Geometry: Theory and Applications, vol. 43:5, pp. 535-553.
Chernov N, Stoyan Y, Romanova T and Pankratov A (2012) Phi-functions for 2D objects formed by line segments and circular arcs. Advances in Operations Research. doi:10.1155/2012/346358.
Bennell J., Scheithauer G., Stoyan Y., Romanova T., and Pankratov A. (2014) Global optimisation"Optimal clustering of a pair of irregular objects" Journal of Global Optimisation, JOGO-D-13-00328R2.
Pankratov A.V., Stoyan Yu. G. Placement of non-convex polygons with rotations into a non-convex polygon// Proc. Workshop Cutting Stock Problems. – 2005. Alutus, Miercurea-Ciuc, Romania. – P. 29-36.
Wachter, A., Biegler, L. T. (2006) On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Mathematical Programming.106, 1, 25-57.
Yu. Stoyan, A. Pankratov, T. Romanova (2015) Cutting and Packing problems for irregular objects with continuous rotations: mathematical modeling and nonlinear optimization. Journal of Operational Research Society, DOI 10.1057/jors.2015.94.
Josef Kallrath and Steffen Rebennack, "Cutting Ellipses from Area-Minimizing Rectangles" Journal of Global Optimisation, (2013), DOI10.1007/s10898-013-0125-3.
Downloads
Published
Issue
Section
License
Copyright (c) 2016 А. В. Панкратов, T. Romanova, A. Kotelevskiy
This work is licensed under a Creative Commons Attribution-NoDerivatives 4.0 International License.
All authors agree with the following conditions:
- The authors reserve the right to claim authorship of their work and transfer to the journal the right of first publication of the work under the license agreement (the agreement).
- Authors have a right to conclude independently additional agreement on non-exclusive spreading the work in the form in which it was published by the jpurnal (for example, to place the work in institution repository or to publish as a part of a monograph), providing a link to the first publication of the work in this journal.
- Journal policy allows authors to place the manuscript in the Internet (for example, in the institution repository or on a personal web sites) both before its submission to the editorial board and during its editorial processing, as this ensures the productive scientific discussion and impact positively on the efficiency and dynamics of citation of published work (see The Effect of Open Access).
