A new heuristic algorithm for cuboids packing with no orientation constraints

The three-dimensional cuboids packing is NP-hard and finds many applications in the transportation industry. The problem is to pack a subset of cuboid boxes into a big cuboid container such that the total volume of the packed boxes is maximized. The boxes have no orientation constraints, i.e. they can be rotated by 90^°${90}^{°}$ in any direction. A new heuristic algorithm is presented that defines a conception of caving degree to judge how close a packing box is to those boxes already packed into the container, and always chooses a packing with the largest caving degree to do. The performance is evaluated on all the 47 related benchmarks from the OR-Library. Experiments on a personal computer show a high average volume utilization of 94.6% with an average computation time of 23 min for the strengthened A1 algorithm, which improves current best records by 3.6%. In addition, the top-10 A2 algorithm achieved an average volume utilization of 91.9% with an average computation time of 55 s, which also got higher utilization than current best records reported in the literature.     

An efficient heuristic algorithm for rectangle-packing problem

Rectangle-packing problem involves many industrial applications, such as shipping, timber cutting, very large scale integration (VLSI) floor planning, and so on. This problem has shown to be NP hard, and many algorithms such as genetic algorithm, simulated annealing and other heuristic algorithms are presented to solve it. Based on the wisdom and experience of human being, an efficient heuristic algorithm is proposed in this paper. Two group benchmarks are used to test the performance of the produced algorithm, 19 instances of first group and 3 instances of second group having achieved optimal solutions. The experimental results demonstrate that the presented algorithm is rather efficient for solving the rectangle-packing problem.     

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

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

求解矩形packing问题的贪心算法

在货物装载、木材下料、超大规模集成电路设计等工作中提出了矩形packing问题。对这一问题,国内外学者提出了诸如模拟退火算法、遗传算法及其它一些启发式算法等求解算法。该文利用人类的智慧及历史上形成的经验,提出了一种求解矩形packing问题的贪心算法。并对21个公开测试实例进行了实算测试,所得结果的平均面积未利用率为0.28%,平均计算时间为17.86s,并且还得到了其中8个实例的最优解。测试结果表明,该算法对求解矩形packing问题相当有效。     

求解矩形和圆形装填问题的最大穴度算法

在超大规模集成电路设计,裁缝裁剪布料,玻璃切割等工作中提出了矩形和圆形装填问题,即把不同大小的矩形块和圆饼装入一个矩形容器中,以最大化容器的面积利用率为优化目标。对这一问题,可采用模拟退火,遗传算法等国际流行算法进行求解,但这些方法计算时间较长,计算结果的优度也不甚理想。利用人类的智慧和经验,提出了一种求解此问题的最大穴度算法。并对3个随机生成的测试实例进行了实算测试。所得结果的平均面积利用率为90．80％,平均计算时阊为8．38s。测试结果表明,算法对求解矩形和圆形装填问题是行之有效的。     

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.     

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.     

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.     

基于两阶段排放算法的矩形件排样优化方法

针对矩形件排样问题,经典的最下左填充(BLF)算法易于出现区域浪费、原材料利用率低的缺点。对此,提出一种改进的两阶段排放算法。第一阶段利用BLF算法,第二阶段设计一个改进BLF排放算法以减小区域的浪费。再以矩形件排放顺序进行编码,利用两阶段排放算法解码,设计邻域搜索算法寻找最优解。通过已有文献的多个案例,对改进的算法进行实验验证,结果与BLF算法相比,原材料利用率能提高14%,证实了改进算法的有效性。     

不规则区域矩形件排样的一种改进算法

采用遗传算法解决不规则区域的矩形件带排样问题,用有序的带符号整数串作为初始种群个体,改善了初始个体解的质量.提出基于最低水平线的择优插入算法,同时考虑不规则区域的左右两端区域,选取最适合的零件进行填充,使零件排放紧凑,提高了材料的利用率.     

A new heuristic algorithm for the circular packing problem with equilibrium constraints

The circular packing problem with equilibrium constraints is an optimization problem about simplified satellite module layout design.A heuristic algorithm based on tabu search is put forward for solving this problem.The algorithm begins from a random initial configuration and applies the gradient method with an adaptive step length to search for the minimum energy configuration.To jump out of the local minima and avoid the search doing repeated work,the algorithm adopts the strategy of tabu search.In the pr...     

改进的双种群遗传算法在矩形件排样中的应用

