论文标题
Anytime Tree搜索算法，用于二维两级和三级断头台包装问题
An anytime tree search algorithm for two-dimensional two- and three-staged guillotine packing problems
论文作者
论文摘要
[libralesso_anytime_2020]提出了2018年Roadef/EURO挑战玻璃切割问题的任何时间树搜索算法（https://www.roadef.org/challenge/Challenge/2018/en/index.php）。最终的计划在64名参与者中排名第一。在本文中，我们将其概括并表明它不仅对其最初设计的特定问题有效，而且还非常有竞争力，甚至还可以在文献中返回各种切割和包装问题的最先进的解决方案。我们对二维垃圾箱，多个背包和带状堆积问题进行了调整，具有两阶段或三阶段的精确或非精确的断头台切割，第一个切割的方向，或不施加或没有项目旋转。效率，快速提供良好解决方案的能力，简单性和多功能性的结合使其特别适合工业应用，这些应用需要快速开发实施多种特定业务约束的算法。该算法是在称为PackingSolver的新软件包中实现的。
[libralesso_anytime_2020] proposed an anytime tree search algorithm for the 2018 ROADEF/EURO challenge glass cutting problem (https://www.roadef.org/challenge/2018/en/index.php). The resulting program was ranked first among 64 participants. In this article, we generalize it and show that it is not only effective for the specific problem it was originally designed for, but is also very competitive and even returns state-of-the-art solutions on a large variety of Cutting and Packing problems from the literature. We adapted the algorithm for two-dimensional Bin Packing, Multiple Knapsack, and Strip Packing Problems, with two- or three-staged exact or non-exact guillotine cuts, the orientation of the first cut being imposed or not, and with or without item rotation. The combination of efficiency, ability to provide good solutions fast, simplicity and versatility makes it particularly suited for industrial applications, which require quickly developing algorithms implementing several business-specific constraints. The algorithm is implemented in a new software package called PackingSolver.
