在表面上嵌套最大数量的形状

在表面上嵌套最大数量的形状

在安德鲁（Andrew）的回答为我指明了正确的方向并为我指出了问题之后，我决定将研究结果转交给一个单独的答案。

这确实是一个包装问题，更确切地说，这是一个嵌套问题。这个问题在数学上是NP难的，因此当前使用的算法是启发式方法。除了琐碎的问题集，似乎没有任何解决方案可以在线性时间内解决问题。如果要获得具有良好材料利用率的解决方案，使用当前硬件解决复杂的问题可能要花费数分钟到数小时。有数十种提供形状嵌套的商业软件解决方案，但是我无法找到任何开源解决方案，因此没有实际例子可以看到算法的实际实现。

哥本哈根大学（Nielsen）的BennyKjærNielsen撰写的一篇论文中可以很好地描述嵌套和带状嵌套问题以及历史解决方案。

通用方法似乎是混合使用多种已知算法，以便找到最佳的嵌套解决方案。这些算法包括 （引导/迭代）本地搜索 ，基于 No-
Fit多边形的
快速邻域搜索 以及 Jostling Heuristics
。我找到了一篇很好的论文，介绍了算法的工作原理。到目前为止，它还具有不同软件实现的基准。本文由S.
Umetani等人（Umetani）在2006年国际调度研讨会上发表。 __
__

一个相对较新和可能迄今最好的办法是基于 混合遗传算法 （HGA），由其组成的混合 模拟退火 和 遗传算法
已经由吴清明等武汉大学（的人所述全明）。他们已经通过使用MatLab中的Visual
Studio，SQL数据库和遗传算法优化工具箱（GAOT）来实现了这一点。