1808. Packing Irregular Polygons in A Shape Optimized Convex Container
Invited abstract in session MC-21: Irregular packing and cutting, stream Cutting and packing (ESICUP).
Monday, 12:30-14:00Room: Esther Simpson 2.12
Authors (first author is the speaker)
| 1. | Tetyana Romanova
|
| Leeds University Business School, University of Leeds | |
| 2. | Julia Bennell
|
| Leeds University Business School, University of Leeds | |
| 3. | Josef Kallrath
|
| Dept. of Astronomy, University of Florida | |
| 4. | Igor Litvinchev
|
| Universidad Autónoma de Nuevo León | |
| 5. | Olexandr Pankratov
|
| A.M. Pidgorny Institute of Power Machines and Systems National Academy of Sciences of Ukraine | |
| 6. | Yifu Wei
|
| School of Chemical and Process Engineering, University of Leeds |
Abstract
One of classical problems in computational geometry is constructing a convex hull of a given set of convex polygons. This problem has important applications in logistics, manufacturing, operations research, chemistry and mechanics. Corresponding problems arise, e.g., in animation to facilitate collision detection, in epidemiology to represent a spatial extent of an epidemic. However, if the polygons are freely moving without overlapping, then different convex hulls can be constructed depending on the translated/rotated positions of polygons. Correspondingly, the problem to find a minimum perimeter/area convex hull arises. Another interpretation of this problem is packing irregular polygons in a shape-optimized (soft) convex polygonal container. The container is represented by a convex polygon with at most m unknown vertices, while the side lengths of the container can be bounded. The convexity and metric conditions for the container are formulated, as well as the non-overlapping and containment constraints for arbitrary polygonal objects. The objective function to be minimized is either the area of the soft container or the length of its perimeter. A corresponding nonlinear programming problem is formulated, and a multistart model-based heuristic is proposed. Computational results are reported to demonstrate the efficiency of the proposed approach.
Keywords
- Cutting and Packing
- Continuous Optimization
Status: accepted
Back to the list of papers