A fast and scalable bottom-left-fill algorithm to solve nesting problems using a semi-discrete representation

DOI10.1016/J.EJOR.2021.10.043zbMATH Open1506.90218arXiv2103.08739OpenAlexW3208902804MaRDI QIDQ2116899FDOQ2116899

T. Wauters, Dirk Roose, Sahar Chehrazad

Publication date: 18 March 2022

Published in: European Journal of Operational Research (Search for Journal in Brave)

Abstract: We present a fast algorithm to solve nesting problems based on a semi-discrete representation of both the 2D non-convex pieces and the strip. The pieces and the strip are represented by a set of equidistant vertical line segments. The discretization algorithm uses a sweep-line method and applies minimal extensions to the line segments of a piece to ensure that non-overlapping placement of the segments, representing two pieces, cannot cause overlap of the original pieces. We implemented a bottom-left-fill greedy placement procedure, using an optimised ordering of the segments overlap tests. The C++ implementation of our algorithm uses appropriate data structures that allow fast execution. It executes the bottom-left-fill algorithm for typical ESICUP data sets in a few milliseconds, even when rotation of the pieces is considered, and thus provides a suitable `building block' for integration in metaheuristics. Moreover, we show that the algorithm scales well when the number of pieces increases.

Full work available at URL: https://arxiv.org/abs/2103.08739

Recommendations

• Fast neighborhood search for two- and three-dimensional nesting problems
• An algorithm for polygon placement using a bottom-left strategy
• TOPOS -- A new constructive algorithm for nesting problems
• Algorithm for 2D irregular-shaped nesting problem based on the NFP algorithm and lowest-gravity-center principle
• A fully general, exact algorithm for nesting irregular shapes

zbMATH Keywords

cuttingnesting problemssweep-line algorithmbottom-left-fill algorithmsemi-discrete representation

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Cites Work

• TOPOS -- A new constructive algorithm for nesting problems
• On genetic algorithms for the packing of polygons
• A 2-exchange heuristic for nesting problems
• The geometry of nesting problems: a tutorial
• An improved typology of cutting and packing problems
• A New Bottom-Left-Fill Heuristic Algorithm for the Two-Dimensional Irregular Packing Problem
• Complete and robust no-fit polygon generation for the irregular stock cutting problem
• Computational geometry. Algorithms and applications.
• Irregular Packing Using the Line and Arc No-Fit Polygon
• Algorithms for nesting with defects
• Jostling for position: local improvement for irregular cutting patterns
• Dealing with nonregular shapes packing
• Irregular packing problems: a review of mathematical models
• Raster penetration map applied to the irregular packing problem

Cited In (4)

• A 2-exchange heuristic for nesting problems
• The necessary and sufficient condition and the efficient algorithms for gradually varied fill
• Fast neighborhood search for two- and three-dimensional nesting problems
• TOPOS -- A new constructive algorithm for nesting problems

Uses Software

• TOPOS
• MKL
• JNFP
• speedtest

This page was built for publication: A fast and scalable bottom-left-fill algorithm to solve nesting problems using a semi-discrete representation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2116899)