TRAJECTORY ANALYSIS OF THE STOCHASTIC QUEUE MEDIAN IN A PLANE WITH RECTILINEAR DISTANCES

In this paper we analyze the trajectory of stochastic queue median (SQM) location problem in a planar region with a rectilinear travel metric. The location objective is to minimize expected response time to customers (that is, travel time plus queue delay). We introduce a methodology for parametric analysis of planar location problems which is potentially applicable to other location problems as well. Using the methodology, we demonstrate strong parallels between our planar SQM problem and the same problem on a tree network. We show how the optimal SQM location must occur in a certain region of the plane. Given a mild regularity condition, we develop trajectory results for the optimal location as a function of the customer call rate, and we derive a simple necessary and sufficient ratio condition which characterizes points on the optimal trajectory, and present an algorithm for finding that trajectory. We also analyze the problem in the degenerate case when the regularity condition in violated. We also analyze the problem in the degenerate case when the regularity condition is violated. Finally, we extend our results to the planar stochastic expected queue median problem, which incorporates stochastic travel times.