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

作     者：余国兴 丁玉成 李涤尘 

作者机构：西安交通大学机械工程学院 

出 版 物：《西安交通大学学报》 (Journal of Xi'an Jiaotong University)

年 卷 期：2004年第38卷第1期

页      面：39-42页

核心收录：

学科分类：080202[工学-机械电子工程] 08[工学] 0802[工学-机械工程] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：机械制造系统工程国家重点实验室资助项目 

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

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