On the inaccuracy of Pollaczek-Khinchine for spatial FCFS queues

In this paper, we consider a single-server queueing system operating under the First-Come First-Served discipline within a spatial context. In contrast to traditional models where customers visit a central service location, our model features a server who travels to customers at random locations within a designated region. This model is primarily inspired by applications in home healthcare, especially for unplanned care activities, whereas it also applies to emergency services and on-demand delivery systems. By incorporating travel time between customers along with on-site service, we find that the aggregate service times of successive customers are dependent, deviating from the assumptions of the classical M/G/1 model. Consequently, despite a previous claim, we find that the traditional Pollaczek-Khinchine (PK) formula for M/G/1 queues does not apply exactly, although it remains a reasonably accurate approximation. We propose an improved approximation that accounts for the dependency between successive travel times, providing insights into the limitations of the PK formula in this context. Additionally, we offer a closed-form analysis for scenarios where there is a finite set of potential demand points, establishing a connection between expected delays and the PK formula.