A Travelling Salesman Problem in a three-dimensional spatial domain is associated with a scheduling problem encountered in a flexible manufacturing cell including a computer-controlled punching machine. The heuristic recently proposed by Bartholdi and Platzman, which uses a spacefilling curve as a quick way to organize a tour of a set of locations to visit in a unit square, is tested and generalized to the spatial domain describing the punch operations. A new recursive procedure is proposed for the construction of open spacefilling curves in the unit cube and in a parallelopiped. Numerical experimentations show that the 3-dimensional spacefilling curve heuristic becomes attractive when the number of punches executed by each tool is relatively small and when the turret rotation speed is relatively high.
Published October 1985 , 35 pages