Adaptive Routing on the Plane

Leandros Tassiulas
Additional contact information
Leandros Tassiulas: University of Maryland, College Park, Maryland

Operations Research, 1996, vol. 44, issue 5, 823-832

Abstract: 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.

Keywords: queues; algorithms; Markovian network/graphs routing; stochastic traveling salesman; transportation; vehicle routing (search for similar items in EconPapers)
Date: 1996
References: Add references at CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.44.5.823 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:44:y:1996:i:5:p:823-832

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().