高效求解嵌套问题的局部搜索算法

需积分: 9 50 浏览量更新于2024-07-17 收藏 2.96MB PDF 举报

"这篇技术报告探讨了'Fast Neighborhood Search for the Nesting Problem'，由 Benny Kjr Nielsen 和 Allan Odgaard撰写，主要关注二维形状在容器内的嵌套问题，旨在优化包装，例如最小化矩形容器的尺寸或最大化容器内包含的形状数量。报告详细介绍了问题定义、几何特性、现有解决方案方法以及局部搜索算法等关键概念。" 在《Fast Neighborhood Search for the Nesting Problem》中，作者首先介绍了问题的基本概念。嵌套问题本质上是将各种不规则的二维形状紧凑地排列在一个容器内，而不产生重叠。这个问题在多个领域都有应用，如制造、物流和计算机图形学。报告的第二部分深入讨论了问题的各个方面。2.1章节明确了问题定义，指出目标可以是尺寸最小化或形状的最大化放置。2.2章节探讨了问题的几何特性，这涉及到形状的大小、形状和相对位置。接着，2.3章节概述了现有的解决方法，包括合法放置和放松放置方法。2.4和2.5章节分别详细阐述了这两种方法的细节。2.6章节提到了商业化的求解器，这些工具通常用于实际应用中的嵌套问题解决。此外，2.7章节还简要讨论了三维嵌套的可能性，尽管报告主要集中在二维问题上。第三部分重点关注解决方案方法。3.1章节介绍了局部搜索，这是一种常用的方法，通过迭代改进当前解决方案来寻找最优解。3.2章节进一步探讨了Guided Local Search，这是一种有指导的局部搜索策略，可以更有效地探索解空间。3.3章节讨论了初始解决方案的选择，这是搜索过程的起点。3.4章节则讲述了不同的打包策略，这些策略决定了如何移动和旋转形状以优化嵌套。报告的核心在于第四部分，即快速邻域搜索。4.1章节给出了背景信息，说明了快速邻域搜索在解决嵌套问题中的重要性。4.2章节至4.5章节详细阐述了一种特殊的交集面积公式、矢量场的概念、形状和边界的符号边界以及一个简单的示例。这些理论基础支持了高效的变换算法，包括4.4章节的多边形平移和4.5章节的多边形旋转。最后，第五部分讨论了其他约束，如5.2章节的质量区域和5.3章节的多边形之间的边缘（或间隙）。边缘部分特别提到了直角前进的算法，这是处理形状间距离限制的一种方法。这篇报告提供了一个全面的视角来理解并解决二维嵌套问题，特别是在快速搜索邻域算法方面的创新，对于优化制造过程和提高效率具有重要意义。

2.4. Legal placement methods The Nesting Problem

constitutes 115000 lines of code (see Section 2.6).

In 1998 Dowsland et al. [23] introduce a new idea, jostling for position. They use a standard

bottom left placement algorithm with hole ﬁlling for their ﬁrst placement. Then they sort the

stencils in decreasing order using their right-most x-coordinates in the placement. A new

placement is then made using a right-sided variant of the placement algorithm. This process is

repeated for a ﬁxed number of iterations (this is the jostling). In addition to NFPs, all polygons

are split into x-convex subparts to speed up calculations. Any horizontal line through an x-

convex polygon crosses at most two edges. Dowsland et al. emphasize that their algorithm is

intended for situations where computation time is strictly limited, but exceeds the time needed

for a single pass placement. A test instance with 43 stencils takes around 30 seconds for 19

jostles on a Pentium 166 MHz.

Time is not the main consideration in an algorithm described by Oliveira et al. [51] (2000).

Their placement algorithm TOPOS (a Portuguese acronym) is actually 126 diﬀerent algo-

rithms. The basic algorithm is a leftmost placement without hole ﬁlling. The sequence of

stencils is either based on some initial sorting scheme (length, area, convexity, ...) or is deter-

mined iteratively by which stencil would result in the best partial solution in the placement

according to some measure of best ﬁt. Five test instances are used in the experiments on a

Pentium Pro 200 MHz. Only the best results are presented, but average execution times are

also given. The test instance from the jostle algorithm is also tested (it was actually created

by Oliveira et al.). The length is about 4% worse and it has taken 34.6 seconds to ﬁnd. But

this is not quite true since this is only the time used by 1 out of 126 algorithms. Using the

average execution times the real amount of time used is more like 45 minutes. Even though

