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 < infinity). The location objective is to minimize expected response time to customers (i.e., travel time plus queue delay). We use an epsilon-perturbed version of the SQM objective function (to account for points of nondifferentiability) to show that for the epsilon-perturbed problem the optimal SQM location occurs in a region bounded by the point minimizing the first and second moments of service time (s* \ epsilon and s2* \ epsilon, 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* \ epsilon toward s2* \ epsilon, then turns and retraces the same path back to s* \ epsilon. Finally, we establish convergence of the epsilon-optimal solution to an optimal SQM solution as epsilon-approaches zero, as well as a general condition under which we can solve the SQM problem directly, with no perturbation.