密集型多轮廓裁片的刀具空行程路径寻优

摘要：服装行业中缩短刀具裁剪空行程对于高效裁剪布料具有重要意义。结合服装裁片排列具有轮廓形状复杂、分布密集的特点，将问题转化成广义旅行商问题 于最大最小蚁群（MMAS）算法提出了一种新的用于裁片刀具空行程路径寻优的算法——密集多轮廓蚁群算法，该算法包括4步：1）用MMAS算法确定初步裁片顺序；2）由裁片顺序寻找各裁片入刀节点；3）将各裁片的入刀节点再次用MMAS进行顺序优化重组得到初步裁剪路径；4）反复迭代第2）步和第3）步以求得最优路径。实验验证了所提算法的有效性，对比现有的扫描算法以及双信息素蚁群（NACS）算法其结果分别提升了60.15%和22.44%，该算法在刀具空行程优化上具有明显优势。

关键词： 密集型多轮廓裁片； 空行程； 路径寻优； 广义旅行商问题； 最大最小蚁群算法

中图分类号： TP391.7 文献标志码： A

0引言

随着人力成本大幅提高，全自动裁剪设备对于降低服装制造企业成本具有重要意义 于这一需求，自主研发了全自动高速裁剪设备以及配套CAD/CAM软件。根据裁片CAD图，CAM模块自动生成较短的刀具裁剪路径，是高效裁剪的前提条件。

裁剪路径的生成即是各裁片裁剪顺序的确定和裁片上入刀节点的选择：裁刀根据裁剪顺序对裁片依次进行裁剪，对当前裁片从入刀节点进刀然后沿该裁片的轮廓线进行裁剪，刀具运行到入刀节点后出刀，完成该裁片的裁剪，然后移动到下一裁片的入刀节点进行下一裁片的裁剪工作，直到所有裁片裁剪完毕。裁刀在各裁片入刀节点间的移动路径为刀具走位行程即刀具空行程。由于加工裁片轮廓排版密集，裁剪批量大（裁片总数目通常有几十到上百），空行程将成为影响加工效率的一个重要因素。如图1所示为一衬衣的二维裁片（包括已编号的五个封闭轮廓裁片）的三种不同的裁剪路径，其中刀具空行程以虚线表示，入刀节点以粗点表示；从该图可见，同样的裁剪顺序但入刀节点不同则空行程路径长度差别很大（对比图1（a）与图（b）），其中图1（c）的刀具空行程路径为三种路径中的最短路径。可见对于给定的裁片排版图，空行程的长度与裁片的裁剪顺序以及每个裁片的入刀节点不同而变化。因此需就裁片裁剪顺序以及相应入刀节点的选择进行优化，这两个子问题可转化为一广义旅行商问题（GeneralizedTravelingSalesmanProblem，GTSP）进行统一求解。

