Packing ellipses in an optimized rectangular container
- PDF / 2,440,181 Bytes
- 11 Pages / 595.276 x 790.866 pts Page_size
- 88 Downloads / 251 Views
(0123456789().,-volV)(0123456789().,-volV)
Packing ellipses in an optimized rectangular container A. Pankratov1 • T. Romanova1
•
I. Litvinchev2
Springer Science+Business Media, LLC, part of Springer Nature 2018
Abstract The paper studies packing ellipses in a rectangular container of minimum area. The problem has various applications in production, logistics, industrial design. New phi-functions are proposed to state containment constraints and quasi-phifunctions are used for analytical description of non-overlapping constraints. A mathematical model for the packing problem is stated as a nonlinear programming problem. Two algorithms to find feasible starting points for identical and non-identical ellipses are proposed. The optimization procedure is used as a compaction algorithm to search for local optimal solutions. Computational results are provided to show the efficiency of the proposed approach. Keywords Ellipses Packing Continuous rotations Phi-function technique Mathematical modelling Nonlinear optimization
1 Introduction Mathematical modeling of packing problems is a part of computational geometry and solution algorithms related to Operations Research. A problem of packing ellipses has multiple applications in modern biology, mineralogy, medicine, materials science, nanotechnology, robotics, coding, pattern recognition systems, control systems, 3DPrinting etc. The particular interest to the packing problem arises in logistics. One of application is described in [1]. Color to be painted on walls is usually stored in paint buckets, which have an elliptical shape. This shape allows the painting rolls to be larger in length compared to a circular bucket having the same volume. The best area utilization is desired when transporting such buckets (differently or equally sized) on palettes. As described by Miller [2], ellipses can be used to approximate (irregular or nonconvex) geometric objects via a cover. The obtained ellipse placements can then help to compute solutions to the original problem. & T. Romanova [email protected] 1
Institute for Mechanical Engineering Problems of the National Academy of Sciences of Ukraine, Kharkiv, Ukraine
2
Nuevo Leon State University (UANL), Mexico, Mexico
We consider here a packing problem in the following setting. Let X ¼ fðx; yÞ 2 R2 : 0 x l; 0 y wg denote a rectangular container of variable length l and width w. Assume a set of ellipses Ei ; i 2 f1; . . .; ng ¼ In , is given. Each ellipse Ei is defined by its semi-axes ai and bi , ai [ bi : With each ellipse Ei we associate its local coordinate system whose origin coincides with the center of the ellipse. We call (xi,yi, hi) the vector of placement parameters of Ei , where (xi, yi) is a translation vector and hi is a rotation angle. Ellipse packing problem. Pack the set of ellipses Ei , i 2 In , within a rectangular domain X of minimum area. One way to solve the packing problem is to approximate our ellipses with circular arcs and apply the existing phifunctions (see [3, 4] for details). However
Data Loading...
