余国兴,丁玉成,李涤尘
（西安交通大学机械工程学院,710049,西安）
摘要：应用一种节点可变的广义旅行商问题，为平面多轮廓加工路径优化问题建模．针对在分层实体制造中，轮廓加工路径的优化必须实时进行、优化计算时间必须小于因路径缩短而节省的加工时间的要求，以及每层加工的轮廓数量通常少于102、每条轮廓的节点数可能为10.3的特点，提出一种先用时间复杂度潍O(n2)的最近邻算法，求轮廓原始起点集合的旅行商问题解，然后在O(n)时间内改变每条轮廓的起点，进一步缩短路径长度的2步优化近似算法，从而兼顾了轮廓加工特点和算法实时性的要求．实验统计表明，该算法对路径的优化程度比仅按传统旅行商问题处理时提高了10％以上，且运行时间不超过0.1 s．
关键词：轮廓加工；路径优化；旅行商问题；分层实体制造
中图分类号：TH164；TP301文献标识码：A文章编号： 0253987X（2004）01003904