一种新的TSP问题环路构造算法及其在激光雕刻机路径控制中的应用

通过引入全局构造原则,并借鉴了Kruskal、2-opt等算法的思想,提出了一种新的时间复杂度为O(N2)的环路构造算法,并将其运用于激光雕刻机雕刻复杂图形时的路径优化。本算法生成路径长度约为理论下限的1.1倍,上浮幅度与NN和GD算法比较,分别下降了58%和42%。将此算法嵌入激光雕刻机控制程序,可将雕刻头空走的距离缩减88%。

A New Tour Construction Algorism and its Application in Laser Carving Path Control

By Bring in integral principle and the idea of Kruskal/2-opt algorism, a new tour construction algorism with time complicity O(N2) is presented in this paper. In fact, carving path of laser carving machine could be transferred to the traveling salesman problem(TSP) and optimized for laser carving process(LCP). In this algorism, some reasonable small loops are constructed in the first step, then larger loops are progressively synthesized with the small ones from bottom to top and in the end, a near-optimal resolution can be captured in this way. Moving distance resulted from this calculation is about 1.1 times of lower bound due to Held and Karp. Experimental results show that in the case of laser engraving machine, this algorism can reduce the vacancy path by 88%.