Oliveira et al. has done a lot of work to be able to evaluate the eﬃciency of diﬀerent strategies,

the small amount of test instances limit the conclusions to be made. In their own words: “the

geometric properties of the pieces to place [...] have a crucial inﬂuence on the results obtained

by diﬀerent variants of the algorithm”.

Recently Gomes and Oliveira [34] continued their work. Now the focus is on changing the

order in the sequence of stencils used for the placement algorithm. The placement algorithm

is a greedy bottom-left heuristic with hole ﬁlling. The sequence of stencils is changed by

2-exchanges i.e. by swapping two stencils in the sequence used for the placement algorithm.

Diﬀerent neighborhoods are deﬁned that limit the number of possible 2-exchanges and diﬀerent

search strategies are also deﬁned (ﬁrst better, best and random better). They are all local search

variants and include no hill climbing. Again all combinations are attempted on 5 test instances

and they obtain most of the best published solutions, but the computation times are now even

worse than before. The above mentioned data instance takes more than 10 minutes for the best

solution produced (Pentium III 450 MHz). Other instances take hours for the best solution

and days if all search variants (63) are included in the computation time.

The above article is one of the few addressing the problem of limited freedom of rotation

when using NFPs, but they simply claim: “Fortunately, in real cases the admissible orientations

are limited to a few possibilities due to technological constraints (drawing patterns, material

resistance, etc.)”. This is obviously not true for a lot of real world problems e.g. in metal sheet

cutting (although rotation can be limited in this industry as well). Even the textile industry

allows a small (but continuous) amount of rotation as already noted by Art back in 1966.

In the same journal issue a much faster algorithm is presented by Dowsland et al. [24]. This

is also a bottom-left placement heuristic with hole ﬁlling using NFPs. Experiments are done

on a 200 MHz Pentium and solutions are on average found in about 1 minute depending on

various criteria. The quality of the solutions can be quite good, but they cannot compete with

The Nesting Problem 2.5. Relaxed placement methods

the best results of the method applied by Gomes and Oliveira. The speed of their algorithm

makes it very interesting for the purpose of generating a good initial solution for some of the

relaxed placement methods — including the solution method presented in this thesis.

2.5 Relaxed placement methods

Methods allowing overlap as part of the solution process have a much shorter history than the

legal placement methods, but they do make up for this in numbers. During the 90’s quite a

few meta heuristic methods have been applied to the nesting problem, but it has not been

a continuous development — even test instances are rarely reused. This means that a lot of

diﬀerent ideas have been tried, but very few of them have been compared.

The most popular meta heuristic method applied to the nesting problem is the same as in

most areas of optimization, Simulated Annealing (SA). One of the ﬁrst articles on the subject

by Lutﬁyya et al. [45] (1992) is mainly focused on describing and ﬁne tuning the SA techniques.

Among other things their cost function maximizes edgewise adjacency between polygons, which

is an interesting approach. It also minimizes the distance to the origin to keep the stencils

closely together. Overlap is determined by using a raster model and to remedy the inherent

problems of this approach they suggest for future research to increase the granularity as part

of the annealing process. The neighborhood is searched by randomly displacing a polygon,

interchanging two polygons or rotating a polygon (within a limited set of rotation angles).

In the same year Jain et al. [40] also use SA, but their approach is quite diﬀerent since it is

focused on a special problem variation brieﬂy mentioned in the beginning of this chapter as the

repeated pattern problem. They only nest a few polygons, three or fewer, and the nesting is

supposed to be repeated on a continuous strip with ﬁxed width. Changing the repeat distance

is part of the neighborhood which also includes translation and rotation. Jain et al. refers to

blank nesting in the metal industry as the origin of the problem, but it is also relevant for

other industries, e.g. the textile industry [48].

The raster model technique returns in Oliveira et al. [50]. They present two variations of

SA, one using a raster model and one using the polygons as given. Both with neighborhoods

which only allow translation. In the polygonal variant they claim that the rectangular enclosure

of the intersection of two polygons can be “fairly fast” computed, but they do not describe

how. It cannot be much faster than calculating the exact overlap since the hard part is to ﬁnd

the intersection — not to calculate its area.

A much more ambitious application of SA is described by Heckmann and Lengauer [35].

They focus on the textile manufacturing industry, but their method can clearly handle problems

from other industries too. The neighborhood consists of translation, rotation and exchange. A

wide range of constraints are described and handled and the implementation has clearly been

