在表面上嵌套最大数量的形状 [英] Nesting maximum amount of shapes on a surface

问题描述

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

In industry, there is often a problem where you need to calculate the most efficient use of material, be it fabric, wood, metal etc. So the starting point is X amount of shapes of given dimensions, made out of polygons and/or curved lines, and target is another polygon of given dimensions.

我假设许多当前的 CAM 套件都实现了这一点，但是没有使用它们或其内部的经验，使用哪种计算算法来找到最有效的空间使用?谁能给我指点讨论这个话题的书或其他参考资料?

I assume many of the current CAM suites implement this, but having no experience using them or of their internals, what kind of computational algorithm is used to find the most efficient use of space? Can someone point me to a book or other reference that discusses this topic?

推荐答案

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

After Andrew in his answer pointed me to the right direction and named the problem for me, I decided to dump my research results here in a separate answer.

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

This is indeed a packing problem, and to be more precise, it is a nesting problem. The problem is mathematically NP-hard, and thus the algorithms currently in use are heuristic approaches. There does not seem to be any solutions that would solve the problem in linear time, except for trivial problem sets. Solving complex problems takes from minutes to hours with current hardware, if you want to achieve a solution with good material utilization. There are tens of commercial software solutions that offer nesting of shapes, but I was not able to locate any open source solutions, so there are no real examples where one could see the algorithms actually implemented.

可以在哥本哈根大学的 Benny Kjær Nielsen 撰写的论文中找到对嵌套和条形嵌套问题的出色描述(Nielsen).

Excellent description of the nesting and strip nesting problem with historical solutions can be found in a paper written by Benny Kjær Nielsen of University of Copenhagen (Nielsen).

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

General approach seems to be to mix and use multiple known algorithms in order to find the best nesting solution. These algorithms include (Guided / Iterated) Local Search, Fast Neighborhood Search that is based on No-Fit Polygon, and Jostling Heuristics. I found a great paper on this subject with pictures of how the algorithms work. It also had benchmarks of the different software implementations so far. This paper was presented at the International Symposium on Scheduling 2006 by S. Umetani et al (Umetani).

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

A relatively new and possibly the best approach to date is based on Hybrid Genetic Algorithm (HGA), a hybrid consisting of simulated annealing and genetic algorithm that has been described by Wu Qingming et al of Wuhan University (Quanming). They have implemented this by using Visual Studio, SQL database and genetic algorithm optimization toolbox (GAOT) in MatLab.

这篇关于在表面上嵌套最大数量的形状的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！