全自主研发自动排料引擎/自动排料软件

自动排料即使用计算机软件实现裁片（服装衣片，钣金零件）在规定材料（面料，金属板材）上的自动布局，并以材料利用率为主要追求目标。Markdown的基本语法知识。

市面上有哪些知名排料软件？

目前市面上能看到的知名排料软件绝大部分是国外软件。 还有一类是使用国外排料引擎的国内排料软件，所谓排料引擎即核心算法库/模块。比较知名的有Autonester(德国),Gemini(罗马尼亚),Lectra(法国力克)，ShapeShifter(新西兰,简称SS)，Nestfab(英国), Sigmanest(美国?), … ，国内的比较有名的有smartnest, 和鹰和青鹤（均不确定两家是否使用自研发引擎， 主要用于皮料行业）：

国产引擎与国外引擎的差距

从功能上看，国产引擎能够提供较多甚至完备的功能，主要差距还是体现在利用率上。 对比国外顶级排料软件，国产引擎与国外引擎利用率差距通常在平均2%以上。
比较不同的排料引擎，需要测试很多的例子，各种类型的例子，并统计平均利用率。 单独拿一个例子比较意义不大， 比如 A测试100个例子平均利用率85%， B对应的是84%。 但是随机抽取其中一个，B还是有比A利用率高的可能的。

自动排料引擎的难点在哪？

国外对自动排料软件的研究从上世纪70年代就开始了。大概经历

1. 矩形左底
2. 不规则形状的左底，
3. Grid扫描的左底
4. 使用NFP算法加速
5. 重叠移除算法
6. Pattern识别和匹配
7. 云/AI ？？
   从运行过程中的状态来看，又可以分为可行解法和不可行解法。
   左底算法通常都是可行解法， 即设定一组零件排放顺序，依次把裁片放入材料（面料/板材）中， 通过调节和优化顺序改进利用率。
   不可行解法通常利用启发式方法或者可行解法初始化一个初解， 然后缩短面料/板材长度或者增加裁片个数，这样这个布局就会有裁片相互重叠，通过移动或交换裁片来移除重叠，得到一个没有重叠的可行解。
   通常不可行解的解空间接近问题的解空间， 而按照次序排放的不可行解算法的解空间要比问题的解空间小，也就是说即使能遍历所有的解，也可能离真实问题的极限相距甚远，何况组合优化问题本来就是NP问题。
   而对于不可行解算法来说，运算量非常大，多数不可行解算法是通过构造线性或者非线性模型，通过解方程组来移除裁片之间的重叠。 这对于理论和实际编程技巧都是一个很高的挑战。

友图自动排料

友图自动排料引擎/软件是上海友图科技有限公司自主研发的新型排料软件，基于重叠移除算法，在小规模上能有效逼近理论极限

来看几个测试例子
shirt 89.7% 180度

这是欧洲切割与包装事务委员会的标准测试数据，是很多学术论文比较排料算法的测试基准数据。
这个例子的目前最好论文纪录是88.96%，Nestfab的10分钟成绩是88.63%.
基准测试数据有一个特点就是多边形的顶点数经过了精简，通常每个多边形的顶点数都小于20. 下面看一个真实测例，来自Padsystem的测试数据 2500（可在Padsystem的软件附带sample中获得）.

友图自动排料 3分钟的数据是 91.48%（上图）。 对应的Autonester数据是91.25%。
该例子多边形顶点数最多的有116个，除了几个近矩形形状外，顶点数都超过了50，是真实的生产用例。 下面是 友图排料10分钟的运行结果

友图自动排料真有那么好么？

嗯， 光从上面两个例子看，确实够好。 不过实际情况远比这个复杂。
来看下面的例子

这个例子共136个裁片，友图排料 10分钟的利用率是 81.95%， 而autonester的利用率高达83.8%。
当然并非个数多，友图排料利用率就一定差，看下面的例子

这个例子裁片数目104， 友图排料10分钟 90.66% ， autonester是90.58%

所以可以看到， autonester应对各种类型的裁片时更加全面，友图自动排料在全面性上不如autonester。

友图自动排料可以用于钣金排料吗？

相对来说，友图自动排料在钣金测例中的表现比在服装排料中的表现更好，
先看下面一个例子

红圈的两个裁片阻止裁片A上移。 通常我们希望的是裁片A上移以弥补和左上裁片的缝隙， 但是这里红圈两个裁片在其他位置很难找到更好的排放位置。特别是红圈内的裁片是细长条时更为明显，比如右上的直长条如果立在布局图的中间位置，将阻断两边的裁片，使得总的空隙更大。

而对于钣金排料来说，由于可以任意旋转，至少大部分情况下可以旋转90度， 直长条变成横长条，就不是问题了。
下面看一个真实的钣金例子

``

钣金多板材排料的实现

友图自动排料的实现与大部分钣金类排料软件不同， 通常多板材下利用率的提高是通过增加或者替换更大的零件来实现， 而友图排料是通过在板材边界设置禁止线， 不同板材之间可以跨越边界禁止线（不能和边界线重合）来实现全局寻优的， 所以，对于三百个一下的零件来说，这种方法能找到更好的解。

看下面的例子

每个零件都可以在三块板材上相互跨越。当然，这样处理搜索空间就会变大。 通常超过三百个零件就不能这样处理了。

友图自动排料软件的性价比

友图自动排料引擎/软件相比较国外顶级排料软件，价格只有三分之一左右。

二次开发

友图自动排料还提供开发接口， 开发商可以使用友图排料引擎实现自己的自动排料软件，个性化指定GUI/输入输出等功能

待续