Using PCGTSPAlgorithm for Solving Generalized Segment Continuous Cutting Problem

Abstract

The problem of optimal tool routing for CNC sheet cutting machines (referred to as Cutting Path Problem or Tool Path Problem) is considered. The general formulation is used - Generalized Segment Continuous Cutting Problem (GSCCP). The new algorithm developed by the authors to solve generalized traveling salesman problem with precedence constraints (PCGTSP) is shown to effectively tackle this problem. This branch-and-bound algorithm, combined with the use of dynamic programming and a specialized heuristic solver, makes it possible to get optimal solutions for problems of small dimension in a relatively short time compared to known exact algorithms, as well as to find effective lower and upper bounds for the optimal solutions for large-scale problems. The conclusions are illustrated by solving several model examples. © 2022 The Authors. This is an open access article under the CC BY-NC-ND license (https://creativecommons.org/licenses/by-nc-nd/4.0/)