On Generating Tool Paths for Laser Cutters

Laser cutting is one of the major cutting processes used to manufacture sheet metal products. A typical production process consists of designing parts, nesting the parts on metal sheets, cutting the parts from the sheets and if there are three dimensional parts, bending the parts. Integrated production scheduling methods to minimize the total cost incurred by the entire production process exist. One of the results is the assignment of parts to a metal sheet after which CAM software executes the actual nesting and generates a cutting path. In sheet metal laser cutting, a typical cutting process can take between several minutes to several hours, depending on the number of parts on the plate, the material type, the machine, the process parameters, and the plate thickness. Current CAM software utilizes very simple heuristics to generate these tool paths and as such not all relevant costs and technical constraints are taken into account, such as piercing costs, bridges, pre-cuts, sharp angle costs, skeleton cuts, plate edge and clamp positions, collisions, imposed path patterns, and thermal effects.

This PhD research aims at developing fast and effective algorithms for generating tool paths for laser cutting machines taking all technical constraints into account. The tool path problem excluding thermal effects is modeled as a  precedence constrained generalized traveling salesman. A tabu search meta-heuristic approach is found to be able to  generate fast tool paths in a short amount of computation time for thin metal sheets where piercings can be executed on the fly and thermal effects are negligible. For thicker plates, this approach becomes too computationally expensive and specialized construction heuristics are developed that take advantage of the specific structure of laser cutting tool path problems. A novel tool path representation is developed that recasts the tool path problem in such a way that promising local improvement moves can more easily be identified. Furthermore, this new representation naturally decomposes the problem in two well-studied problems: the generalized traveling salesman problem (GTSP) and the rooted directed  minimum spanning tree (RDMST). An improvement heuristic framework that iteratively solves GTSPs and RDMSTs and executes a local search improvement phase is developed and positively evaluated.

A Finite Difference Method (FDM) simulation is developed to evaluate the thermal effects during cutting. It is shown that a FDM approach can estimate the thermal effects sufficiently accurate within acceptable calculation times. This FD method is utilized to construct a heat-penalty based multi-start construction heuristic that is able to generate tool paths free from thermal errors. 

The research further shows that many of the additional technical constraints can be included in the model by a proper preprocessing phase or can effectively be handled by a post optimization phase.