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

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

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

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

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

从功能上看，国产引擎能够提供较多甚至完备的功能，主要差距还是体现在利用率上。对比国外*排料软件，国产引擎与国外引擎利用率差距通常在平均2%以上。

比较不同的排料引擎，需要测试很多的例子，各种类型的例子，并统计平均利用率。单独拿一个例子比较意义不大，比如 A测试100个例子平均利用率85%， B对应的是84%。但是随机抽取其中一个，B还是有比A利用率高的可能的。

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

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

矩形左底
不规则形状的左底，
Grid扫描的左底
使用NFP算法加速
重叠移除算法
Pattern识别和匹配
云/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分钟的运行结果
自动排料-友图自动排料
下面的例子裁片数目104，友图排料10分钟 90.66% ， autonester是90.58%， Nestfab 90.25%(最新版尚未发布，Nestfab作者Doctor Gleen Whitwell提供数据)

自动排料-友图自动排料
钣金单板材不限长示例

``

钣金多板材排料的实现

自动排料-友图自动排料

板式家具

37种1480个部件 83张板材
自动排料-友图自动排料
不同板材尺寸下的结果

超大规模排料

超大规模排料无法使用重叠移除来优化，需要使用传统BLF和pattern recognition技术。
下面这个例子总计裁片种类121种，共3936片，宽度 12000mm 友图自动排料完成时间 7秒
自动排料-友图自动排料
同样的数目，材料宽度 6000mm 完成时间 10秒

trousers 64片 * 64倍共计 4096片 < 2秒

钣金零件总计3990个 5秒