对于GTSP的求解存在大量算法，主要分为3类：1）特殊启发式算法[1-6；2）将CTSP转化成标准旅行商问题（TravelingSalesmanProblem，TSP）进行求解[7-10]；3）采用领域算法[11-13]。上述方法均没考虑裁片分布密集轮廓复杂的具体情况，针对此特定情况，本文以最大最小蚁群（MaxMinAntSystem，MMAS）算法[14]为基础，提出一种新的走刀空行程路径优化算法：采用标准MMAS算法首先制定初步裁片顺序；随后在用变异的MMAS算法求解入刀点，而后对求得的入刀节点进行顺序重组再次确定裁片顺序，对以上两步骤进行迭代求解，从而确定裁剪顺序与入刀点，使最终空行程路径达到全局优化。

为直观看出本文算法优势，绘制了两种代表性的裁片文件的空行程路径图（如图4所示），这两种裁片包括结构相对简单的弹袖棉裁片和结构比较复杂的裤袋布（长）裁片的。图4中细线所绘制的封闭轮廓部分为裁片，裁片间的粗折线段则表示刀具空行程路径。

在所展示裁片中，弹袖棉的裁片构成要比裤袋布（长）的裁片构成简单，裁片规模也相对较小。结合两裁片的路径图分析表4中的数据：对于弹袖棉裁片，IMAS算法比扫描算法以及NACS算法，空行程分别缩短了56.6%和23.6%；对于裤袋布（长）裁片，IMAS算法比扫描算法以及NACS算法，空行程分别缩短了69.8%和35.1%。由此可以得出IMAS算法随着裁片轮廓复杂程度的增加以及裁片规模的增大将越来越优于扫描算法和NACS算法。其原因是原始的搜索扫描算法并非智能算法，该算法针对不同对象时不能进行反馈调节，而NACS算法却没能考虑裁片裁剪顺序与裁片入刀节点选择之间存在的松散耦合关系，所以随着裁片数目的增多以及轮廓越趋复杂其优化效果也会变差。而本文算法充分考虑到此松散耦合关系，故可以取得更优解。

4结语

基于最大最小蚁群算法，针对密集型多轮廓加工走刀空行程路径进行优化，提出一种新的路径优化算法。该算法已经成功集成到自动化服装裁剪设备的CAD/CAM系统上，实例验证了该算法的可行性，对比现有算法，在刀具空行程的路径长度优化上具有明显优势。其中的参数选择需根据每个特定实例进行实验选择，在将来的研究中将对参数的选择进行深入研究，从而提高该算法的实用性。

参考文献：

[1]MATEIO，POPP.Anefficientgeneticalgorithmforsolvingthegeneralizedtravelingsalesmanproblem[C]//Proceedingsof2010IEEEInternationalConferenceonIntelligentComputerCommunicationandProcessing.Piscataway，NJ：IEEEPress，2010：87-92.

[2]GUTING，KARAPETYAND.Amemeticalgorithmforthegeneralizedtravelingsalesmanproblem[J].NatualComputing，2010，9（1）：47-60.

[3]POPPC，MATEIO，SABOC.Anewapproachforsolvingthegeneralizedtravelingsalesmanproblem[C]//HybridMetaheuristics，LNCS6373.Berlin：SpringerVerlag，2010：62-72.

[4]RENAUDJ，BOCTORFF.Anefficientcompositeheuristicforthesymmetricgeneralizedtravelingsalesmanproblem[J].EuropeanJournalofOperationalResearch，1998，108（3）：571-584.

[5]YANGJH，SHIXH，MARCHESEML.AnantcolonyoptimizationmethodforgeneralizedTSPproblem[J].ProgressinNatualScience，2008，18（11）：1417-1422.

[6]MOULM.AnovelantcolonysystemwithdoublepheromonesforthegeneralizedTSP[C]//Proceedingsof2011SeventhInternationalConferenceonNaturalComputation.Piscataway，NJ：IEEEPress，2011：1923-1928.

[7]DIMITRIJEVIV，ARIZ.Anefficienttransformationofthegeneralizedtravelingsalesmanproblemintothetravelingsalesmanproblemondigraphs[J].InformationSciences，1997，102（1）：105-110.

[8]NOONCE，BEANJC.Anefficienttransformationofthegeneralizedtravelingsalesmanproblem[J].AnnArbor，1989，1001：48109-2117.

[9]LAPORTEG，putationalevaluationofatransformationprocedureforthesymmetricgeneralizedtravelingsalesmanproblem[J].INFOR，1999，37（2）：114-120.

[10]BEHZADA，MODARRESM.Anewefficienttransformationofthegeneralizedtravelingsalesmanproblemintotravelingsalesmanproblem[C]//Proceedingsofthe15thInternationalConferenceofSystemsEngineering.Berlin：SpringerVerlag，2002：6-8.

[11]HUB，RAIDLG.Effectiveneighborhoodstructuresforthegeneralizedtravelingsalesmanproblem[M]//EvoCOP2008：Proceedingsofthe8thEuropeanConference.Berlin：SpringerVerlag，2008：36-47.

[12]BONTOUXB，ARTIGUESC，FEILLETD.Amemeticalgorithmwithalargeneighborhoodcrossoveroperatorforthegeneralizedtravelingsalesmanproblem[J].Computers&OperationsResearch，2010，37（11）：1844-1852.

[13]KARAPETYAND，GUTING.Efficientlocalsearchalgorithmsforknownandnewneighborhoodsforthegeneralizedtravelingsalesmenproblem[J].EuropeanJournalofOperationalResearch，2012，219（2）：234-251.

[14]THOMASS，HOLGERH.MAXMINantsystem[J].FutureGenerationsComputerSystems，2000，16（8）：889-914.

[15]YUWJ，HUXM，ZHANGJ，etal.Selfadaptiveantcolonysystemforthetravelingsalesmanproblem[C]//SMC2009：Proceedingsofthe2009IEEEInternationalConferenceonSystems，ManandCybernetics.Piscataway，NJ：IEEEPress，2009：1399-1404.

[16]ZHANGXF，ZHANGHM，GAOMZ.Continuousantcolonyoptimizationalgorithmbasedoncrossoverandmutation[C]//Proceedingsof2010theSixthInternationalConferenceonNaturalComputation.Piscataway，NJ：IEEEPress，2010，5：2605-2608.