# Spatial Queues with Nearest Neighbour Shifts

B R Vinay Kumar

► To cite this version:

B R Vinay Kumar. Spatial Queues with Nearest Neighbour Shifts. ITC-35 - 35th International Teletraffic Congress, Oct 2023, Torino, Italy. 10.1109/ITC-3560063.2023.10555680. hal-04386596

HAL Id: hal-04386596

https://inria.hal.science/hal-04386596v1

Submitted on 10 Jan 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Spatial Queues with Nearest Neighbour Shifts

B. R. Vinay Kumar*

Centre Inria d'Université Côte d'Azur

Valbonne, France

vinay-kumar.bindiganavile-ramadas@inria.fr

*Abstract*—Motivated primarily by electric vehicles (EV) queueing at charging stations, in this work we study multiple server queues on a Euclidean space. We consider *N* servers that are distributed uniformly in $[0, 1]^d$. Customers or EV users arrive at the servers according to Poisson processes of intensity $\lambda$. However, they probabilistically decide whether to join the queue they arrived at, or move to one of the nearest neighbours. The strategy followed by the customers affects the load on the servers in the long run. In this paper, we are interested in characterizing the fraction of servers that bear a larger load as compared to when the users do not follow any strategy, i.e., they join the queue they arrive at. These are called overloaded servers. We evaluate the expected fraction of overloaded servers in the system for the one dimensional case ($d = 1$) when the users follow probabilistic nearest neighbour shift strategies. Simulations corroborate our theoretical findings.

*Index Terms*—queues, electric vehicles, Poisson process, nearest neighbour, spatial queues, jockeying

## I. INTRODUCTION

Electric vehicles (EV) have been touted to be the future of mobility. With increased adaptation of EVs, the charging infrastructure is also being scaled up. However, physical and financial constraints put a cap on the number of charging stations that can be deployed. In such a scenario, it is natural to expect EV users to adopt strategies in order to minimize their waiting times at charging stations. For example, a user on arriving at a charging station and finding it to be occupied, might decide to travel to a farther station in the hope that it would be empty. The user strategy affects the load that is perceived at the servers in the long run. Some of the servers get overloaded which might degrade the performance of the system on the whole. An understanding of the fraction of overloaded servers helps in optimal resource allocation preventing such degradation. Additionally, monitoring the fraction of overloaded servers can be used to incentivize customers to change their strategies thus increasing the durability of the entire system. Similar considerations arise in other practical networks involving queues, like supermarkets, airports etc.

Motivated by such applications, in this work we consider a set of *N* servers that are deployed in a Euclidean space with queues at each of them modelled as Poisson arrival processes. In the context of EVs, the servers are the charging stations, and a Poisson arrival process models the EV users arriving at a charging station. EV charging stations have been

modelled as a Poisson point process in two dimensional space in several previous works (see, for e.g., [1]–[3]). However, the problem that authors address in these works pertain to optimal placement of charging stations in the underlying space.

Another line of work that considers queues on spaces are polling systems. One of the earlier works in this domain [4] considers multiple queues in a convex space with a single server moving across to serve them. Several later works, such as [5], [6], study vehicle routes and delay in such systems. In all of these (and some related) works there is a single server and there is no interaction between different queues.

In contrast, in the present work we consider queues where customers from one queue probabilistically move to a queue which is located closest to it in the underlying space. Customers changing queues has been referred to as *jockeying* in the queueing theory terminology. There has been considerable work on jockeying in queues in the past [7]–[9]. The focus in these works is predominantly to analyse the steady-state distribution or find expected line-lengths or delays. However, they primarily consider two server systems with no spatial component in the problem.

The closest work to ours is [10] where the authors consider arrivals occurring on the two-dimensional torus, with multiple servers following a greedy strategy to serve the customers by travelling minimally. They find that such a strategy results in servers coalescing making the system inefficient. In contrast, in our work the servers are fixed whereas the arrivals follow nearest neighbour strategies and hence the two works are not directly comparable.

