Heuristics for the plate-cutting traveling salesman problem

In this paper we present a new problem that arises when parts are cut from large plates of metal or glass. We call this problem the plate-cutting traveling salesman problem because it requires the determination of a minimum-length tour such that exactly one point must be visited on each of a number of given polygons. We present a mathematical formulation of the problem and show that the problem is a variation of the well-known traveling salesman problem. We examine the problem when the order in which parts are to be cut is known. For this problem we present a Lagrangean decomposition of the problem and develop lower bounds and heuristics based on this decomposition. Computational testing on problems with 5–40 polygons reveals that the heuristics give fairly good solutions. When the order in which polygons are to be cut is known, the heuristic solutions are within 3–4% of the optimal. The decomposition-based heuristics are embedded in a variable r-opt heuristic for the overall problem.