Characterization of the Stochastic Median Queue Trajectory in a Plane with Generalized Distances

We characterize the trajectory of the Stochastic Queue Median (SQM) location problem in a planar region with discrete demands and a general L_p travel metric (1 < p < ∞). The location objective is to minimize expected response time to customers (i.e., travel time plus queue delay). We use an ε-perturbed version of the SQM objective function (to account for points of nondifferentiability) to show that for the ε-perturbed problem the optimal SQM location occurs in a region bounded by the point minimizing the first and second moments of service time (s*∣ε and s2*∣ε, respectively); all optimal locations can be characterized by a simple ratio condition relating the derivatives of the first and second moments of service time; and the trajectory as a function of the customer call rate moves monotonically along a path from s*∣ε toward s2*∣ε, then turns and retraces the same path back to s*∣ε. Finally, we establish convergence of the ε-optimal solution to an optimal SQM solution as ε approaches zero, as well as a general condition under which we can solve the SQM problem directly, with no perturbation.