Improved local search algorithms for the rectangle packing problem with general spatial costs

The rectangle packing problem with general spatial costs is to pack given rectangles without overlap in the plane so that the maximum cost of the rectangles is minimized. This problem is very general, and various types of packing problems and scheduling problems can be formulated in this form. For this problem, we have previously presented local search algorithms using a pair of permutations of rectangles to represent a solution. In this paper, we propose speed-up techniques to evaluate solutions in various neighborhoods. Computational results for the rectangle packing problem and a real-world scheduling problem exhibit good prospects of the proposed techniques.     

Local search algorithms for the rectangle packing problem with general spatial costs

We propose local search algorithms for the rectangle packing problem to minimize a general spatial cost associated with the locations of rectangles. The problem is to pack given rectangles without overlap in the plane so that the maximum cost of the rectangles is minimized. Each rectangle has a set of modes, where each mode specifies the width and height of the rectangle and its spatial cost function. The spatial costs are general piecewise linear functions which can be non-convex and discontinuous. Various types of packing problems and scheduling problems can be formulated in this form. To represent a solution of this problem, a pair of permutations of n rectangles is used to determine their horizontal and vertical partial orders, respectively. We show that, under the constraint specified by such a pair of permutations, optimal locations of the rectangles can be efficiently determined by using dynamic programming. The search for finding good pairs of permutations is conducted by local search and metaheuristic algorithms. We report computational results on various implementations using different neighborhoods, and compare their performance. We also compare our algorithms with other existing heuristic algorithms for the rectangle packing problem and scheduling problem. These computational results exhibit good prospects of the proposed algorithms. Key words.rectangle packing – sequence pair – general spatial cost – dynamic programming – metaheuristicsMathematics Subject Classification (1991):20E28, 20G40, 20C20     

货物尺寸相同的2维装箱问题的等价类(英文)

在生产与储运领域,把小长方体货物（盒子）装入大长方体箱子是一项重要的工作.本文涉及的问题是:把相同尺寸（a×b×c）的盒子装到一个箱子X×Y×Z中,使所装入箱子的盒子数量为最大.由于某些条件的限止,有时要求货物只能按一个重力方向进行装箱,从而使装箱问题变为把尺寸相同的2维盒子（a×b）填装到一个2维箱子X×Y中.本文讨论当盒子尺寸（a×b包括 b×a）给定,箱子尺寸充分大时,在本文所给的等价意义下,共有多少种互不等价的箱子X×Y.     

An effective quasi-human based heuristic for solving the rectangle packing problem

In this paper, we introduce an effective deterministic heuristic, Less Flexibility First, for solving the classical NP-complete rectangle packing problem. Many effective heuristics implemented for this problem are CPU-intensive and non-deterministic in nature. Others, including the polynomial approximation methodology [J. Assoc. Comput. Mach. 32 (1) (1985) 130] are too laborious for practical problem sizes. The technique we propose is inspired and developed by enhancing some rule-of-thumb guidelines resulting from the generation-long work experience of human professionals in ancient days. Although the Less Flexibility First heuristic is a deterministic algorithm, the results are very encouraging. This algorithm can consistently produce packing densities of around 99% on most randomly generated large examples. As compared with the recent results of a well known simulated annealing based Rectangle Packing (RP) algorithm [IEEE Trans. Computer-aided Design Integrated Circuits Systems 17 (1) (1998) 60], the results are much better both in less dead space² (4% vs 6.7%) and much less CPU time (9.57 vs 331.78 seconds). Experimenting our heuristics on a public rectangle packing data set covering instances of 16–97 rectangles, the average unpack ratio is quite satisfactory (0.92% for bounding boxes limited to be optimum and 2.68% for the completed packing), while most cases spend only a few minutes in CPU time.     

Dynamic multi-dimensional bin packing