More precisely, in the current work, *N* servers are deployed in a Euclidean space and customers arriving into a queue decide whether to stay or to move to a queue nearest to them with a prescribed probability. We call such strategies as nearest neighbour shift (NNS) strategies. The metric of interest is the expected fraction of overloaded servers in the system which we characterize for users following an NNS strategy on a 1-d space. We begin by describing our system model in Section II followed by the analysis of NNS strategies for one dimension in Section III. Section IV provides numerical simulations justifying our results and Section V highlights some future directions.

## II. SYSTEM MODEL

Consider *N* servers distributed uniformly and independently within a finite area $\Gamma = [0, 1]^d$, $d \in \mathbb{N}$ equipped with the standard Euclidean metric. Let $\{X_i\}_{i=1}^N$ denote the locations

<footnote>Supported by the French government through the RISE Academy of UCAJEDI Investments in Future project managed by the National Research Agency (ANR) with reference number ANR-15-IDEX-0001.</footnote>
of the servers. A server $i$ is associated with a Poisson arrival process of intensity $\lambda$ denoted using $N_i(t)$ as a function of time $t$.

Customers on arriving at a queue can adopt different strategies. In this work, we consider all customers to be identical who make independent decisions. More specifically, we consider the following scenarios for the decisions that can be taken by a customer on arriving at a queue.

• **Strategy 1: Nearest neighbour shift (NNS)**

Customers join the same queue where they arrive with probability $p$, or join the closest server with probability $1-p$.

• **Strategy 2: k-nearest neighbour shift (k-NNS)**

Customers join the same queue where they arrive with probability $p$, or join one of the closest $k$ servers with probability $\frac{1-p}{k}$. For $k = 1$, this reduces to the NNS strategy.

In addition to the above scenarios, we define the *null strategy* wherein the customers arriving to a queue stay in the same queue. In all the strategies, the decision to join a queue is made only once. Specifically, a customer does not change the queue after joining a nearest neighbour queue. The reader is advised to note the distinction that is made between a customer *arriving* at a queue and *joining* a queue.

Our goal is to characterize the expected fraction of overloaded servers in the system. To go about this, we first define the load at a particular server as the asymptotic rate of the number of people joining the queue at that server. To be more precise, let $J_i(t)$ be the number of people who join server $i$ till time $t$. The asymptotic load (or just, load) at server $i$ is defined as

$$L_i := \lim_{t \to \infty} \frac{J_i(t)}{t}. \qquad (1)$$

We refer to this as the load since servers with a large value of $L_i$ have more arrivals in the long term as compared to servers with a small $L_i$ value, which degrades their performance.

Under the null strategy, the asymptotic load at a server is almost surely (a.s.) $L_i = \lambda$ for all $1 \le i \le N$. However, when the customers follow other strategies on arriving at a queue, the load on each server changes. Some servers will have a load larger than $\lambda$ and some smaller. Our interest is in the fraction of overloaded servers which is defined as

$$R := \frac{\left| \left\{ i : \lim_{t \to \infty} \frac{J_i(t)}{t} > \lambda \text{ a.s.} \right\} \right|}{N}, \qquad (2)$$

where $|\cdot|$ denotes the cardinality.

In this paper, we analyze the nearest neighbour shift strategies and characterize the expected fraction of overloaded servers when the dimension $d = 1$. In the process of doing so, we also obtain the expected fraction of servers with all possible loads.

Before we proceed, we remark here on the boundary conditions for the underlying space $[0, 1]^d$. Since servers are uniformly distributed, the fraction of servers that fall near the boundary diminishes as $N$ increases. Thus, neglecting the servers on the boundary does not affect the fraction of overloaded servers in (2) for large $N$. Alternately, this also

<figure><img src="image_2.png" /><figcaption>Fig. 1: EVs arriving as a Poisson process into charging stations distributed as a Poisson point process on $[0, 1]$.</figcaption></figure>

