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

Su Jia, Stony Brook University

February 14, 2017

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 $V=\{v_1,\ldots,v_n\}$ of sites, each having an associated time window of availability, $[r_i,d_i]$, between a release time $r_i$ and a deadline $d_i$.

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 $v_i$ at times within the relaxed time windows $[r_i-\varepsilon L_i,d_i+\varepsilon L_i]$, for fixed $\varepsilon>0$, where $L_i=d_i-r_i$; the running time is $O((nL_{max})^{O(\frac{\log L_{max}} {\log (1+\varepsilon)})})$, where $L_{max}=\max_i L_i$.

For TWPC, the computed path visits at least $k^*$ (the cardinality of an optimal solution to TWPC) sites; for TWTSP, the computed path is of length at most $\lambda^*$ (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, $\lambda^*(s)$, for the given speed $s$, while relaxing the speed to be a factor greater than $s$; for arbitrary time windows, we give an $O(\log n)$-approximation for TWTSP, assuming unbounded speed ($s=\infty$).