An efficient placement heuristic for three-dimensional rectangular packing

By embodying the spirit of “gold corner, silver side and strawy void” directly on the candidate packing place such that the searching space is reduced considerably, and by utilizing the characteristic of weakly heterogeneous problems that many items are in the same size, a fit degree algorithm (FDA) is proposed for solving a classical 3D rectangular packing problem, container loading problem. Experiments show that FDA works well on the complete set of 1500 instances proposed by Bischoff, Ratcliff and Davies. Especially for the 800 difficult strongly heterogeneous instances among them, FDA outperforms other algorithms with an average volume utilization of 91.91%, which to our knowledge is 0.45% higher than current best result just reported in 2010.     

A new heuristic recursive algorithm for the strip rectangular packing problem

A fast and new heuristic recursive algorithm to find a minimum height for two-dimensional strip rectangular packing problem is presented. This algorithm is mainly based on heuristic strategies and a recursive structure, and its average running time is T(n)=θ(n³)$T(n)=\theta (n^3)$. The computational results on a class of benchmark problems have shown that this algorithm not only finds shorter height than the known meta-heuristic ones, but also runs in shorter time. Especially for large test problems, it performs better.     

An efficient deterministic heuristic for two-dimensional rectangular packing

This paper proposes a deterministic heuristic, a best fit algorithm (BFA), for solving the NP-hard two-dimensional rectangular packing problem to maximize the filling rate of a rectangular sheet. There are two stages in this new approach: the constructive stage and the tree search stage. The former aims to rapidly generate an initial solution by employing the concepts of action space and fit degree in evaluating different placements. The latter seeks to further improve the solution and searches for promising placements by a partial tree search procedure. We then compare BFA with other approaches in terms of solution quality and computing time. We carry out computational experiments on two sets of well-known benchmark instances, C21 proposed by Hopper and Turton, and N13 proposed by Burke et al. BFA gained an average filling rate of 100% for the C21 instances within short times, indicating that all the layouts obtained are optimal. To the best of our knowledge, this is the first time that optimal layouts on all the 21 instances were obtained by a deterministic algorithm. As for the N13 instances, to date, researchers have found optimal solutions to the first three instances, whereas BFA solved seven, including the first three, within a reasonable period. An additional work is to adapt BFA to solve a relevant problem, the constrained two-dimensional cutting (or packing) problem (CTDC). Though BFA is not for the CTDC in the original design such that some specific characteristics of CTDC are not considered, the adapted algorithm still performed well on 21 public CTDC instances.     

一种高效的矩形套裁排样的带填充排样算法

提出一种带填充排样算法,实现矩形毛坯套裁排样。该算法首先用水平剪切线将板材分层,每层的宽度和板材宽度相同,高度和层最左端的主毛坯高度相同;通过调用两个递归过程确定最优排样方式,第一个过程确定每层左端的主毛坯,第二个过程确定层右端区域的毛坯排列方式。采用分支定界技术缩小搜索空间。实验计算结果说明所述算法比文献中最近报道的几种算法都有效。     

矩形件三阶段带排样问题的遗传算法

采用混合遗传算法求解矩形件带排样问题,采用三阶段排样方式以满足特定的约束或简化切割工艺。改进遗传算子,在变异操作之后使用调整操作,以进一步简化得到的排样方案。在初始种群构造时,根据矩形件的特性采用一些简单有效的方法,使结果更好更快地收敛。实验结果表明方法对解决这类问题是有效的。     

一种求解二维矩形Packing问题的拟人型全局优化算法

针对二维矩形Packing问题,提出了基于占角动作的基本算法。以基本算法为基础,提出了三阶段优化的拟人型全局优化算法。在第一阶段生成初始布局。在第二阶段交替调用邻域搜索子程序和跳坑策略子程序对矩形块的优先级排序进行优化。邻域搜索采用交换式和插入式两种邻域结构,避免单一邻域结构的局限性。当搜索遇到局部最优解时,采用跳坑策略子程序跳出局部最优解,将搜索引向有希望的区域。在第三阶段调用优美度枚举子程序对占角动作的选择作进一步优化。提出了两条优度定理。对于六组benchmark测试用例的实验结果表明,算法的整体表现优于当前文献中的先进算法。针对矩形块方向固定的情形,算法对zdf6和zdf7两个问题实例得到了比已有文献记录更优的布局。     