A natural generalization of the classical online bin packing problem is the dynamic bin packing problem introduced by Coffman et al. (1983) [7]. In this formulation, items arrive and depart and the objective is to minimize the maximal number of bins ever used over all times. We study the oriented multi-dimensional dynamic bin packing problem for two dimensions, three dimensions and multiple dimensions. Specifically, we consider dynamic packing of squares and rectangles into unit squares and dynamic packing of three-dimensional cubes and boxes into unit cubes. We also study dynamic d-dimensional hypercube and hyperbox packing. For dynamic d-dimensional box packing we define and analyze the algorithm NFDH for the offline problem and present a dynamic version. This algorithm was studied before for rectangle packing and for square packing and was generalized only for multi-dimensional cubes. We present upper and lower bounds for each of these cases.     

Optimal rectangle packing

We consider the NP-complete problem of finding an enclosing rectangle of minimum area that will contain a given a set of rectangles. We present two different constraint-satisfaction formulations of this problem. The first searches a space of absolute placements of rectangles in the enclosing rectangle, while the other searches a space of relative placements between pairs of rectangles. Both approaches dramatically outperform previous approaches to optimal rectangle packing. For problems where the rectangle dimensions have low precision, such as small integers, absolute placement is generally more efficient, whereas for rectangles with high-precision dimensions, relative placement will be more effective. In two sets of experiments, we find both the smallest rectangles and squares that can contain the set of squares of size 1×1, 2×2,…,N×N, for N up to 27. In addition, we solve an open problem dating to 1966, concerning packing the set of consecutive squares up to 24×24 in a square of size 70×70. Finally, we find the smallest enclosing rectangles that can contain a set of unoriented rectangles of size 1×2, 2×3, 3×4,…,N×(N+1), for N up to 25.     

Construction heuristics for two-dimensional irregular shape bin packing with guillotine constraints

The paper examines a new problem in the irregular packing literature that has many applications in industry: two-dimensional irregular (convex) bin packing with guillotine constraints. Due to the cutting process of certain materials, cuts are restricted to extend from one edge of the stock-sheet to another, called guillotine cutting. This constraint is common place in glass cutting and is an important constraint in two-dimensional cutting and packing problems. In the literature, various exact and approximate algorithms exist for finding the two dimensional cutting patterns that satisfy the guillotine cutting constraint. However, to the best of our knowledge, all of the algorithms are designed for solving rectangular cutting where cuts are orthogonal with the edges of the stock-sheet. In order to satisfy the guillotine cutting constraint using these approaches, when the pieces are non-rectangular, practitioners implement a two stage approach. First, pieces are enclosed within rectangle shapes and then the rectangles are packed. Clearly, imposing this condition is likely to lead to additional waste. This paper aims to generate guillotine-cutting layouts of irregular shapes using a number of strategies. The investigation compares three two-stage approaches: one approximates pieces by rectangles, the other two approximate pairs of pieces by rectangles using a cluster heuristic or phi-functions for optimal clustering. All three approaches use a competitive algorithm for rectangle bin packing with guillotine constraints. Further, we design and implement a one-stage approach using an adaptive forest search algorithm. Experimental results show the one-stage strategy produces good solutions in less time over the two-stage approach.     

An efficient deterministic optimization approach for rectangular packing problems

The rectangular packing problem aims to seek the best way of placing a given set of rectangular pieces within a large rectangle of minimal area. Such a problem is often constructed as a quadratic mixed-integer program. To find the global optimum of a rectangular packing problem, this study transforms the original problem as a mixed-integer linear programming problem by logarithmic transformations and an efficient piecewise linearization approach that uses a number of binary variables and constraints logarithmic in the number of piecewise line segments. The reformulated problem can be solved to obtain an optimal solution within a tolerable error. Numerical examples demonstrate the computational efficiency of the proposed method in globally solving rectangular packing problems.     

A two-stage intelligent search algorithm for the two-dimensional strip packing problem

This paper presents a two-stage intelligent search algorithm for a two-dimensional strip packing problem without guillotine constraint. In the first stage, a heuristic algorithm is proposed, which is based on a simple scoring rule that selects one rectangle from all rectangles to be packed, for a given space. In the second stage, a local search and a simulated annealing algorithm are combined to improve solutions of the problem. In particular, a multi-start strategy is designed to enhance the search capability of the simulated annealing algorithm. Extensive computational experiments on a wide range of benchmark problems from zero-waste to non-zero-waste instances are implemented. Computational results obtained in less than 60 seconds of computation time show that the proposed algorithm outperforms the supposedly excellent algorithms reported recently, on average. It performs particularly better for large instances.     