在矩形件排样问题中,按照面积大小的顺序排放通常比随机排放效果要好,因此在遗传算法的随机初始的种群中加入部分按照面积大小排序的个体以达到加速收敛的目的。然而在同一个种群中,这部分个体适应度高,迭代前期快速扩散,使得种群多样性降低,导致遗传算法过早熟。针对此缺陷把随机个体作为一个种群,按照面积大小排序的个体作为另一个种群并采用特定的交叉方式保证此种群子代个体大体上按面积大小排序局部乱序。此外,针对最低水平线搜索算法搜索频率低的缺陷,增多了搜索的发生时机,实现更频繁的调整排序提高遗传算法局部搜索能力。实验结果表明了改进后算法的有效性。     

A hybrid simulated annealing metaheuristic algorithm for the two-dimensional knapsack packing problem

The rectangle knapsack packing problem is to pack a number of rectangles into a larger stock sheet such that the total value of packed rectangles is maximized. The paper first presents a fitness strategy, which is used to determine which rectangle is to be first packed into a given position. Based on this fitness strategy, a constructive heuristic algorithm is developed to generate a solution, i.e. a given sequence of rectangles for packing. Then, a greedy strategy is used to search a better solution. At last, a simulated annealing algorithm is introduced to jump out of the local optimal trap of the greedy strategy, to find a further improved solution. Computational results on 221 rectangular packing instances show that the presented algorithm outperforms some previous algorithms on average.     

Design of efficient packing system using genetic algorithm based on hyper heuristic approach

In practice the maximum usage of container space arises in many applications which is one of the crucial economical requirements that have a wide impact on good transportation. A huge amount of monetary infrastructure is spent by companies on packing and transportation. This study recommends that there exists a scope for further optimization which if implemented can lead to huge saving. In this paper, we propose a new hyper heuristic approach which automates the design process for packing of two dimensional rectangular blocks. The paper contributes to the literature by introducing a new search technique where genetic algorithm is coupled with the hyper heuristic to get the optimal or sub optimal solution at an acceptable rate. The results obtained show the benefits of hyper-heuristic over traditional one when compared statistically on large benchmark dataset at the 5% level of significance. Improvements on the solution quality with high filling rate up to 99% are observed on benchmark instances.     

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 heuristic algorithm for cube packing with time schedule

Packing problem has been proved to be an NP-hard problem. Many algorithms such as simulation annealing algorithm, genetic algorithm and other heuristic algorithms have been proposed to solve twodimensional and three-dimensional packing problem. To solve the cube packing problem with time schedule, this paper first introduces some concepts such as packing level, space distance and average neighbor birth order and then proposes a greedy algorithm. The algorithm tries every feasible corner greedily to calculat...     

A simple randomized algorithm for two-dimensional strip packing

Two-dimensional strip packing problem is to pack given rectangular pieces on a strip of stock sheet having fixed width and infinite height. Its aim is to minimize the height of the strip such that non-guillotinable and fix orientation constraints are meet. In this paper, an improved scoring rule is developed and the least waste priority strategy is introduced, and a randomized algorithm is presented for solving this problem. This algorithm is very simple and does not need to set any parameters. Computational results on a wide range of benchmark problem instances show that the proposed algorithm obtains a better or matching performance as compared to the most of the previously published meta-heuristics.     

Note on: An improved algorithm for the packing of unequal circles within a larger containing circle

This note proposed an improved version of the algorithm proposed by Wang et al. [Wang, H. Q., Huang, W. Q., Zhang, Q., & Xu, D. M. (2002). An improved algorithm for the packing of unequal circles within a larger containing circle. European Journal of Operational Research, 141, 339–347] for solving the disk packing problem with equilibrium constraints. An efficient strategy of accelerating the search process is introduced in the gradient method to shorten the execution time. A number of computational results are presented, showing the effectiveness of the proposed method.     

基于动作空间的求解三维矩形装箱问题的穴度算法

基于拟人途径求解三维矩形装箱问题。在穴度算法的基础之上,通过定义当前格局下的极大空闲矩形空间即动作空间,使得穴度的定义既能反映其本质,同时又大能幅度地缩减计算量,从而使算法能在较短的时间内得出空间利用率较高的布局图案。试算了OR-Library中无方向约束的全部47个算例。实验结果表明,改进后的穴度算法得到的平均空间利用率为95. 24 %,将目前的最好结果提高了0.32%,且花费了更少的计算时间。