A heuristic algorithm for optimal placement of rectangular objects

The problem of partitioning a two-dimensional area into pieces having certain sizes with a minimum of wasted space is very important, especially in packing components tightly in the manufacture of very large-scale integrated circuits. The purpose of this paper is to examine the problem of placing rectangular objects in a rectangular area so as to minimize the wasted space, from the viewpoint of establishing maximum empty rectangles rather than the standard linear-programming approach. A comparison of our results with those of the Steudel [5] is reported. Empirical comparisons of our results indicate that our algorithm is very simple and efficient.     

A least wasted first heuristic algorithm for the rectangular packing problem

The rectangular packing problem is to pack a number of rectangles into a single large rectangular sheet so as to maximize the total area covered by the rectangles packed. The paper first presents a least wasted first strategy which evaluates the positions used by the rectangles. Then a random local search is introduced to improve the results and a least wasted first heuristic algorithm (LWF) is further developed to find a desirable solution. Twenty-one rectangular-packing instances are tested by the algorithm developed, the experimental results show that the presented algorithm can achieve an optimal solution within reasonable time and is fairly efficient for dealing the rectangular packing problem. LWF still performs well when it is extended to solve zero-waste and non-zero-waste strip packing instances.     

Heuristic for the rectangular strip packing problem with rotation of items

This paper presents a heuristic algorithm for the rectangular strip packing problem, where a set of rectangular items are packed orthogonally into a strip of definite width and infinite height, so as to minimize the required height. The items cannot overlap and rotation by 90 degrees is allowed. The solution contains several sections. The algorithm is based on a sequential grouping and value correction procedure that considers multiple candidate solutions. It generates each next section using a subset of the remaining items and then corrects the values of the included items. The algorithm is used to solve 13 groups of benchmark instances. It is able to improve the solution quality for all groups.     

A recursive branch-and-bound algorithm for the rectangular guillotine strip packing problem

A heuristic recursive algorithm for the two-dimensional rectangular strip packing problem is presented. It is based on a recursive structure combined with branch-and-bound techniques. Several lengths are tried to determine the minimal plate length to hold all the items. Initially the plate is taken as a block. For the current block considered, the algorithm selects an item, puts it at the bottom-left corner of the block, and divides the unoccupied region into two smaller blocks with an orthogonal cut. The dividing cut is vertical if the block width is equal to the plate width; otherwise it is horizontal. Both lower and upper bounds are used to prune unpromising branches. The computational results on a class of benchmark problems indicate that the algorithm performs better than several recently published algorithms.     

求解二维正交矩形布局问题的动态填空启发式算法

为更高效解决二维正交矩形布局问题,建立该问题的数学模型,改进BL算法规则;为寻找布局过程中的空余平面,建立了新颖的图形矩阵化理论。最后提出一种动态填空（DFB）启发式算法,制定了四条动态调整机制,结合遗传算法对该问题进行求解。大量算例测试显示：DFB算法可达到100%的平面利用率,极大提高了BL算法的效率,并且可以适用于大规模布局问题。     

An improved skyline based heuristic for the 2D strip packing problem and its efficient implementation

The best-fit heuristic by Burke et al. (2004) is a simple but effective approach for the 2D Strip Packing (2DSP) problem. In this paper, we propose an improved best-fit heuristic for the 2DSP. Instead of selecting the rectangle with the largest width, we use the fitness number to select the best rectangle fitting into the gap. An efficient implementation pattern with a time complexity of O(n log n) (n is the number of rectangles) is provided for the improved best-fit heuristic. A simple random local search is used to improve the results by trying different sequences. The experiment on the benchmark test sets shows that the final approach is both effective and efficient.     

An algorithm for the strip packing problem using collision free region and exact fitting placement