Multidimensional dual-feasible functions and fast lower bounds for the vector packing problem

In this paper, we address the 2-dimensional vector packing problem where an optimal layout for a set of items with two independent dimensions has to be found within the boundaries of a rectangle. Many practical applications in areas such as the telecommunications, transportation and production planning lead to this combinatorial problem. Here, we focus on the computation of fast lower bounds using original approaches based on the concept of dual-feasible functions.     

The general routing problem polyhedron: Facets from the RPP and GTSP polyhedra

In this paper we study the polyhedron associated with the General Routing Problem (GRP). This problem, first introduced by Orloff in 1974, is a generalization of both the Rural Postman Problem (RPP) and the Graphical Traveling Salesman Problem (GTSP) and, thus, is NP -hard. We describe a formulation of the problem such that from every non-trivial facet-inducing inequality for the RPP and GTSP polyhedra, we obtain facet-inducing inequalities for the GRP polyhedron. We describe a new family of facet-inducing inequalities for the GRP, the honeycomb constraints, which seem to be very useful for solving GRP and RPP instances. Finally, new classes of facets obtained by composition of facet-inducing inequalities are presented.     

A new exact method for the two-dimensional orthogonal packing problem

The two-dimensional orthogonal packing problem (2OPP) consists in determining if a set of rectangles (items) can be packed into one rectangle of fixed size (bin). In this paper we propose two exact algorithms for solving this problem. The first algorithm is an improvement on a classical branch&bound method, whereas the second algorithm is based on a new relaxation of the problem. We also describe reduction procedures and lower bounds which can be used within enumerative methods. We report computational experiments for randomly generated benchmarks which demonstrate the efficiency of both methods: the second method is competitive compared to the best previous methods. It can be seen that our new relaxation allows an efficient detection of non-feasible instances.     

非线性系统高维特征量的稳健投影寻踪建模

针对非线性系统高维特征量的识别与提取问题,本文给出了稳健投影寻踪建模的方法。应用此方法,对试飞实测数据进行处理,建立了飞机发动机低压转子转速与其余六个特征量的稳健投影寻踪模型。上述模型不仅揭示了该非线性系统多个特征量之间关系,而且模型精度高,达到了实际工程要求。     

An effective recursive partitioning approach for the packing of identical rectangles in a rectangle

In this work, we deal with the problem of packing (orthogonally and without overlapping) identical rectangles in a rectangle. This problem appears in different logistics settings, such as the loading of boxes on pallets, the arrangements of pallets in trucks and the stowing of cargo in ships. We present a recursive partitioning approach combining improved versions of a recursive five-block heuristic and an L-approach for packing rectangles into larger rectangles and L-shaped pieces. The combined approach is able to rapidly find the optimal solutions of all instances of the pallet loading problem sets Cover I and II (more than 50?000 instances). It is also effective for solving the instances of problem set Cover III (almost 100?000 instances) and practical examples of a woodpulp stowage problem, if compared to other methods from the literature. Some theoretical results are also discussed and, based on them, efficient computer implementations are introduced. The computer implementation and the data sets are available for benchmarking purposes.     

The Three-Dimensional Pallet Chart: An Analysis of the Factors Affecting the Set of Feasible Layouts for a Class of Two-Dimensional Packing Problems

The two-dimensional orthogonal packing problem of packing identical rectangles into a large containing rectangle is important in pallet loading and has recently received much attention in O.R. publications. In this paper, we examine the conditions under which the set of feasible layouts remains unchanged and show that these conditions can be represented by a series of planes in three-dimensional space. We call this representation the three-dimensional pallet chart because it is an extension of the two-dimensional pallet charts presently used in many practical situations. The strength of this result is demonstrated by three examples of its use. Accurate two-dimensional charts are produced from the three-dimensional version with a minimum of calculation, and a complete sensitivity analysis to changes in box and pallet dimensions can be carried out visually by viewing the chart at different angles. Finally, the result is used to generate a new procedure for determining the maximum number of rectangles which can be fitted. This method is shown to be accurate for over 90% of observations in a random sample of 5000—an improvement of 20% over previous methods.     

