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

Question

在工业中，经常会遇到一个问题，您需要计算 Material 的最有效使用，无论是织物、木材、金属等。因此，起点是 X 数量的给定尺寸的形状，由多边形和/或曲线，目标是给定尺寸的另一个多边形。

我假设许多当前的 CAM 套件都实现了这一点，但没有使用它们或其内部结构的经验，使用什么样的计算算法来找到最有效的空间利用？谁能给我指出讨论该主题的书籍或其他引用资料？

Answer 1

在 Andrew 在他的回答中为我指出了正确的方向并为我命名了问题之后，我决定将我的研究结果转储到这里作为一个单独的答案。

这确实是一个打包问题，更准确的说，是一个嵌套问题。该问题在数学上是 NP-hard 问题，因此当前使用的算法是启发式方法。似乎没有任何解决方案可以在线性时间内解决问题，除了琐碎的问题集。如果您想获得具有良好 Material 利用率的解决方案，则使用当前硬件解决复杂问题需要几分钟到几小时。有数十种提供形状嵌套的商业软件解决方案，但我无法找到任何开源解决方案，因此没有可以看到算法实际实现的真实示例。

在哥本哈根大学 (Nielsen) 的 Benny Kjær Nielsen 撰写的论文中可以找到关于嵌套和带状嵌套问题的历史解决方案的精彩描述。

一般方法似乎是混合使用多种已知算法以找到最佳嵌套解决方案。这些算法包括(引导/迭代)本地搜索，基于快速邻域搜索 em>不适合的多边形，和JoSTLing Heuristics。我找到了一篇关于这个主题的很棒的论文，其中包含算法如何工作的图片。到目前为止，它还有不同软件实现的基准。这篇论文由 S. Umetani 等人 ( Umetani ) 在 2006 年国际调度研讨会上发表。

一种相对较新且可能是迄今为止最好的方法是基于混合遗传算法 (HGA)，一种由模拟退火 和遗传算法，武汉大学吴清明等人 (Quanming)。他们通过在 MatLab 中使用 Visual Studio、SQL 数据库和遗传算法优化工具箱 (GAOT) 实现了这一点。