In this paper the problem of efficiently serving a sequence of requests pre
sented in an on-line fashion located at points of a metric space is conside
red. We call this problem the On-Line Travelling Salesman Problem (OLTSP).
It has a variety of relevant applications in logistics and robotics.
We consider two versions of the problem. In the first one the server is not
required to return to the departure point after all presented requests hav
e been served. For this problem we derive a lower bound on the competitive
ratio of 2 on the real line. Besides, a 2.5-competitive algorithm for a wid
e class of metric spaces, and a 7/3-competitive algorithm for the real line
are provided.
For the other version of the problem, in which returning to the departure p
oint is required, we present an optimal 2-competitive algorithm for the abo
ve-mentioned general class of metric spaces. If in this case the metric spa
ce is the real line we present a 1.75-competitive algorithm that compares w
ith a approximate to1.64 lower bound.