means that we are allowed to take any boundary conditions that renders the analysis easy. In the case of dimension $d = 1$, we take fixed boundary conditions where the servers closest to 0 and 1 constitute the boundary servers. Taking toroidal boundary conditions by gluing the ends 0 and 1 together does not alter our results. However, some of the arguments in our proofs have to be made differently.

### III. ONE DIMENSION $d = 1$

The case of dimension $d = 1$ is interesting in its own right since it can be motivated by numerous applications. With reference to the examples discussed in the introduction, EV charging stations located on a highway and checkout counters at supermarkets correspond to queues on a 1-d space. An illustration for a 1-d system is provided in Fig. 1.

In this section, we first provide some preliminaries in Section III-A required for the case of $d = 1$. We define and analyze a deterministic strategy called oNNS in Section III-B that will aid us in the analysis of the probabilistic NNS strategies which is done in Section III-C.

#### A. Preliminaries

The primary tool that we will use in the 1-d case are the order statistics of the server locations which we define below.

Let $\mathbf{X} = (X_1, \dots, X_N)$ be independent and identically distributed (iid) random variables from a distribution $F(\cdot)$ with density $f(\cdot)$ supported on $[0, 1]$. If $X_1, \dots, X_N$ are arranged in order of magnitude and then written as $X_{(1)} \le X_{(2)} \le \dots \le X_{(N)}$, then $X_{(i)}$ is called the $i$-th order statistic for $i = 1, \dots, N$. Together, $X_{(1)}, X_{(2)}, \dots, X_{(N)}$ are referred to as the order statistics of $X_1, \dots, X_N$.

The following are some facts about order statistics that will be used in our analysis (see for eg., [11], [12]). These are stated for $f(x) = 1\{x \in [0, 1]\}$ and $F(x) = \int_0^x f(x)dx$ since in our case the servers are distributed uniformly in $[0, 1]$.

• **Fact 1:** Conditioned on $X_{(i)} = a$, the random variables $X_{(1)}, \dots, X_{(i-1)}$ are the order statistics of

$$Y_1, \dots, Y_{i-1} \stackrel{\text{iid}}{\sim} \text{Unif}([0, a]), \qquad (3)$$

and $X_{(i+1)}, \dots, X_{(N)}$ are the order statistics of

$$Y_{i+1}, \dots, Y_N \stackrel{\text{iid}}{\sim} \text{Unif}([a, 1]), \qquad (4)$$
and, moreover $X_{(1)}, \dots, X_{(i-1)}$ are (conditionally) independent of $X_{(i+1)}, \dots, X_{(N)}$.

* **Fact 2:** The joint density of the i-th and the j-th order statistic for $i < j$ is given by

$$f_{i,j}(r,s) = \frac{N!}{(i-1)!(j-i-1)!(N-j)!} F(r)^{i-1} f(r) \times [F(s) - F(r)]^{j-i-1} f(s) [1 - F(s)]^{N-j}. \quad (5)$$

## B. Only nearest neighbour shift (oNNS)

Before investigating the NNS and the k-NNS strategies which are probabilistic in nature, we look into a deterministic strategy called only nearest neighbour shift or oNNS for short. This will help us to address the probabilistic strategies.

In the oNNS strategy, customers on arriving at queue i join the queue at the nearest neighbour of i. The arrivals to servers on the boundary ($X_{(1)}$ and $X_{(N)}$) join the adjacent queues ($X_{(2)}$ and $X_{(N-1)}$ respectively).

As a first observation, notice that the asymptotic load at any server for users following the oNNS strategy can take on the values $L_i \in \{0, \lambda, 2\lambda\}, 1 \le i \le N$ almost surely. This is because arrivals to the left and right neighbours of server i could both join the queue at i resulting in $L_i = 2\lambda$ a.s.. If only arrivals to one of the neighbours of i join the queue at i, $L_i = \lambda$ a.s. and if neither join the queue at i, it results in $L_i = 0$ a.s.. Owing to this, we define the fraction of servers with load $k\lambda$ as

