Approximation Algorithms for Time-Window TSP and Prize Collecting TSP Problems

We give new approximation algorithms for robot routing problems that are variants of the classical traveling salesperson problem (TSP). We are to find a path for a robot, moving at speed at most s, to visit a set of sites, each having an associated time window of availability, between a release time and a deadline. In the time-window prize collecting problem (TWPC), the objective is to maximize the number of sites visited within their time windows. In the time-window TSP problem (TWTSP), the objective is to minimize the length of a path that visits all of the sites V within their respective time windows, if it is possible to do so within the speed bound s. For sites on a line, we give approximation algorithms for TWPC and TWTSP that produce paths that visit sites at times within the relaxed time windows, for fixed, where; the running time is, where. For TWPC, the computed path visits at least (the cardinality of an optimal solution to TWPC) sites; for TWTSP, the computed path is of length at most (the length of an optimal TWTSP solution). For general instances of sites in a metric space, we give approximation algorithms that apply to instances with certain special structure of the time windows (that they are “dyadic” or that they are “elementary”), giving paths whose lengths are within a bounded factor of the optimal length, for the given speed s, while relaxing the speed to be a factor greater than s; for arbitrary time windows, we give an-approximation for TWTSP, assuming unbounded speed.