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.
Paru en octobre 1985 , 35 pages