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

摘要：

应用一种节点可变的广义旅行商问题,为平面多轮廓加工路径优化问题建模.针对在分层实体制造中,轮廓加工路径的优化必须实时进行、优化计算时间必须小于因路径缩短而节省的加工时间的要求,以及每层加工的轮廓数量通常少于102、每条轮廓的节点数可能为103的特点,提出一种先用时间复杂度为O(n2)的最近邻算法,求轮廓原始起点集合的旅行商问题解,然后在O(n)时间内改变每条轮廓的起点,进一步缩短路径长度的2步优化近似算法,从而兼顾了轮廓加工特点和算法实时性的要求.实验统计表明,该算法对路径的优化程度比仅按传统旅行商问题处理时提高了10%以上,且运行时间不超过0.1 s.

关键词：轮廓加工、路径优化、旅行商问题、分层实体制造

所属期刊栏目：38

分类号：TH164;TP301

资助基金：国家重点实验室基金

在线出版日期：2004-03-05（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：39-42