On the Power of Temporal Locality on Online Routing Problems

We consider the online variants of two fundamental routing problems, traveling salesman (TSP) and dial-a-ride (DRP), which have a variety of relevant applications in logistics and robotics. These problems concern with eciently serving a sequence of requests presented in an on-line fashion located at points of a metric space by servers (salesmen/repairmen/vehicles/robots). In this paper, we propose the temporal locality model that provides in advance the time interval between the release of subsequent request(s). We study the usefulness of this advanced information on achieving the improved competitive ratios for both the problems with : 1 servers. We show the surprising impact: shorter locality is useful for arbitrary metric but for line metric larger locality.