Abstract
We further improve our methodology for solving irregular packing and cutting problems. We deal with an accurate representation of objects bounded by circular arcs and line segments and allow their continuous rotations and translations within rectangular and circular containers. We formulate a basic irregular placement problem which covers a wide spectrum of packing and cutting problems. We provide an exact non-linear programming (NLP) model of the problem, employing ready-to-use phi-functions. We develop an efficient solution algorithm to search for local optimal solutions for the problem in a reasonable time. The algorithm reduces our problem to a sequence of NLP subproblems and employs optimization procedures to generate starting feasible points and feasible subregions. Our algorithm allows us to considerably reduce the number of inequalities in NLP subproblems. To show the benefits of our methodology we give computational results for a number of new challenger and the best known benchmark instances.
Similar content being viewed by others
References
Alvarez-Valdes R, Martinez A and Tamarit JM (2013). A branch & bound algorithm for cutting and packing irregularly shaped pieces. International Journal of Production Economics 145 (2): 463–477.
Bennell JA and Oliveira JF (2008). The geometry of packing problems: A tutorial. European Journal of Operational Research 184 (2): 397–415.
Bennell JA and Oliveira JF (2009). A tutorial in irregular shape packing problem. Journal of the Operational Research Society 60 (S1): 93–105.
Bennell JA, Scheithauer G, Stoyan Y, Romanova T and Pankratov A (2015). Optimal clustering of a pair of irregular objects. Journal of Global Optimization 61 (3): 497–524.
Blazewicz J, Drozdowski M, Soniewicki B and Walkowiak R (1989). Two-dimensional cutting problem basic complexity results and algorithms for irregular shapes. Foundations of Control Engineering 14 (4): 137–160.
Burke EK, Hellier R, Kendall G and Whitwell G (2007). Complete and robust no-fit polygon generation for the irregular stock cutting problem. European Journal of Operational Research 179 (1): 27–49.
Burke EK, Hellier R, Kendall G and Whitwell G (2010). Irregular packing using the line and arc no-fit polygon. Operations Research 58 (4): 948–970.
Chazelle B, Edelsbrunner H and Guibas LJ (1989). The complexity of cutting complexes. Discrete & Computational Geometry 4 (2): 139–181.
Chernov N, Stoyan Y and Romanova T (2010). Mathematical model and efficient algorithms for object packing problem. Computational Geometry: Theory and Applications 43 (5): 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, http://www.hindawi.com/journals/aor/2012/346358/; Available from http://www.researchgate.net/publication/258383475_Phi-Functions_for_2D_Objects_Formed_by_Line_Segments_and_Circular_Arcs, accessed 1 November 2015.
Egeblad J, Nielsen BK and Odgaard A (2007). Fast neighborhood search for two and three-dimensional nesting problems. European Journal of Operational Research 183 (3): 1249–1266.
Gomes AM and Oliveira JF (2006). Solving irregular strip packing problems by hybridising simulated annealing and linear programming. European Journal of Operational Research 171 (3): 811–829.
Gomes AM (2014). Irregular packing problems: Industrial applications and new directions using computational geometry. Proceedings of the conference. Intelligent Manufacturing Systems. Golden Tower, São Paulo, Brazil. Vol. 11 (1), pp 378–383. doi:10.3182/20130522-3-BR-4036.00113.
Imamichi T, Yagiura M and Nagamochi H (2009). An iterated local search algorithm based on nonlinear programming for the irregular strip packing problem. Discrete Optimization 6 (4): 345–361.
Jones DR (2014). A fully general, exact algorithm for nesting irregular shapes. Journal of Global Optimization 59 (2–3): 367–404.
Kallrath J and Rebennack S (2014). Cutting ellipses from area-minimizing rectangles. Journal of Global Optimization 59 (2–3): 405–437.
Leung SCH, Lin Y and Zhang D (2012). Extended local search algorithm based on nonlinear programming for two-dimensional irregular strip packing problem. Computers and Operations Research 39 (3): 678–686.
Milenkovic V (1998). Rotational polygon overlap minimization and compaction. Computational Geometry 10 (4): 305–318.
Milenkovic V (1999). Rotational polygon containment and minimum enclosure using only robust 2D constructions. Computational Geometry 13 (1): 3–19.
Pankratov AV and Stoyan YG (2005). Placement of non-convex polygons with rotations into a non-convex polygon. Proceedings of the Workshop Cutting Stock Problems. Alutus. Miercurea-Ciuc, Romania, pp 29–36.
Rocha P (2014). Geometrical models and algorithms for irregular shapes placement problems. PhD thesis, INESC,Faculty of Engineering, University of Porto, Portugal.
Rocha P, Rui R, Gomes AM, Andretta M and Toledo FMB (2014). Circle covering representation for nesting problems with continuous rotations. Proceedings of the 19th World Congress. The International Federation of Automatic Control. Cape Town. South Africa. August 24–29. 19(1), pp 5235–5240. doi:10.3182/20140824-6-ZA-1003.01663.
Stoyan Y, Pankratov A and Romanova T (2015). Quasi-phi-functions and optimal packing of ellipses. Journal of Global Optimization doi:10.1007/s10898-015-0331-2, http://springerlink.bibliotecabuap.elogim.com/article/10.1007%2Fs10898-015-0331-2.
Stoyan YG and Patsuk VM (2010). Covering a compact polygonal set by identical circles. Computational Optimization and Applications 46 (1): 75–92.
Stoyan YG, Zlotnik MV and Chugay AM (2012). Solving an optimization packing problem of circles and non-convex polygons with rotations into a multiply connected region. Journal of the Operational Research Society 12 (3): 379–391.
Wachter A and Biegler LT (2006). On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Mathematical Programming 106 (1): 25–57.
Wascher G, Hauner H and Schuma H (2007). An improved typology of cutting and packing problems. European Journal of Operational Research 183 (3): 1109–1130.
Whitwell G (2005). Novel heuristic and metaheuristic approaches to cutting and packing. School of Computer Science and Information Technology. University of Nottingham. PhD Thesis.
Author information
Authors and Affiliations
Appendices
Appendix A
We follow here the paper (Bennell et al, 2015) to define placement objects. We consider phi-objects as mathematical models of our placement objects. A two-dimensional phi-object T is a canonically closed point set T⊂R2 (T=cl*(T)=cl(int(T)) having the same homothopic type as its interior (details of defenition one can find in Chernov et al (2010)). Each composed placement object T is given by an ordered collection of frontier elements l1, l2, …, l n , (in counter clockwise order). Each element l i is given by tuple if l i is an arc or by tuple (x i , y i , 0) if l i is a line segment, where (x i , y i ) and (xi+1, yi+1) are the end points of l i , is the center point of the arc generating circle C i of radius |r i |. We note that l i is a ‘convex’ arc, if r i >0; l i is a ‘concave’ arc, if r i <0 and assume (xi+1, yi+1)=(x1, y1) for i=n.
Given the ordered collection of line segments and circular arcs, in our programme we apply the object decomposition algorithm described by Chernov et al (2010) to obtain a set of basic objects automaticaly that covers our object T. Authors of the paper prove that each phi-object T, bounded by line segments and circular arcs, may be presented as a union of a finite number of basic objects of four types, including convex polygons (K), circular segments (D), hats (H) and horns (V). Each basic object is the intersection of primitive objects (half-planes, circles and circular holes). Illustrations of primitive and basic objects are given in Figure A1.
Thus, we represent placement object T in the form
where ℜ is the set of basic objects.
Example A
-
Let us consider two objects A and B given in Figure A2a . These can be decomposed into basic objects according to formula (A), so we have A=H∪K, B=D∪V, V, D, H, K∈ℜ, n A =n B =2 (see Figure A2b).
We set that a circle T≡C is defined by its radius (r C ) and a convex m-polygon T≡K is defined by its verticies (x i , y i , i=1, 2, …, m).
Appendix B
Example B1
-
Let a basic phi-function Φ k in (6) be given in the form
where ϕ j ∈{f}, j=1, 2, 3, 4, {f} is a family of smooth functions.
The transformed function takes the equivalent form according to (8)
Example B2
-
Let us consider a region W described by inequality ϕ⩾0, where ϕ has the form defined in Example B1. We emphasize that ϕ⩾0 if at least min{ϕ1, ϕ3}⩾0 or min{ϕ2, ϕ3}⩾0 or min{ϕ1, ϕ4}⩾0 or min{ϕ2, ϕ4}⩾0.
Taking into account
we conclude that the region W can be presented as a union of subregions W1, W2, W3 and W4, described by the appropriate inequality systems in (B1), (B2), (B3) and (B4).
Appendix C
Data to Instance 4 of Subsection 4.2
Four types of arc objects are considered: A1, A2, A3, A4 (see Figure C1). Each object is defined by tuple l A =(l1, l2, l3), where i=1, 2, 3 (see Appendix A for details).
For the first type object: =(−127.793885277, −31.260629710, −269.683141074, −114.585285651, −300.620109728, 107.745848162, −147.983732947, −855.023127662, 880.040475106, 218.929823670, 25.145613652, 204.120208658, −286.311966465, −260.582463369, 222.396098309),
For the second type object: =(−127.793885277, −31.260629710, −222.243232453, −89.597792211, −250.196951150, 107.745848162, −147.983732947, −341.501046399, 419.415318598, −8.394672165, 114.198987902, 144.791346024, 164.379352457, 33.240703895, 1.730772263),
For the third type object: =(−190.389372841, 30.002879612, 263.715084806 28.896179393, 176.493468167, 45.150360598, −86.720223626, 227.048705406, −125.107278015, 63.491131206, 51.603500338, 206.054855345, −179.259124424, −127.468038006, 197.856206394),
For the forth type object: =(−190.389372841, 30.002879612, 181.347924897, −17.140772642, 83.593852669, 45.150360598, −86.720223626, 214.700196049, −108.608670698, 63.127480656, 51.603500338, 206.054855345, 477.417362860, 197.319382676, −248.581504831).
Rights and permissions
About this article
Cite this article
Stoyan, Y., Pankratov, A. & Romanova, T. Cutting and packing problems for irregular objects with continuous rotations: mathematical modelling and non-linear optimization. J Oper Res Soc 67, 786–800 (2016). https://doi.org/10.1057/jors.2015.94
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1057/jors.2015.94