  Constant-factor, polynomial-time approximation algorithms are presented for
two variations of the traveling salesman problem with time windows. In the
first variation, the traveling repairman problem, the goal is to find a tour
that visits the maximum possible number of locations during their time windows.
In the second variation, the speeding deliveryman problem, the goal is to find
a tour that uses the minimum possible speedup to visit all locations during
their time windows. For both variations, the time windows are of unit length,
and the distance metric is based on a weighted, undirected graph. Algorithms
with improved approximation ratios are given for the case when the input is
defined on a tree rather than a general graph. The algorithms are also extended
to handle time windows whose lengths fall in any bounded range.