A tabu search algorithm for a two-dimensional non-guillotine cutting problem

In this paper we study a two-dimensional non-guillotine cutting problem, the problem of cutting rectangular pieces from a large stock rectangle so as to maximize the total value of the pieces cut. The problem has many industrial applications whenever small pieces have to be cut from or packed into a large stock sheet. We propose a tabu search algorithm. Several moves based on reducing and inserting blocks of pieces have been defined. Intensification and diversification procedures, based on long-term memory, have been included. The computational results on large sets of test instances show that the algorithm is very efficient for a wide range of packing and cutting problems.     

A reduction approach for solving the rectangle packing area minimization problem

In the rectangle packing area minimization problem (RPAMP) we are given a set of rectangles with known dimensions. We have to determine an arrangement of all rectangles, without overlapping, inside an enveloping rectangle of minimum area. The paper presents a generic approach for solving the RPAMP that is based on two algorithms, one for the 2D Knapsack Problem (KP), and the other for the 2D Strip Packing Problem (SPP). In this way, solving an instance of the RPAMP is reduced to solving multiple SPP and KP instances. A fast constructive heuristic is used as SPP algorithm while the KP algorithm is instantiated by a tree search method and a genetic algorithm alternatively. All these SPP and KP methods have been published previously. Finally, the best variants of the resulting RPAMP heuristics are combined within one procedure. The guillotine cutting condition is always observed as an additional constraint. The approach was tested on 15 well-known RPAMP instances (above all MCNC and GSRC instances) and new best solutions were obtained for 10 instances. The computational effort remains acceptable. Moreover, 24 new benchmark instances are introduced and promising results are reported.     

A heuristic for the circle packing problem with a variety of containers

In this paper we present a heuristic algorithm based on the formulation space search method to solve the circle packing problem. The circle packing problem is the problem of finding the maximum radius of a specified number of identical circles that can be fitted, without overlaps, into a two-dimensional container of fixed size. In this paper we consider a variety of containers: the unit circle, unit square, rectangle, isosceles right-angled triangle and semicircle. The problem is formulated as a nonlinear optimization problem involving both Cartesian and polar coordinate systems.Formulation space search consists of switching between different formulations of the same problem, each formulation potentially having different properties in terms of nonlinear optimization. As a component of our heuristic we solve a nonlinear optimization problem using the solver SNOPT.Our heuristic improves on previous results based on formulation space search presented in the literature. For a number of the containers we improve on the best result previously known. Our heuristic is also a computationally effective approach (when balancing quality of result obtained against computation time required) when compared with other work presented in the literature.     

A hybrid genetic algorithm-heuristic for a two-dimensional orthogonal packing problem

In this paper we address a two-dimensional (2D) orthogonal packing problem, where a fixed set of small rectangles has to be placed on a larger stock rectangle in such a way that the amount of trim loss is minimized. The algorithm we propose hybridizes a placement procedure with a genetic algorithm based on random keys. The approach is tested on a set of instances taken from the literature and compared with other approaches. The computation results validate the quality of the solutions and the effectiveness of the proposed algorithm.     

Parallel greedy algorithms for packing unequal circles into a strip or a rectangle

Given a finite set of circles of different sizes we study the strip packing problem (SPP) as well as the Knapsack Problem (KP). The SPP asks for a placement of all circles within a rectangular strip of fixed width so that the variable length of the strip is minimized. The KP requires packing of a subset of the circles in a given rectangle so that the wasted area is minimized. To solve these problems some greedy algorithms were developed which enhance the algorithms proposed by Huang et al. (J Oper Res Soc 56:539–548, 2005). Furthermore, the new greedy algorithms were parallelized using a master slave approach. The resulting parallel methods were tested using the instances introduced by Stoyan and Yaskov (Eur J Oper Res 156:590–600, 2004). Additionally, two sets of 128 instances each for the SPP and for the KP were generated and results for these new instances are also reported.