ﬁne-tuned e.g. by using approximated polygons in the early stages to save computation time.

The annealing is used in 4 diﬀerent stages. The ﬁrst stage is a rough placement, the second

stage eliminates overlaps, the third stage is a ﬁne placement with approximated stencils and

the last stage is a ﬁne placement with the original stencils. This algorithm has evolved into

a commercial nesting library (see Section 2.6). Some experiments has also been done with

other meta heuristic methods and Threshold Accepting is concluded to be faster, but it does

not increase the yield. Whether it decreases the yield is not stated.

In the same year Theodoracatos and Grimsley [55] published their attempt at applying

SA to the nesting problem. They try to pack both circles and polygons (separately). The

2.6. Commercial solvers The Nesting Problem

number of polygons is very limited though, and they have some unsupported claims about

their geometric methods. E.g. they claim that the fastest point inclusion test is obtained by

testing against all the triangles in a triangulation of the polygons and intersection area is

calculated by calculating intersection areas of all pairs of triangles.

Jakobs [41] tried to apply a genetic algorithm, but just like Adamowicz and Albano he

actually packs bounding rectangles and then compact the solution in a post-processing step.

No comparisons with existing methods are done, but his method is most likely not competitive.

Bennell and Dowsland [6] has a much more interesting approach using a tabu search variant

called Tabu Thresholding (TT). This is one of the few nesting algorithms which uses intersection

depth to measure overlap. They only use horizontal intersection depth and this introduces some

problems since it does not always reﬂect the true overlap in an appropriate way. This is partly

ﬁxed by punishing moves that involve large stencils. Rotation is not allowed.

A couple of years later Bennell and Dowsland [7] continue their work. Now they try to

combine their TT solution method and the ideas for compaction and separation by Li and

Milenkovic [43] brieﬂy described in Section 2.2. Their hybrid algorithm changes between

two modes, using the TT algorithm to ﬁnd locally optimal solutions and using the LP-based

compaction routines to legalize these solutions if possible. They also use NFPs in new ways to

speed up various calculations.

As mentioned in the introduction, unpublished work was done by Egeblad et al. [28] in

2001. This was a result of an 8 week project and it was the ﬁrst attempt of applying Guided

Local Search (GLS) to the nesting problem — based on a successful use of GLS by Færø et al.

for the rectangular packing problem in two and three dimensions. A very fast neighborhood

search for translation was presented and the results were very promising (better than those

published at the time).

2.6 Commercial solvers

The commercial interest in the nesting problem is probably even greater than the academical

interest. Their motivation is naturally that large sums can be saved if a bit of computing

time can spare the use of expensive materials. A quick search of the Internet revealed the

commercial applications presented in Table 2.1.

Although quite a few of the solvers are available as demo programs, it is very diﬃcult to

obtain information about the solution methods applied. Exceptions are the two ﬁrst solvers in

the list. 2NA is developed by Boeing and they describe their solution method on a homepage.

It is based on combining stencils to form larger stencils with little waste. These are packed

using methods applied to rectangular packing problems. It is fast, but it is probably not among

the best regarding solution quality.

AutoNester is based on the work done by Heistermann and Lengauer [37] and Heckmann

and Lengauer [35]. It is actually two diﬀerent libraries called AutoNester-T (textile) and

AutoNester-L (leather) using two very diﬀerent solution methods. We believe the nesting

algorithm in AutoNester-T using SA to be one of the best algorithms in use both regarding

speed and quality (also see Section 8.1.8 for benchmarks).

The Nesting Problem 2.7. 3D nesting

Package name Homepage

2NA http://www.boeing.com/phantom/2NA/

AutoNester http://www.gmd.de/SCAI/opt/products/index.html

NESTER http://www.nestersoftware.com/

Nestlib http://www.geometricsoftware.com/geometry_ct_nestlib.htm

OPTIMIZER http://www.samtecsoft.com/anymain.htm

MOST 2D http://www.most2d.com/main.htm

PLUS2D http://www.nirvanatec.com/nesting_software.html

Pronest/Turbonest http://www.mtc-limited.com/products.html

radpunch http://www.radan.com/radpunch.htm

SigmaNEST http://www.sigmanest.com/

SS-Nest/QuickNest http://www.striker-systems.com/ssnest/proddesc.htm

Table 2.1: A list of commercial nesting solvers found on the Internet. Most of them are

intended for metal blank nesting.

2.7 3D nesting

The nesting problem can be generalized to three dimensions, but the literature and commercial

