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 number of nodes of a contour can be more than one thousand, a two-step approximation algorithm is proposed. The cutting sequence was first determined by the so-called nearest-neighbor algorithm with running time O(n²). Then the new starting point for every contour was chosen in time O(n) to further reduce the tool-path. The performance of the algorithm shows that the running time of the algorithm is within 0.1 second and the length of tool-path can be shortened in the second step by more than 10 percent.