$$R_k := \frac{\left| \left\{ i : \lim_{t \to \infty} \frac{J_i(t)}{t} = k\lambda \text{ a.s.} \right\} \right|}{N},$$

for $k = 0, 1, 2$. Since there are $N$ queues with equal arrival rates of $\lambda$, we have that $R_0 + R_1 + R_2 = 1$. The expected fraction of servers with loads of $0, \lambda, 2\lambda$ is characterized in the following theorem.

**Theorem III.1.** For $N$ servers distributed uniformly in $[0, 1]$ with Poisson arrivals of intensity $\lambda$ following the oNNS strategy, we have

$$\mathbb{E}R_0 = \frac{1}{4}, \quad \mathbb{E}R_1 = \frac{1}{2}, \quad \text{and} \quad \mathbb{E}R_2 = \frac{1}{4}.$$

*Proof.* Let $X_{(1)}, \dots, X_{(N)}$ denote the order statistics of the location of the $N$ servers. In the following discussion, node $i$ will refer to the i-th order statistic. The asymptotic load at node $i$ is 0 if the arrivals to both the (i-1)-th and the (i+1)-th node do not join the i-th node. This happens if and only if both the events $E_i^+ := \{X_{(i+2)} - X_{(i+1)} < X_{(i+1)} - X_{(i)}\}$ and $E_i^- := \{X_{(i-1)} - X_{(i-2)} < X_{(i)} - X_{(i-1)}\}$ occur simultaneously. We first compute the probability of the event $E_i^+ \cap E_i^-$.

From Fact 1 of Section III-A, conditioned on the value of $X_{(i)} = x$, the events $E_i^+$ and $E_i^-$ are independent. Thus

$$\mathbb{P}(E_i^+ \cap E_i^-) = \int_0^1 \mathbb{P}(X_{(i+2)} > 2X_{(i+1)} - x | X_{(i)} = x) \mathbb{P}(X_{(i-2)} > 2X_{(i-1)} - x | X_{(i)} = x) f_{X_{(i)}}(x) dx, \quad (6)$$

where $f_{X_{(i)}}(\cdot)$ is the density of the i-th order statistic. We will now evaluate each of the probabilities in the above expression using (3), (4) and (5). For this, we first write down the joint

<figure><img src="image_3.png" /><figcaption>Fig. 2: Illustration for the load at node $X_{(i)}$ being 0.</figcaption></figure>

<table><caption>TABLE I: Asymptotic load of a node as a function of inter-node distances. (Replace ? by the inequality.)</caption><thead><tr><th>Y<sub>i</sub> ? Y<sub>i-1</sub></th><th>Y<sub>i+2</sub> ? Y<sub>i+1</sub></th><th>lim<sub>t→∞</sub> <sup>J<sub>i</sub>(t)</sup>/<sub>t</sub></th></tr></thead><tbody><tr><td>&lt;</td><td>&lt;</td><td>1</td></tr><tr><td>&lt;</td><td>&gt;</td><td>2</td></tr><tr><td>&gt;</td><td>&lt;</td><td>0</td></tr><tr><td>&gt;</td><td>&gt;</td><td>1</td></tr></tbody></table>

distribution of the j-th and the (j+1)-th order statistic using (5) as follows:

$$f_{j,j+1}(r,s) = N! \frac{F(r)^{j-1} f(r) f(s) (1-F(s))^{N-j-1}}{(j-1)!(N-j-1)!}. \quad (7)$$

Using (3), (4) with (7) we find that

