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$).