The irregular shape packing problem is approached. The container has a fixed width and an open dimension to be minimized. The proposed algorithm constructively creates the solution using an ordered list of items and a placement heuristic. Simulated annealing is the adopted metaheuristic to solve the optimization problem. A two-level algorithm is used to minimize the open dimension of the container. To ensure feasible layouts, the concept of collision free region is used. A collision free region represents all possible translations for an item to be placed and may be degenerated. For a moving item, the proposed placement heuristic detects the presence of exact fits (when the item is fully constrained by its surroundings) and exact slides (when the item position is constrained in all but one direction). The relevance of these positions is analyzed and a new placement heuristic is proposed. Computational comparisons on benchmark problems show that the proposed algorithm generated highly competitive solutions. Moreover, our algorithm updated some best known results.     

A new heuristic algorithm for rectangle packing

The rectangle packing problem often appears in encasement and cutting as well as very large-scale integration design. To solve this problem, many algorithms such as genetic algorithm, simulated annealing and other heuristic algorithms have been proposed. In this paper, a new heuristic algorithm is recommended based on two important concepts, namely, the corner-occupying action and caving degree. Twenty-one rectangle-packing instances are tested by the algorithm developed, 16 of which having achieved optimum solutions within reasonable runtime. Experimental results demonstrate that the algorithm developed is fairly efficient for solving the rectangle packing problem.     

矩形件优化排样的混合启发式方法

提出一种启发式递归与遗传算法相结合的混合启发式算法求解矩形件优化排样问题。首先给出一种启发式递归算法,利用该算法逐个从待排矩形件中生成局部利用率高的条料,直到所有待排矩形件均生成条料;利用遗传算法全局搜索能力强的特点,对这些条料序进行搜索重组,使其所用的板材数最少;最后再次利用遗传算法,对条料生成之前的矩形件种类序进行全局最优搜索,使总的板材利用率达到了最大。对两个典型实际算例进行计算,并与相关文献比较,结果表明了该算法的有效性。     

Bidirectional evolutionary heuristic for the minimum vertex-cover problem

In this study, we have solved the minimum vertex-cover problem, NP-hard, by the means of genetic algorithms (GA). In prior studies, initial population on which GA iteratively run, was created randomly. However, we have improved this technique to create initial population and the population created has some useful properties such as decreasing the number of iterations of GA algorithm and gets rid of diversity problem, local solution problem. Initially, one chromosome is created and then the inversion of this chromosome is taken as another chromosome. If it is required to create an initial population with large set of chromosomes, then randomly created chromosomes can be divided into desired partitions and other chromosomes can be obtained by the complement of each partition at a time. Search is handled in bi-directional manner, and the initial population contains both ends of solution space.     

A heuristic for packing boxes into a container

Given a container of known dimensions and a collection of rectangular boxes with known dimensions and number of boxes of each type, the problem is to find suitable positions for placing the boxes in the container in such a way that all the boxes can be fitted in. A heuristic for computer or manual operation is described.     

求解矩形布局问题的自适应算法

矩形布局问题属于NP-Hard 问题,其求解算法多为启发式算法。该文侧重 于构造布局求解算法中定位函数（规则）的优化,将模拟退火算法的思想融入到遗传算法中, 提出了求解矩形布局问题的自适应算法,其利用自适应交叉、变异及接收劣质解的概率等方 法对定位函数中各参数进行优化。算法通过两种方式确定初始种群的数目,具有较强的适应 性。在算法搜索的后期,利用差异性较大的个体进行交叉操作,从而保持种群的多样性。最 后通过实例证明了该算法能够很好的应用于矩形布局问题的求解。     

Approximation algorithms for orthogonal packing problems for hypercubes

Orthogonal packing problems are natural multidimensional generalizations of the classical bin packing problem and knapsack problem and occur in many different settings. The input consists of a set I={_r1,…,_rn}$I=\{r_1,\dots ,r_n\}$ of d$d$-dimensional rectangular items _ri=(_ai,1,…,_ai,d)$r_i=(a_{i,1},\dots ,a_{i,d})$ and a space Q$Q$. The task is to pack the items in an orthogonal and non-overlapping manner without using rotations into the given space. In the strip packing setting the space Q$Q$ is given by a strip of bounded basis and unlimited height. The objective is to pack all items into a strip of minimal height. In the knapsack packing setting the given space Q$Q$ is a single, usually unit sized bin and the items have associated profits _pi$p_i$. The goal is to maximize the profit of a selection of items that can be packed into the bin.