Optimal Server Location on a Network Operating as an <i>M</i>/<i>G</i>/1 Queue

Abstract

This paper extends Hakimi's one-median problem by embedding it in a general queueing context. Demands for service arise solely on the nodes of a network G and occur in time as a Poisson process. A single mobile server resides at a facility located on G. The server, when available, is dispatched immediately to any demand that occurs. When a demand finds the server busy with a previous demand, it is either rejected (Model 1) or entered into a queue that is depleted in a first-come, first-served manner (Model 2). Service time for each demand comprises travel time to the scene, on-scene time, travel time back to the facility and possibly additional off-scene time. One desires to locate the facility on G so as to minimize average cost of response, which is either a weighted sum of mean travel time and cost of rejection (Model 1), or the sum of mean queueing delay and mean travel time. For Model 1, one finds that the optimal location reduces to Hakimi's familiar nodal result. For Model 2, nonlinearities in the objective function can yield an optimal solution that is either at a node or on a link. Properties of the objective function for Model 2 are utilized to develop efficient finite-step procedures for finding the optimal location. Certain interesting properties of the optimal location as a function of demand rate are also developed.