A new global toolpath linking algorithm for different subregions with Travelling Saleman problem solver

ABSTRACT

In CNC toolpath generation process, the operation of linking toolpaths from different sub-machining regions is common and inevitable. Apparently, the jumping toolpath between machining regions is invalid. They do not contribute to the machining process but only waste valuable manufacturing time; therefore, these toolpaths should be as short as possible. Many methods have been used to link toolpaths, such as the Genetic Algorithm (GA), the Particle Swarm Optimization (PSO) or even the greedy algorithm. However, GA and PSO require multiple iterations to find the global optimum, while greedy algorithm selects the current shortest connection each time without considering the global optimum. To reduce the total length of non-productive toolpaths and save computing time, in this paper, a new method is proposed by modeling the toolpath linking problem purely as a traveling salesman problem (TSP). The initial toolpaths in different subregions are generated in ordinary ways. Each toolpath of a subregion has two endpoints, which can be simplified as a line segment. In this way, the toolpath linking problem can be considered as a segment TSP: finding the shortest tour through all the segments. In this paper, the efficient TSP solver using Lin-Kernighan–Helsgaun (LKH) algorithm is employed and modified for the segment TSP application. The distance function between ‘cities’ is redefined to adapt the segments TSP. Finally, the feasibility of the proposed method is verified with several examples. The comparison with the result of traditional greedy algorithm proves the superiority of the proposed method.

KEYWORDS:

• Toolpath linking
• toolpath generation
• traveling salesman problem

Disclosure statement

No potential conflict of interest was reported by the author(s).

Ethical Approval

The authors declare that they have no conflict of interest.

Additional information

Funding

This work was financially supported by the Natural Science Foundation of Zhejiang Province, China [No. LGG19E050027] and the University Laboratory Research Project of Zhejiang Province, China [N0. ZD202001]. Key Projects of National Natural Science Foundation of Zhejiang Province.