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-cu tting traveling salesman problem (P-TSP) because it requires the deter mination of a minimum-length tour such that exactly one point must be visited on each of a number of given polygons. We present a mathematic al 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 lowe r bounds and heuristics based on this decomposition. Computational tes ting on problems with 5-40 polygons reveals that the heuristics give f airly good solutions. When the order in which polygons are to be cut i s known, the heuristic solutions are within 3-4% of the optimal. The d ecomposition-based heuristics are embedded in a variable r-opt heurist ic for the overall problem.