平面多轮廓加工路径优化模型及其近似算法

余国兴　丁玉成　李涤尘

摘要：应用一种节点可变的广义旅行商问题，为平面多轮廓加工路径优化问题建模．针对在分层实体制造中，轮廓加工路径的优化必须实时进行、优化计算时间必须小于因路径缩短而节省的加工时间的要求，以及每层加工的轮廓数量通常少于10²每条轮廓的节点数可能为10³的特点，提出一种先用时间复杂度为O(n²)的最近邻算法，求轮廓原始起点集合的旅行商问题解，然后在O(n)时间内改变每条轮廓的起点，进一步缩短路径长度的2步优化近似算法，从而兼顾了轮廓加工特点和算法实时性的要求．实验统计表明，该算法对路径的优化程度比仅按传统旅行商问题处理时提高了10％以上，且运行时间不超过0．1s.关键词：轮廓加工；路径优化；旅行商问题；分层实体制造中图分类号：TH164；TP301文献标识码：A文章编号：0253—987X(2004)01—0039—04