【作者】 李坤；

【导师】 吕志鹏；

【作者基本信息】 华中科技大学 ， 计算机技术（专业学位）， 2024， 硕士

【摘要】 矩形装箱面积最小化问题是工业生产中的常见问题,它要求将一组矩形物品互不重叠地正交放置于可变尺寸容器中,目标是最小化装箱容器面积。该问题是NP难问题,常出现于芯片设计、报纸印刷、钢材切割和布料加工等领域。因此,设计求解矩形装箱面积最小化问题的高效算法具有重要的理论价值和现实意义。通过将矩形装箱面积最小化问题转化为二维条带装箱问题,提出了一种改进的自适应启发式算法。上层算法是一个自适应的选择框架,用于生成并选择候选宽度。下层算法可分别采用两阶段随机局部搜索算法或两阶段集束搜索算法,对给定候选宽度下的装箱方案进行迭代优化。首先,为了挑选有潜力的候选宽度,设计了基于矩形块边长组合的宽度上下界。依据经验选择任意三个矩形块计算边长组合并取最小值作为宽度下界,宽度上界取容器近似正方形时的高度值。其次,提出了两种基于天际线结构的八分类情形的打分规则,将下层算法搜索过程分为两个阶段,前后两阶段各采用不同打分的规则。通过切换两种打分规则微调当前阶段待放置矩形块的优先级,以期提高空间利用率。为了确定两种打分规则的切换点,采用多次重启的策略在装箱后半段不同高度处测试切换效果,从而自适应地选择最好的切换点。然后,设计了一种按矩形块的最长边降序排序的参考序列,同时提出了基于交换动作和循环移位动作的邻域扰动策略,从而使算法更易于跳出局部最优值陷阱。最后,下层实现了另一种集束搜索算法,该算法采用局部评估、全局评估和向前看评估相结合的方式对子节点剪枝,以贪心构造的解估计候选动作的潜力,从而控制搜索树的生长过程。在公开算例集上进行测试,两种算法都取得了良好的效果。相较于现有文献中的历史最好解,在共计39个算例中,随机局部搜索算法改进了34个算例的历史最好解,集束搜索算法改进了31个算例的历史最好解。两种算法的平均填充率都有较大提升,实验结果表明了上层自适应选择框架和下层两种搜索算法的有效性。更多还原

【Abstract】 The Rectangle Packing Area Minimization Problem is a common problem in industrial production,which requires to orthogonally pack a group of rectangles without overlap into a variable-sized container,aiming to minimize the area of the packing container.This problem is NP-Hard and has a wide range of applications in areas such as chip design,newspaper printing,steel cutting,and fabric processing.Therefore,designing efficient algorithms for the problem holds significant theoretical value and practical significance.An improved adaptive heuristic algorithms is proposed by transforming the Rectangle Packing Area Minimization Problem into a Two-Dimensional Strip Packing Problem.The upper-level algorithm serves as an adaptive selection framework for generating and selecting candidate widths.The lower-level algorithms can employ either two-stage random local search or two-stage beam search to iteratively optimize the packing schemes under given candidate widths.Initially,to select promising candidate widths,upper and lower bounds are designed based on combinations of rectangles.Based on experience,select any three rectangules to calculate combinations of edges and take the minimum value as the lower bound of the candidate width.While the upper bound is the height when the container is approximately a square.Additionally,two scoring rules based on skyline in eight classified cases are proposed,dividing the lower-level algorithm search process into two stages,each adopting different scoring rules.Switching between two scoring rules to finetune the priority of the rectangular blocks to be placed in the current stage aims to enhance space utilization.To determine the switching points of the two scoring rules,a strategy of multiple restarts is adopted to test at different heights in the latter half of the packing process,thus adaptively selecting the optimal switching points.Subsequently,for the lower-level random local search algorithm,a new reference sequence is designed,sorting the rectangles in descending order of their longer edges.Moreover,neighborhood disturbance strategies based on swap actions and cyclic shift actions are proposed to make the algorithm more likely to escape local optima trap.Finally,the lower-level also implements another beam search algorithm,which employs combinations of local evaluation,global evaluation,and lookahead evaluation to prune child nodes,greedily constructs the estimated potential of candidate actions,thus controlling the growth of the search tree.Testing the two algorithms on a publicly available set of instances,both the random local search algorithm and the beam search algorithm achieve good results.Compared to the historical optimal results in existing literature,out of a total of 39 instances,the random local search algorithm improves the historical optimal solution in 34 instances,while the beam search algorithm improves it in 31 instances.The average filling ratio of both algorithms shows significant improvement,demonstrating the effectiveness of the adaptive selection framework and the two lower-level search algorithms.更多还原