$$\begin{aligned} \mathbb{P}(X_{(i-2)} > 2X_{(i-1)} - x | X_{(i)} = x) \\ = \int_0^x \int_0^s \frac{(i-1)!}{(i-3)!} \left( \frac{r^{i-3}}{x^{i-1}} \right) dr ds \\ - \int_{\frac{x}{2}}^x \int_0^{2s-x} \frac{(i-1)!}{(i-3)!} \left( \frac{r^{i-3}}{x^{i-1}} \right) dr ds = \frac{1}{2}, \end{aligned}$$

and similarly $\mathbb{P}(X_{(i+2)} > 2X_{(i+1)} - x | X_{(i)} = x) = \frac{1}{2}$. Substituting this in (6), we obtain

$$\mathbb{P}(E_i^+ \cap E_i^-) = \int_0^1 \frac{f_{X_{(i)}}(x)}{4} dx = \frac{1}{4}.$$

Since $\mathbb{E}R_0 = \frac{1}{N}\mathbb{E}[\sum_{i=1}^N 1\{E_i^+ \cap E_i^-\}]$, we have that $\mathbb{E}R_0 = \frac{1}{4}$. Similar computations for $\mathbb{E}R_1$ and $\mathbb{E}R_2$ can be shown which prove the theorem. $\square$

An intuitive interpretation for the previous result stems from the distribution of consecutive order statistics, also referred to as uniform spacings. Define the inter-node distances $Y_j = X_{(j)} - X_{(j-1)}$ for $j \in \{i-1, i, i+1, i+2\}$ (see Fig. 2). The asymptotic load at node $i$ as a function of these distances is shown in Table I. Since the nodes are uniformly distributed, each row of Table I has equal probability of $\frac{1}{4}$ each. Using these probabilities to compute the expected value of $R_k$ as in the end of the proof of Theorem III.1, we have the desired result. In fact, a stronger statement to Theorem III.1 holds for $R_0$ and $R_2$ which is stated below.

**Proposition III.2.** For $N$ servers distributed uniformly in $[0, 1]$ with Poisson arrivals of intensity $\lambda$ following the oNNS strategy, we have

$$R_0 = R_2 \quad \text{a.s.}$$

*Proof.* The arguments in this proof are made for each realization in the underlying probability space. Recall that $L_i$ was defined to be the asymptotic load at server $i$, i.e., $L_i = \lim_{t \to \infty} \frac{J_i(t)}{t} \in \{0, \lambda, 2\lambda\}$. Note that $\sum_i \frac{L_i}{N\lambda} = 1 = R_0 + R_1 + R_2$. Define $S_i := \frac{L_i}{\lambda}$ so that $\sum_{i=1}^N S_i = N$. The
<figure><img src="image_4.png" /><figcaption>Fig. 3: Illustration for $R_0 = R_2$ a.s.. An arrow from server $i$ to server $j$ indicates that customers arriving at server $i$ join the queue at $j$. $L_i$ denotes the asymptotic load at server $i$.

proof is divided into two cases. See Fig. 3 for an illustration of the two cases.</figcaption></figure>

**Case 1: $R_0 = 0$**

Owing to the fixed boundary conditions, the closest neighbour to the queue at $X_{(1)}$ is the queue at $X_{(2)}$. The only possible way that $R_0 = 0$ is if arrivals to $X_{(2)}$ join the queue at $X_{(1)}$. Now suppose that the arrivals to the queue at $X_{(3)}$ join $X_{(2)}$, then $\sum_{i=3}^N S_i = N - 3$ since $S_1 = 1$ and $S_2 = 2$. For this to hold at least one of the summands, $S_i$, needs to be equal to zero. However, this is not possible since $R_0 = 0$. Therefore, arrivals to $X_{(3)}$ cannot join $X_{(2)}$ but must join $X_{(4)}$ resulting in $S_1 = S_2 = 1$. The nodes from $X_{(3)}$ to $X_{(N)}$ now form a system of $N - 2$ nodes with the property that $R_0 = 0$. Recursing over the same argument, we obtain $S_i = 1$ for all $i \in [N]$. Equivalently $R_0 = R_2 = 0$.

