Adaptive routing on the plane

Demands for service arrive at random times, in random locations, in a region of the plane. The service time of each demand is random. A server that travels with constant speed moves from demand to demand providing service. The server spends its time either in providing service or in traveling. The objective is to route the server, based on the location of the current demands on the plane and the anticipated demand arrivals, such that the time spent in traveling is minimal and the service is provided efficiently. A routing policy is provided that achieves maximum throughput and is independent of the statistical parameters of the system, under the assumption that the arrival process is Poisson. For a renewal arrival process, a class of policies is specified that achieve maximum throughput based on some knowledge of the system parameters. Finally, an adaptive version of the partitioning policies is given, which makes them independent of the system statistics.