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
Abstract
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.
Erratum
The paper 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 PostScript and PDF file links above), and in my
dissertation,
of which this paper is a part.
Last update: August 16, 2012.