基于最小重力势能原理与遗传算法的服装排料算法

汪朋朋 施群 谢云斌 谢家骏 潘炳伟

摘要：高效自动排料算法中布料利用率的提升对于企业具有重要的经济价值。但排料问题属于NP完全问题，难以在有限时间内找到问题的最优解。研究提出基于最小重力势能原理的排料算法，并将遗传算法应用到排料优化问题中，最终进行排料算法的对比验证。基于最小重力势能原理及遗传算法的排料算法优化减小了每次排料过程中的计算量，可在有限的时间内得到近似最优解。结果表明，所提出的自动排料算法在提高利用率方面具有较高的实用价值。

关键词：排料算法；最小重力势能原理；遗传算法；不规则排料

中图分类号：TS195.644文献标志码：A文章编号：1009-265X（2018）03-0053-09Garment Nesting Algorithm Based on Principle of Minimum

Gravity Potential Energy and Genetic Algorithm

WANG Pengpeng， SHI Qun， XIE Yunbin， XIE Jiajun， PAN Bingwei

（School of Mechatronic Engineering and Automation， Shanghai University， Shanghai 200072， China）Abstract：The improvement of material utilization in efficient automatic nesting algorithm has important economic benefits for Enterprises. However， nesting problem is a NPcomplete problem and it is hard to find out the optimal solution to the problem within the finite time. The nesting algorithm based on the principle of minimum gravity potential energy was proposed in this paper and genetic algorithm was also applied in nesting optimization problem. Finally， the comparison validation of the nesting algorithm was conducted. To a certain extent， this nesting algorithm based on the principle of minimum gravity potential energy and genetic algorithm reduce and optimize the computation load in each process， and the quasioptimal solution can be gained within the limited time. The experimental results show that this automatic nesting algorithm has a high practical value in improving the utilization rate.

Key words：nesting algorithm； principle of minimum gravity potential energy； genetic algorithm； irregular nesting

服装排料属于不规则图形排料问题，部分研究者采用最小矩形包络法将不规则图形排料转化为矩形排料[12]，这种方法排料效率较高，但存在材料利用率低的缺陷。排料优化问题主要包括样片最优排放位置确定和样片最优排样顺序确定两个问题。

样片位置确定有多种研究策略，最常用的是Baker等[3]左下角（BottomLeft condition，BL）策略，BL策略的主要思想是在保证样片不重叠的前提下，重复将样片向左、向下移动，直到不能再移动为止，由于BL策略容易引起排料结果左侧偏高，遗留较大块的空白区域等问题，一些学者提出了相应的改进算法，如Liu等[4]向左平移优于向下的BLLF策略、Hopper等[5]左下角填充的BLF策略。采用BL策略进行排料的算法一般需要计算临界多边形（NFP），当样片数量（N）和旋转次数（RN）增大时，临界多边形的计算非常耗时；……