**Case 2: $R_0 > 0$**

Let node $i$ be such that $S_i = 0$. Suppose that the arrival to node $i$ joins $X_{(i+1)}$ (a similar argument goes through if it joins $X_{(i-1)}$ instead). Since $S_i = 0$, arrivals to $X_{(i+1)}$ should join $X_{(i+2)}$. For $j \ge 2$, arrivals to $X_{(i+j)}$ can join either $X_{(i+j-1)}$ or $X_{(i+j+1)}$. If for some $j$, arrivals to $X_{(i+j)}$ join $X_{(i+j-1)}$ then $S_{i+j-1} = 2$. Note that there must always exist such a node $j$ owing to our boundary conditions that arrivals to nodes 0 and $N$ join nodes 1 and $N-1$ respectively. Thus $S_i = 0$, $S_{i+1} = 1, \dots, S_{i+j-2} = 1$ and $S_{i+j-1} = 2$. Removing the nodes $k \in \{i, \dots, i+j-1\}$ results in $N-j$ nodes with $NR_0-1$ number of nodes with 0 asymptotic load. Repeating the same procedure by choosing a node $i'$ with $S_{i'} = 0$ iteratively decrements the value of $NR_0$ in each iteration, finally resulting in $NR_0 = 0$. The remaining nodes have an asymptotic load of $\lambda$ each. Note that each removal step comprises of a node with $S_i = 0$ and a node with $S_{i+j-1} = 2$. This shows that $R_0 = R_2$ pointwise from which the statement of the lemma follows. $\square$

We are now in a position to tackle the probabilistic NNS strategies.

### C. Nearest neighbour shift (NNS)

We first establish additional terminologies to convey the ideas clearly. Designate a customer as lazy if on arrival at a queue, the user joins it with probability $p$, or as active if the user joins the nearest queue with probability $1-p$.

Denote the fraction of servers with an asymptotic load of $s\lambda$ by

$$R_s := \frac{|\{i : \lim_{t \to \infty} \frac{J_i(t)}{t} = s\lambda \text{ a.s.}\}|}{N}.$$

The following theorem characterizes the expected value of $R_s$ for all possible asymptotic loads $s$ in the NNS strategy.

<figure><img src="image_5.png" /><figcaption>Fig. 4: Arrival process decomposition into lazy and active users. The arrows indicate the shifts to the nearest neighbours for active users.</figcaption></figure>

**Theorem III.3.** For $N$ servers distributed uniformly in $[0, 1]$ with Poisson arrivals of intensity $\lambda$ following the NNS strategy with lazy probability $p$, we have

$$\mathbb{E}R_p = \frac{1}{4}, \quad \mathbb{E}R_1 = \frac{1}{2}, \quad \text{and} \quad \mathbb{E}R_{2-p} = \frac{1}{4}.$$

*Proof.* First, we find the asymptotic loads that are possible for each server. Owing to the thinning property of the Poisson process, the arrivals to queue $i$ can be decomposed into two independent Poisson processes: the lazy process $N_i^L(t)$ of intensity $\lambda p$ and the active process $N_i^A(t)$ of intensity $\lambda(1-p)$ as shown in Fig. 4. Accordingly, the contribution towards the load at server $i$ comprises of the lazy component $J_i^L(t)$ from arrivals $N_i^L(t)$, and the active component $J_i^A(t)$ from nearest neighbours of $i$ whose arrivals join the queue at $i$. The asymptotic load at any node $i$ is given by $\lim_{t \to \infty} \frac{J_i(t)}{t} = \lim_{t \to \infty} \frac{J_i^L(t)}{t} + \lim_{t \to \infty} \frac{J_i^A(t)}{t}$. For the lazy component $\lim_{t \to \infty} \frac{J_i^L(t)}{t} = p\lambda$ a.s., since arrivals of $N_i^L(t)$ contribute to $J_i^L(t)$. For the active component, arrivals in $N_i^A(t)$ behave as in the oNNS strategy. Since $N_i^A(t)$ is a Poisson arrival process of intensity $\lambda(1-p)$, we obtain,

