文献综述（或调研报告）：
装箱问题（或称排样问题）是一个典型的组合优化问题，并且在生产生活中具有广泛的实践。装箱问题具有不同的形式：一维的装箱问题(1-DBP)，即背包问题，最早由数学家Tobias Dantzig在1897年提出研究，并在后续的一百多年里被广泛发掘，目前主要通过分支定界法和动态规划进行求解。二维的装箱问题(2-DBP)，对于规则矩形的物体排样，最早由Paull在上世纪50年代使用线性规划的方法进行求解，但是运算量巨大，求解效率较低。在1988年巴黎EURO IX/TIMS XXV III国际会议上，成立了EURO Special Interest Group on Cutting and Packing专门进行排样问题的研究，并在之后每年定期举行研讨会议。三维的装箱问题(3-DBP)，则与人们日常生活更加紧密，如何向固定容积的包裹里面装更多的东西，如何用更少的箱子完成一批物品的包装等等。
本文主要讨论的不规则多边形二维装箱问题作为装箱问题的一种，也同样属于NP完全困难的组合优化问题，随着问题规模的扩大，求解的时间复杂度会急剧上升。相对于不规则多边形，待排样物体为矩形的情况较为简单。对于这类问题的研究集中于运筹学和计算机的领域。Dagli提出了一个基于图案子集的启发式算法，适合于图形组合的图案较少的情况。Gilmore 和 Gomory应用集合划分和列生成方法对一类特殊的矩形物体排样问题进行了求解。而在与启发式算法的结合上，Schollmeyer 等采用将来自有经验的排样师的启发式规则以及冲孔、剪床下料等限制条件存储在知识库中，指导模型生成图案组合。
而对于不规则的多边形，在智能算法广泛应用之前，学者Jakobs（1996）将不规则多边形用矩形完全包裹起来，再对该矩形进行装箱，即将不规则多边形的排样问题转化为矩形排样，但是这一做法本身会对排样的效果产生不利的影响；在考虑不改变多边形的形状上，Adamowicz， Albano（1976）提出了一种临界多边形的算法，根据不规则多边形的靠接状态进行定位，提高了装箱的利用率，但是无论是求解临界多边形还是对多边形进行排样，都需要进行大量的计算，求解较为复杂。
到20世纪90年代之后，学者们更多将研究方向转向智能算法上来，通过采用启发式算法来求解不规则多边形的装箱方案。Yeung（2003）采用遗传算法生成待装箱物体的排列顺序进行优化求解，Glover（2000）将禁忌搜索算法与装箱算法相结合，Gomes（2006）使用模拟退火算法求解不规则物体的二维装箱问题，inheiro（2015）在遗传算法中加入偏随机密钥以降低算法在迭代过程中陷入局部最优解的概率，Dagli（1997）采用人工神经网络方法、数学规划和遗传算法来求解定宽无限长板材的矩形装箱问题。并给出了模拟退火、遗传算法等与不同装箱算法组合的效果评价。
在国内，学者的研究方向与90年代后国外学者的方向大致类似，同样是采用智能算法对二维装箱问题进行求解，而提升的侧重点多在提高几何算法的效率，优化多边形近似和针对更加具体的应用上。刘胡瑶（2006）以多边形的重心作为生成临界多边形的参照点，提出了一种基于轨迹线的快速生成临界多边形的算法，在优化了生成临界多边形的算法后，结合遗传算法对待排样物体的序列进行搜索，优化排样方案；罗立宏（2013）采用图像法处理排样优化问题，将图形问题转化成图像问题，提出一种基于颜色来判断多边形零件是否发生重叠，多边形零件是否排放在板材的内部的方法，为解决排样问题提供了新的思路；周炯（2015）主要对装箱过程中可能出现的空洞的情况进行了优化；孙佳正（2018）针对多边形的合并算法，简化了多边形合并的过程并通过一种双种群遗传算法进行求解。
综合以往学者们的研究，我们可以发现对于不规则多边形的装箱问题，由于待排样多边形物体的几何特征复杂，难以寻找有效的方法将其近似为规则的图形，而一旦将不规则多边形原本的形状改变过多，又会对求解的结果产生不利影响。若完全保留多边形原有的特征，又缺乏有效的算法对多边形物体之间的靠接状态以及剩余空缺空间进行搜索，孔洞与凹陷的存在极大地增加了搜索的难度。在此之后，不同的定位规则也会对排样的效果产生极大的影响，最为主流的左底法往往在很多情况下不适用，而其他的一些定位策略或缺乏理论支撑，或计算的时间复杂度极高，因此也没有一个能够兼具精度与效率的算法。除此之外，各个多边形零件的排放先后顺序也难以在有限时间内得出最优解，解空间的大小随着多边形的数量呈指数级增长，只能通过启发式算法在一定时间内给出一个较为满意的排样方案。由于这些诸多原因的存在，对于大规模不规则多边形排样优化问题的求解依旧存在很大的挑战。又由于这一问题在生产生活中有广泛的应用，并且涉及到诸多学科的交叉，因此仍然具有很高的研究意义。
参考文献：
[1] Adamowicz M, Albano A. Nesting two-dimensional shapes in rectangular modules[J]. Computer-Aided Design, 1976, 8(1):27-33.
[2] Schollmeyer, M., Lin, J.Q., Krishnamurthy, K., Barami, A et al. Hybrid research for solving nesting problems. In The World congress on Expert system and operations research for solving nesting problems, Pergamon Press, NY, 1991, 1223-1231.
