算法
嵌套(过程)
等距
离散化
计算机科学
可扩展性
块(置换群论)
线段
代表(政治)
正多边形
自上而下和自下而上的设计
旋转(数学)
直线(几何图形)
集合(抽象数据类型)
数学优化
数学
几何学
人工智能
数学分析
冶金
材料科学
软件工程
程序设计语言
法学
政治
政治学
数据库
作者
Sahar Chehrazad,Dirk Roose,Tony Wauters
标识
DOI:10.1016/j.ejor.2021.10.043
摘要
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.
科研通智能强力驱动
Strongly Powered by AbleSci AI