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

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

Tool-Path Optimization Model and Approximate Algorithm for Multi-Contour Machining

Tool-path optimization for multi-contour machining was formulated as a generalized traveling salesman problem (GTSP) with changeable nodes since the cutting sequence and the starting points of contours affect the tool-path. In laminated object manufacturing (LOM), the tool-path must be optimized in real time. The time used to form the optimal path must be less than the time saved by the optimization. Considering the number of contours in a layer is usually less than a hundred and the one of nodes of a contour can be more than one thousand, a two-step approximation algorithm was proposed. The cutting sequence was first determined by the so-called nearest-neighbor algorithm with running time O(n~2). Then the new starting point for every contour was chosen in time O(n) to reduce the tool-path further. The performance of the algorithm shows that the running time of the algorithm is within 0.1second and the length of tool-path can be shortened in the second step by more than 10 percent.