Günter Rote:

The N-line traveling salesman problem

Networks 22 (1992), 91–108, (Zbl 783.90118, MR #92k:90045). doi:10.1002/net.3230220106


We consider the special case of the Euclidean Traveling Salesman Problem where the given points lie on a small number (N) of parallel lines. Such problems arise for example in the fabrication of printed circuit boards, where the distance traveled by a laser which drills holes in certain places of the board should be minimized. By a dynamic programming algorithm, we can solve the N-line traveling salesman problem for n points in time nN, for fixed N, i. e., in polynomial time. This extends a result of Cutler (1980) for 3 lines. The parallelity condition can be relaxed to point sets which lie on N "almost parallel" line segments. We give a characterization of the allowed segment configurations by a set of forbidden subconfigurations.
  PostScript file (gzipped)   pdf file (gzipped)
other papers about this subject


The version that appears in Networks has an incorrect version of the corollary in Section 6, which characterizes the allowed segment configurations by forbidden subconfigurations: one case is missing in Figure 3. This is corrected in the technical report (see the links above), and in my dissertation, of which this paper is a part.

Last update: August 16, 2012.