Trajectory analysis of the stochastic queue median in a plane with rectilinear distances

In this paper the authors 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). The authors introduce a methodology for parametric analysis of planar location problems which is potentially applicable to other location problems as well. Using the methodology, they demonstrate strong parallels between the present planar SQM problem and the same problem on a tree network. The authors show how the optimal SQM location must occur in a certain region of the plane. Given a mild regularity condition, they develop trajectory results for the optimal location as a function of the customer call rate, and derive a simple necessary and sufficient ratio condition which characterizes points on the optimal trajectory, and presents an algorithm for finding that trajectory. The authors also analyze the problem in the degenerate case when the regularity condition is violated. Finally, they extend their results to the planar stochastic expected queue median problem, which incorporates stochastic travel times.