Generalized Hypercube Queueing Models with Overlapping Service Regions

Abstract

Motivated by the operations of the Atlanta Police Department, where heavy workloads and staffing shortages increasingly require units to patrol across overlapping service regions, we develop a generalized hypercube queueing model, extending Larson (1974), for spatial service systems with overlapping coverage. Designing effective service regions requires capturing both workload and the operations of mobile servers such as police units. The classical hypercube model, which tracks only whether each server is busy or idle, is well suited to light traffic but inadequate for congested systems with server-specific queues and restricted service regions. We model the system as a Markov chain on a nonnegative integer-valued state space and develop a sparse truncated hyperlattice approximation for efficient steady-state computation and performance evaluation. We further characterize the workloads attainable under stable dispatch policies, establish conditions for stabilizability, and identify dispatch policies that optimally balance workloads. We validate the model through simulation and apply it to the Atlanta Police Department, where rising workloads, staffing shortages, and boundary effects create significant operational challenges. Using real 911 calls-for-service data, our analysis indicates that a police operations system with permitted overlapping patrols can significantly mitigate these problems, leading to more effective deployment of the police force. Although the paper focuses on police districting applications, the generalized hypercube queueing model is applicable to other mobile server models in the general setup.