A Geometrically Convergent Solution to Spatial Hypercube Queueing Models

The hypercube queueing model was developed initially to address spatial queueing problems and has found wide application in emergency services, such as ambulance and police systems. Although the model was designed originally for homogeneous service rates, we extend it to handle heterogeneous service rates by devising an exact solution through a birth-death process and an equivalent reformulation. We demonstrate that our algorithm converges to the exact solution at a geometric rate. Additionally, we developed a parallel algorithm that leverages the convergence property and two structural features of the hypercube model, achieving more than 91% parallelization. Numerical experiments on emergency medical service systems show that our sequential algorithm is more than 1,000 times faster than the sparse solver and more than 500 times faster than discrete-event simulation while maintaining high accuracy. The parallel algorithm further improves efficiency, achieving an approximately eightfold speedup with 12 processing units, with additional gains possible when more computational resources are available. Overall, the proposed algorithms improve computational efficiency and enable the solution of large-scale problems that are otherwise intractable using traditional approaches.

History: Accepted by Alice E. Smith, Nicola Secomandi/Stochastic Models & Reinforcement Learning.

Funding: C. Hua was partly supported by the National Natural Science Foundation of China [72301172, 72394375, 72495132] and Shanghai Jiao Tong University Office of Liberal Arts [ZHWK2502]. J. Luo was supported by the National Natural Science Foundation of China [72542012, 72571170, 72031006].

Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2025.1353) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2025.1353). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/.