An improvement heuristic framework for the laser cutting tool path problem

Abstract

This paper deals with generating cutting paths for laser cutting machines by representing a tool path in a novel way. Using the new representation, the tool path problem can be viewed as finding a partitioning of contours which minimises the sum of the costs of a rooted directed minimum spanning tree to connect the partitions and the costs of a generalised travelling salesman problem (GTSP) solutions within each partition. Using Edmond–Liu’s algorithm to solve the arborescence problem, an improved Lin–Kernighan heuristic to solve the GTSP and a heuristic-repartitioning approach, tool paths can be generated that are 4.2% faster than those generated by an existing tool path construction heuristic.

Keywords:

• laser cutting
• tool path
• PCGTSP
• RDMST

Notes

1 In fact, two directions are possible, but from an optimisation point of view, the direction actually does not matter with regard to minimising total time. From a technical point of view, there is a benefit in preferring one direction over the other because a laser head is not perfectly symmetrical, resulting in better quality cuts on a certain side of the laser head.

2 The inter contour distance between two contours i and j is the minimum of all distances between all nodes of contour i and all nodes of contour j.

3 The contour size is an approximation to the additional length the laser head has to travel going from the preceding contour to the succeeding contour since in doing so, the laser head has to ‘cross’ (at least partly) the contour i.

4 If precedence constraints would be actively included, care should be taken in choosing the cutting direction of the contours since this fixes the relative order of all nodes. If precedence relations exist between several child partitions of this pierce group, the relative order of the nodes does matter and could theoretically even cause a gridlock.

5 The computational experiments were performed using the default settings of the LKH of Helsgaun (2009). The settings specifically chosen for the GTSP described in Helsgaun (2014) were also tested. These settings resulted in an average 4.38% improvement over the PFr heuristic, compared to a 4.2% average improvement using the default settings. However, the required computation time nearly tripled. With the default settings, 7.7 h were required to solve all instances while with the GTSP settings 22.2 h were required to solve all instances. The increase is solely due to the longer LKH computation times i.e. the number of iterations (number of repartitioning calls) remained the same since the stopping criterion is: 10 non-improving iterations and the changes that the new parameters introduced in the GTSP paths were insufficient to force extra iterations.