$$\lim_{t \to \infty} \frac{J_i^A(t)}{t} \in \{0, \lambda(1-p), 2\lambda(1-p)\} \quad \text{a.s..}$$

Hence the possible asymptotic loads are

$$\lim_{t \to \infty} \frac{J_i(t)}{t} \in \{p\lambda, \lambda, (2-p)\lambda\} \quad \text{a.s..}$$

Next, we find the expected fraction of servers with each of the individual asymptotic loads computed above. To illustrate, consider

$$\begin{aligned} \mathbb{E}R_p &= \frac{1}{N} \mathbb{E} \left[ \sum_{i=1}^{N} \mathbf{1} \left\{ \lim_{t \to \infty} \frac{J_i(t)}{t} = p\lambda \right\} \right] \\ &= \frac{1}{N} \sum_{i=1}^{N} \mathbb{P} \left( \lim_{t \to \infty} \frac{J_i^L(t)}{t} = p\lambda \text{ and } \lim_{t \to \infty} \frac{J_i^A(t)}{t} = 0 \right) \end{aligned}$$

The two events are independent since they are functions of independent Poisson processes $N_i^L(t)$ and $N_i^A(t)$. The term $\mathbb{P}(\lim_{t \to \infty} \frac{J_i^L(t)}{t} = p\lambda)$ corresponds to the null strategy in the lazy component and is equal to 1. The term $\mathbb{P}(\lim_{t \to \infty} \frac{J_i^A(t)}{t} = 0)$ can be obtained via the oNNS strategy for the active component. Using Theorem III.1 for the active component $N_i^A(t)$ yields $\mathbb{E}R_p = \frac{1}{4}$.
<figure><img src="image_6.png" /><figcaption>Fig. 5: Histogram of the number of overloaded servers and the servers with no change in load for different probability values of the 1-NNS strategy in one dimension.</figcaption></figure>

Similar derivations follow for the expected fraction of servers with other asymptotic loads giving $ER_1 = \frac{1}{2}$, and $ER_{2-p} = \frac{1}{4}$. □

Notice that when $p = 0$ we obtain Theorem III.1 for the oNNS strategy and for $p = 1$, we obtain $ER_1 = 1$ corresponding to the null strategy.

In one dimension, the *k*-NNS strategies for $k > 2$ are not practically relevant for the application of electric vehicles. This is because customers when restricted to a line choose one of the directions –left (with prob. $\ell$) or right (with prob. $r$)– and proceed to the nearest server in that direction (or stay in the same queue with prob. $1 - r - \ell$). For such a *left*-right nearest neighbour shift (LR-NNS) strategy, the following theorem asserts that there are no overloaded servers. The proof is similar to that of Theorem III.3 and is omitted here.

**Theorem III.4.** For *N* servers distributed uniformly in $[0, 1]$ with Poisson arrivals of intensity $\lambda$ following the LR-NNS strategy with parameters *r* and $\ell$ we have $ER_1 = 1$.

## IV. NUMERICAL RESULTS

In this section, we present simulation experiments justifying our results. We consider *N* = 1000 charging stations deployed uniformly in $[0, 1]$, each of which is associated with an independent arrival process of intensity $\lambda = 1$. The arrival process is simulated for *t* = 1000 time units with each arrival being lazy with probability *p* or active with probability $1-p$. The probability parameter *p* is chosen from the set $\{0, 0.25, 0.5, 0.75\}$, where *p* = 0 corresponds to the oNNS strategy. Figure 5 plots the histogram of the observed number of overloaded servers ($NR_{2-p}$) and the servers with no change in load ($NR_1$) over 1000 instantiations of the charging station locations in the one dimension case. The expected number of overloaded servers is concentrated well around the mean of $N/4 = 250$ irrespective of the probability *p* corroborating with Theorem III.3.

