Optimal M/G/1 server location on a tree network with continuous link demands (Q1090221)

This paper represents two major extensions of Hakimi's one-median problem specialized on a tree network T: (i) queueing delay is explicitly included in the objective function, and (ii) probabilistic demands for service can originate continuously along a link as well as discretely at a node. Calls for service occur as a time-homogeneous Poisson process. A single mobile server resides at a facility located on T. The server, when available, is dispatched immediately to any demand that occurs. When a customer finds the server busy with previous demand, it is entered into a first-come first-served queue. One desires to locate a facility on T so as to minimize the average response time, which is the sum of mean queueing delay and mean travel time. Convexity properties of the average response time and related functions allow us to develop an efficient two- stage algorithm for finding the optimal location. We also analytically trace the trajectory of the optimal location when the Poisson arrival rate is varied. A numerical example is constructed to demonstrate the algorithm as well as the trajectory results.