Search algorithm and optimization algorithm in packing problem

Brief introduction on 2D irrgular Packing.

Introduction

This problem is a class of the cutting and packing problems and it is a combinatorial optimization problem that deals with various types of polygons including irregular or non-convex polygons, convex polygons, as well as rectangles.

The problem involves placing a set of input polygons on a rectangular sheet or container of a fixed width (W) and variable length (L) ensuring that there are no overlapping polygons or protruding from the con- tainer. Using the typology of Wäscher, Haußner, and Schumann (2007), this problem is categorized as the two-dimensional irregular open dimensional problem (ODP).

The main objective is to maximize the container utilization or to minimize its length while accommodating all polygons inside. The high utilization is greatly desirable in industry so as to minimize the waste material since the material cost is often the major part of the production cost.

The nesting problem has a few variations relying on rotations of polygons: (1) rotations of any angle are allowed, (2) a finite number of angles are allowed, and (3) no rotation is allowed. In some industries such as textile or clothing industry, there is a restriction on the shape rotation due to the fabric drawing patterns and intrin- sic characteristics, so it is limited to 0° or 180°. The nesting problem is known to be NP-hard even without rotation (Nielsen & Odgaard, 2003).

In the industrial environments this problem is usually tackled by experienced workers who build the nesting layout and this may be with the aid of CAD systems. The quality and utilization produced by those skilled workers is high when it is compared with that produced from the available commercial software packages. A list of semi-automatic commercial solutions is available in Hopper (2000) and Nielsen and Odgaard (2003).

Record

Datasets

Available online at EURO Special Interest Group on Cutting and Packing(ESICUP) website.

Formulation

Overlap minimization problem

Shape representation

Difficulties

1. Pure local search approaches frequently end up entrapped in local optimal solutions, since they can only move to better solutions in the neighbourhood.

Basic geometry concept

No fit polygon(NFP)

NFP is introduce in another article.

Inner fit polygon (IFP)

New added piece need be put inside the constrain rectangle, so we should compute the feasible area for this piece. We can use the same way choose a reference point and slide the new piece around rectangle inner. Then, the NFP’s intersection boundary which inside the inner rectangle is the valid positions.

This means that we need to compute O(nlogn) NFPs to complete the first packing. While there are ways to mitigate this, we take the brute-force approach which has good properties for the optimization algo.

How to accommodate stencils

How to find most suitabel position

Dominate Point

Dominate point is proposed in A new approach for sheet nesting problem using guided cuckoo search and pairwise clustering. It is mainly used in convex and concave combination.

In this method, we need compute the no fit polygon first. Then, we should get the convex envelop and compute the distance from all endpints of NFP to convex envelope’s edges. In many situation, DP will grasp the highest utilization ratio.

Extend polygon fit degree

There is no dominate point in convex shape and convex shape’s combination. In many case, even if it’s convex shape and concave shape’s combination, dominate point will not achieve the best utilization ratio.

Fit degree is put forward for this situation. We need compute the extend polygons first and the intersection’s area of extend polygons shows the fit degree.

The position where can hold the highest fit degree will always achieve the highest utilization ratio.

Slides By You Lin

1. Initial Solution

1.1 Bottom left fill

A New Bottom-Left-Fill Heuristic Algorithm for the Two-Dimensional Irregular Packing Problem

1.2 Lowest gravity center

Algorithm for 2D irregular-shaped nesting problem based on the NFP algorithm and lowest-gravity-center principle.

2. Local Search-Overlap remove

2.1 Simple local search

Local search in packing problem always works by change the position of a strip regardless of the overlap. Then we should choose the position which can achieve the lowest overlap area,

2.2 Fast neighborhood search

Fast neighborhood search for two- and three-dimensional nesting problems, Jens Egeblad, Benny K. Nielsen *, Allan Odgaard

2.3 Cuckoo search

A type of local search.

Reference: A new approach for sheet nesting problem using guided cuckoo search and pairwise clustering, Ahmed Elkeran

2.4 Simulating Annealing

A simulated annealing approachto the nesting problem in the textile manufacturing industry

Reason: Pure local search approaches frequently end up entrapped in local optimal solutions, since they can only move to better solutions in the neighbourhood.

How: Simulated annealing can be seen as an evolution of those approaches, by allowing some controlled uphill movements, in order to achieve global optimality. Accepting a movement to a worse solution depends on a control parameter (the temperature) and on the magnitude of the variation of the objective function, i.e. how worse the solution is.

2.5 Extended Local Search

2.6 Iterated local search

An iterated local search algorithm based on nonlinear programming for the irregular strip packing problem

Similar to other search approach

It apple

3. Order arrangement

3.1 DJD Search

How to find the next

3.2 Pairwise combination

3.3 Genetic Algorithm

Source: Algorithm for 2D irregular-shaped nesting problem based on the NFP algorithm and lowest-gravity-center principle

To achieve high quality nesting sequence, GA is adopted in this paper. Some of its important features are listed below.

Gene encoding of the solution

Because the proposed lowest-gravity-center placement principle can determine the gravity center and rotation angle of a piece (Fig.4), there is no need to encode rotation angle into the chromosome, the only thing we need to encode is the nesting sequence (permutation order).

Initialization

The first generation of individuals has great influence on the final GA result. To get a set of well-defined initial individuals, sorted-by-area nesting permutation is used as the first individual, and then other individuals are created by mutations of the first individual with all these individuals forming the first generation.

Fitness function and fitness scaling

The height of the remaining containing region is taken as the fitness, a fitness linear scaling function is adopted to scale the fitness value to a reasonable range:

here $f$ is the original fitness and $f ′$ is the output scaled fitness with

Because proportional selection method is adopted in this GA, some individuals with very low fitness will be rejected too early, which may lead to premature convergence, so σ is added to the fitness function to avoid this kind of rejection.

Crossover

OX (order-crossover (Davis, 1985)) crossover is adopted in this paper. Suppose one parent is (5, 2, 3, 7, 6, 1, 4) and another parent is (4, 6, 2, 1, 3, 5, 7), the OX crossover procedure is illustrated in Fig.7.

Mutation

Mutation occurs after crossover and is applied to newly generated child-individuals. Here mutation is used to exchange two numbers in the chromosome, the mutation probability is 0.1~0.2. Sometimes two segments of the chromosome can also be exchanged, in such case the mutation probability should be de- creased since the chromosome is greatly changed.

Exact Algorithm

Branch and Bound

A branch & bound algorithm for cutting and packing irregularly shaped pieces R. Alvarez-Valdes n, A. Martinez, J.M. Tamarit