## V. CONCLUSIONS AND FUTURE WORK

In this paper, we consider multiple servers on a 1-d Euclidean space. Each server is associated with a Poisson queue of intensity $\lambda$. Customers in each queue follow a probabilistic

policy to either remain in the queue or join a nearest neighbour. In this setting, we evaluate the expected fraction of overloaded servers in the stationary regime. It is to be noted that similar computations can be performed for other distributions of the servers since they rely on just the order statistics.

Numerous related questions arise regarding the fraction of overloaded servers, *R*, some of which are listed below:

* What is the distribution of *R*? While in this paper we only address the mean of *R*, distributional characteristics such as concentration bounds and moments will be addressed in a future publication.

* How does *R* behave in higher dimensions? In particular, the case of *d* = 2 is important for the applications discussed in the introduction. Note that the techniques used in this paper cannot be extended since order statistics are particular to one dimension.

* How does *R* behave for strategies where the probability parameters depend on the state of the queue? In this work, we consider the stationary regime for the queues. In contrast, when the shift probabilities depend on transient queue parameters, such as queue length, or on the ambient space, characterization of *R* is an interesting research direction.

* How does the ambient space impact *R*? If factors from the Euclidean space such as traversal times to other queues are considered, several classical queueing questions (delay, wait times etc.) can be formulated which might be interesting in their own right.

It is clear that there are numerous questions that have to be addressed and that there is ample scope for future work.

## REFERENCES

[1] G. Dong, J. Ma, R. Wei, and J. Haycox, "Electric vehicle charging point placement optimisation by exploiting spatial statistics and maximal coverage location models," *Transportation Research Part D: Transport and Environment*, vol. 67, pp. 77–88, Feb. 2019.

[2] C. Ren and Y. Hou, *A Novel Evaluation Method of Electric Vehicles Charging Network Based on Stochastic Geometry*, Oct. 2020, pages: 468.

[3] R. Atat, M. Ismail, and E. Serpedin, "Stochastic Geometry Planning of Electric Vehicles Charging Stations," in *Proc. International Conference on Acoustics, Speech and Signal Processing (ICASSP)*, May 2020, pp. 3062–3066.

[4] E. Altman and H. Levy, "Queueing in Space," *Advances in Applied Probability*, vol. 26, no. 4, pp. 1095–1116, 1994.

[5] V. Kavitha and E. Altman, "Queueing in space: Design of message ferry routes in static ad hoc networks," in *2009 21st International Teletraffic Congress*, Sep. 2009, pp. 1–8.

[6] G. D. Çelik and E. Modiano, "Dynamic vehicle routing for data gathering in wireless networks," in *49th IEEE Conference on Decision and Control (CDC)*, Dec. 2010, pp. 2372–2377.

[7] E. Koenigsberg, "On Jockeying in Queues," *Management Science*, Jan. 1966.

[8] S. A. Dudin, O. S. Dudina, and O. I. Kostyukova, "Analysis of a Queuing System with Possibility of Waiting Customers Jockeying between Two Groups of Servers," *Mathematics*, vol. 11, no. 6, p. 1475, Jan. 2023.

[9] B. Lin, Y. Lin, and R. Bhatnagar, "Optimal Policy for Controlling Two-Server Queueing Systems with Jockeying," *Journal of Systems Engineering and Electronics*, vol. 33, no. 1, pp. 144–155, Feb. 2022.

[10] K. W. Stacey and D. P. Kroese, "Greedy servers on a torus," in *Proceedings of the 2011 Winter Simulation Conference (WSC)*, Dec. 2011, pp. 369–380.

[11] H. A. David and H. N. Nagaraja, *Order statistics*. John Wiley & Sons, 2004.

[12] S. Ross, *A first course in probability*. Pearson, 2010.