嵌套在一个表面形状的最高金额 [英] 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?

推荐答案

安德鲁经过他的回答向我指出了正确的方向，并命名问题对我来说，我决定在这里倾倒我的研究成果，在一个单独的答案。

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.

这的确是一个包装问题，更precise，这是一个嵌套的问题。的问题在数学上是NP难题，因此，算法目前使用的启发式方法。目前似乎没有任何解决办法，解决线性时间的问题，只是微不足道的问题集。解决复杂的问题，需要从几分钟到几小时与当前的硬件，如果你想获得良好的材料利用率的解决方案。有几十商业软件解决方案，提供筑巢的形状，但我无法找到任何开源解决方案，所以有其中一个能看到实际实现的算法没有实际的例子。

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.

嵌套和带嵌套问题与历史解决方案的优秀描述可以在写的哥本哈根大学尼Kjær的尼尔森（的尼尔森）。

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).

一般的做法似乎是混合使用多种已知的算法，以便找到最佳的嵌套解决方案。这些算法包括的的（制导/迭代）本地搜索的 快速邻域搜索的是基于 临界多边形的和的扰攘的启发式的。我发现了一个非常好的论文就这一问题与的算法是如何工作的图片。它也有不同的软件实现的基准为止。本文是由S.梅谷等人（的梅谷）。

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屋！