Heuristics for laser cutting tool path generation

摘要

This paper deals with generating paths for cutting irregular parts nested on a metal sheet. The objective is to minimize the total time required to cut all parts from the metal sheet explicitly taking the cost of piercing and pre cutting into account. The problem is modeled as a generalized traveling salesperson problem with special precedence constraints. Our solution approach deals with inner-outer contours, common cuts, piercing points and pre cuts and consists of a construction heuristic followed by improvement heuristics embedded in a tabu search metaheuristic. Computational tests have been executed on a limited set of test problems and initial results show that the our solution approach is able to generate tool paths 0-48% better than those generated by a commercial package.