二维装箱问题的启发式算法研究

发布时间：2018-06-04 07:35

本文选题：装箱问题 + 启发式算法　；参考：《厦门大学》2007年硕士论文

【摘要】： 装箱问题是一个经典的组合优化问题。简单地说,装箱问题就是将若干不同尺寸的物体互不重叠地放入有一定容量的箱子中以达到某种最佳目标。装箱问题被广泛应用于计算机科学领域和工业领域,多处理器任务调度、内存管理、货物装载以及原料切割等都是装箱问题在实际应用中的具体体现。因此,研究装箱问题具有重要的理论意义和应用价值。从二十世纪七十年代起,学术界就对装箱问题进行了广泛而深入的研究,但是由于装箱问题是NP难的,具有高度复杂性,用一般的数学方法很难求解。因此,在最近的几十年,启发式算法被广泛应用于装箱问题的求解中。本文首先对装箱问题的研究现状、问题分类及求解算法进行了综述和分析,然后重点对二维矩形装箱问题进行研究。在总结和概括了当前主要的装箱优化算法的基础上,对已有的HR和PH算法进行改进,提出了两种新的算法:基于递归思想的模拟退火算法(SA+HR)和基于动态分层的最小浪费优先启发式算法(SA+LWFBDL)。SA+HR算法主要是引进了模拟退火算法对HR算法进行改进,将HR算法得到的值作为评价解的标准,将任意交换两个物体位置得到的所有物体序列的集合作为邻域解空间,从而搜索出更好的物体序列来改善解的质量。而SA+LWFBDL算法在保留PH算法动态分层的基础上,改进了物体的放置策略,装物体时考虑所有的可行位置,优先选择放置后浪费面积最小的物体和可行位置的组合,对于浪费面积相同的多种组合,按照适合度进行选择,最后我们采用模拟退火算法来改善物体的装箱顺序从而得到更好的解。实验结果表明,我们提出的两种算法比原有的算法HR和PH有很大的改进。而且SA+HR的求解质量优于著名的算法BF、SA+BLF和GA+BLF,而SA+LWFBDL算法经过多次运行对大多数实例都可以得到最优解,可以与目前优秀的算法SPGAL、HRBB和HRP相竞争。
[Abstract]:The packing problem is a classical combinatorial optimization problem. To put it simply, the problem of packing is to put several objects of different sizes into boxes of a certain capacity without overlapping in order to achieve a certain optimal goal. Packing problem is widely used in computer science and industry. Multiprocessor task scheduling, memory management, cargo loading and raw material cutting are the concrete embodiment of packing problem in practical application. Therefore, the study of packing problem has important theoretical significance and application value. Since the 1970s, the academic circle has carried on the extensive and thorough research to the packing problem, but because the packing problem is NP-hard, has the high complexity, it is difficult to solve with the general mathematics method. Therefore, in recent decades, heuristic algorithms have been widely used to solve packing problems. In this paper, the research status, classification and solving algorithm of the packing problem are reviewed and analyzed firstly, and then the two-dimensional rectangular packing problem is studied. On the basis of summing up and summarizing the main packing optimization algorithms, the existing HR and PH algorithms are improved. Two new algorithms are proposed: simulated annealing algorithm (SA) based on recursion and minimum waste priority heuristic algorithm (SA LWFBDL).SA HR) based on dynamic layering, which mainly introduces simulated annealing algorithm to improve HR algorithm. The values obtained by the HR algorithm are taken as the criteria for evaluating the solution, and the set of all the sequences of objects obtained by arbitrarily exchanging the positions of two objects is taken as the neighborhood solution space, thus a better sequence of objects is searched to improve the quality of the solution. On the basis of preserving the dynamic layering of PH algorithm, SA LWFBDL algorithm improves the placement strategy of objects, considers all feasible positions when loading objects, and preferentially selects the combination of the least wasted area objects and feasible positions after placement. For a variety of combinations with the same wasted area, we choose according to the degree of fitness. At last, we use simulated annealing algorithm to improve the packing order of objects and get a better solution. The experimental results show that the proposed two algorithms are much better than the original algorithms HR and PH. Moreover, the solution quality of SA HR is better than that of the famous algorithms BFS SA BLF and GA BLF, and the SA LWFBDL algorithm can obtain the optimal solution for most instances after several runs, and can compete with the current excellent algorithms SPGALHRBB and HRP.
【学位授予单位】：厦门大学
【学位级别】：硕士
【学位授予年份】：2007
【分类号】：TP301.6

【相似文献】