interest for this problem is not overwhelming. The exception is the simpler problem of packing

boxes in a container. There are several reasons for this lack of interest. First of all, the problem

is even harder than the two dimensional variant which is hard enough as it is. Secondly, the

problem seems to have fewer practical applications.

Recently, new technologies have emerged which could beneﬁt from solutions to a 3D gen-

eralization of the nesting problem. This is especially due to the concept of rapid prototyping

which is an expression used about physical prototypes of 3D computer models needed in the

early design/test phases of new products (anything from kitchen utensils to toys). It is also

called 3D free-form cutting and packing.

A survey of various rapid prototyping technologies is given by Yan and Gu [58]. One of

these technologies, selective laser sintering process, is depicted in Figure 2.5. The idea is to

build up the object(s) by adding one very thin layer at the time. This is done by rolling out

a thin layer of powder and then sinter (heat) the areas/lines which should be solid by the

use of a laser. The unsintered powder supports the objects build and therefore no pillars or

bridges have to be made to account for gravitational eﬀects. This procedure can be quite slow

(hours) and since the time required for the laser is signiﬁcantly less than the time required for

preparing a layer of powder, it will be an advantage to pack as many objects as possible into

one run.

A few attempts have been done to solve the 3D nesting problem and a short survey has

been made by Osogami [52]. Most of the limited number of articles mentioned in this survey

are also brieﬂy described in the following paragraphs.

Ikonen et al. [39] (1997) is responsible for one of the earliest approaches to the nesting

problem. They chose to use a genetic algorithm and although the title refers to “non-convex

objects” then the actual implementation only handle solid blocks (or bounding boxes for more

complex objects), but they claim the results to be promising. The examples are quite small

and no benchmarks or data are available. They do handle rotation, but it is limited to 24

2.7. 3D nesting The Nesting Problem

Scanning mirror

Laser

Levelling roller

Powder cartridge

Powder

Figure 2.5: An example of a typical machine for rapid prototyping. The powder is added one

layer at the time and the laser is used to sinter what should be solidiﬁed to produce the objects

wanted.

orientations (45 degree increments). In their conclusions they state that it should be considered

to use a hill-climbing method to get the genetic algorithm out of local minima.

The approach by Cagan et al. [13] is more convincing. They opt for simulated annealing

as their meta heuristic approach and they allow both translation and rotation. They also

handle various optimization objectives e.g. taking routing lengths into account. Intersection is

allowed as part of the solution process and the calculation of intersection volumes is done by

using octree decompositions which closely relates a hierarchical raster model for 2D nesting.

The decompositions are done at diﬀerent levels of resolution to speed up calculations. Each

level uses 8 squares per square in the previous level. This means that level n uses 8

n−1

squares.

The level of precision follows the temperature in the annealing (low temperature requires high

precision since only small moves are done). The experiments focused on packing are done with

a container of ﬁxed size and a number of objects, and the solutions involve overlap which is

given in percent. They pack cubes and cog wheels clearly showing that the algorithm works

as intended.

The SA approach was an example of a relaxed placement method applied to 3D nesting.

Dickinson and Knopf [18, 17] use a legal placement method in their algorithm and as most 2D

algorithms in this category it is a sequential placement algorithm. No backtracking is done and

the sequence is determined by a measure of best ﬁt. This measure is also usable for 2D nesting

and was mentioned at the end of Section 2.2. It is a metric which evaluates the compactness

of the remaining free space in an unﬁnished placement. The best free space is in the form of a

sphere (a circle in 2D). Each stencil is packed at a local minimum with respect to this metric.

How this minimum is found is not described in detail, but in later work [19] SA is used for this

剩余108页未读，继续阅读

CoolCodingMan

粉丝: 141
资源: 21

高效求解嵌套问题的局部搜索算法

variable neighborhood search for the second type of two-sided assembly line balancing problem

Adaptive neighborhood search for nurse rostering

最新的元启发式优化算法有哪些

σ can be determined by the standard deviation of the homogeneous area near the patch window neighborhood, and the size of this area is √n j + 2× √n j + 2 in this work.这句话什么意思

帮我注释代码Algorithm 1: Adaptive Large Neighborhood search 1 Initialization: 2 s← InitialSolution (), s*←s; 3 ρ← InitialWeights(); 4 Ω← InitialScores(); 5 ν← InitialAttempts(); 6 While stop criteria not met do 7 Select neighborhood n ∈ N using ρ;

点云测地线fastmarching代码

最新资源