Cutting Path Optimization Using Tabu Search
This paper deals with generating paths for cutting irregular parts nested on a metal sheet. The objective is to minimize the total non-cutting time for the cutter head starting at a known location, cutting all the required elements and returning to the known location. In contrast to most literature on this topic, a part does not have to be cut at once. If this reduces the total non-cutting time, it is possible to cut a number of elements on a given part, then cut other parts and then return later to finish cutting the given part. The problem is modeled as a generalized traveling salesperson problem with special precedence constraints. An initial feasible solution is generated and improved by local moves embedded in a tabu search framework. The proposed algorithm shows promising results in comparison with a commercial software package on a limited set of test cases.
J.R. Duflou, R. Clarke, M. Merklein, F. Micari, B. Shirvani and K. Kellens
R. Dewil et al., "Cutting Path Optimization Using Tabu Search", Key Engineering Materials, Vol. 473, pp. 739-748, 2011