key: cord-326740-1fjr9qr4
authors: Perlman, Yael; Yechiali, Uri
title: Reducing Risk of Infection - the COVID-19 Queueing Game
date: 2020-09-03
journal: Saf Sci
DOI: 10.1016/j.ssci.2020.104987
sha: 
doc_id: 326740
cord_uid: 1fjr9qr4

The COVID-19 pandemic has forced numerous businesses such as department stores and supermarkets to limit the number of shoppers inside the store at any given time to minimize infection rates. We construct and analyze two models designed to optimize queue sizes and customer waiting times to ensure safety. In both models, customers arrive randomly at the store and, after receiving permission to enter, pass through two service phases: shopping and payment. Each customer spends a random period of time shopping (first phase) and then proceeds to the payment area of the store (second phase) where cashiers are assigned to serve customers. We propose a novel approach by which to calculate the risk of a customer being infected while queueing outside the store, while shopping, and while checking out with a cashier. The risk is proportional to the second factorial moment of the number of customers occupying the space in each phase of the shopping route. We derive equilibrium strategies for a Stackelberg game in which the authority acts as a leader who first chooses the maximum number of customers allowed inside the store to minimize the risk of infection. In the first model, store’ management chooses the number of cashiers to provide to minimize its operational costs and its customers’ implied waiting costs based on the number allowed in the store. In the second model, the store partitions its total space into two separate areas – one for shoppers and one for the cashiers and payers – to increase cashiers’ safety. Our findings and analysis are useful and applicable for authorities and businesses alike in their efforts to protect both customers and employees while reducing associated costs.

The COVID-19 pandemic has upended nearly every type of business, but one of the more dramatic impacts early in the pandemic has been long queues of customers outside supermarkets.

The need to reduce crowding and queueing has forced store managers worldwide to implement regulations such as "maximum shoppers at store" and "maximum number of customers in checkout areas." According to a recent report by BBC News (2020), supermarkets in the United Kingdom are posting staff members at the doors who allow a maximum of 75 shoppers inside the store at a time. Israeli i24News (2020) reports that all business owners in Israel are required to place signs at store entrances specifying the maximum number of people allowed on the premises. As a result of these maximum headcount policies, sometimes-long queues are forming outside these businesses.

Evidence is growing that infection with COVID-19 is associated with prolonged periods of exposure to infected individuals (CNN, 2020) . The longer one spends in a crowded environment with people who may be infected, the greater the risk of getting sick (Barr, 2020) .

Therefore, greater numbers of people in stores and queues increase the likelihood of infection and make it difficult to ensure that social distancing restrictions are maintained (Long et al., 2020) .

Customers waiting outside of stores can maintain adequate social distance but are still potentially exposed to infection (Gupta et al., 2020) . It is also critical to keep workers safe during the pandemic, and greater efforts are needed to reduce the number of customers waiting at cashier areas to allow employees to maintain social distance from customers (see, e.g., Government of the United Kingdom (2020)). Thus, it is critical to control and manage queue sizes and customer waiting times to ensure the safety of customers and workers.

Systems for reducing the number customers in retail stores and reducing waiting times have been studied intensively in the literature using queueing theory. Recently, several queueing models have been constructed to study the impact of the COVID-19 pandemic (see, e.g., Kaplan, 2020; Alban et al., 2020 , Long et al., 2020 . In this paper, we construct and analyze two models to optimize queueing when there is a limit on the number of customers allowed inside a store.

Customers arrive randomly at the store and, after receiving permission to enter, pass through two service phases: shopping and payment. Each customer first spends a random period of time shopping (first phase) and then proceeds to the payment area of the store (second phase) where cashiers are assigned to serve customers. When the store is occupied by the maximum number of allowed customers, newly arriving customers wait outside in line until permitted to enter. In the first model, after completing shopping, the customer proceeds to the payment phase and either is served immediately by a free cashier or waits in a line forming in front of the cashiers. In the second model, we analyze reducing waiting time in the payment queue (and ensuring the safety of cashiers and customers) by allowing store management to set aside a separate waiting space with limited capacity adjacent to the cashiers. For each model, we derive the resulting stability condition and obtain closed form expressions for mean queue sizes and mean waiting times.

To address the issues of controlling and managing queue sizes to ensure the safety of customers and workers while reducing a store's associated costs, we employ a game-theoretic model within the queueing framework to investigate equilibrium strategies in terms of capacity and number of servers. In the game, the authority chooses a maximum number of customers allowed inside the store at a time to minimize the risk of transmission. We propose a novel measure by which to evaluate the risk of infection in this scenario. When L customers are present in the store, each customer can be infected by (the other) L -1 customers. safety problem by developing nonclassical multi-server queueing models involving two service phases, a limit on the number of customers in each phase, and internal blocking and delays. We derive and interpret the corresponding stability conditions. Second, we construct a measure to estimate customers' mean risk of infection. The risk is proportional to the second factorial moment of the number of customers occupying the space in each phase of the shopping route.

Third, within the queueing framework, we formulate a game-theoretic model to investigate equilibrium strategies in terms of capacity and number of servers. Insights from our models are useful to government authorities and businesses as they determine a safe number of customers and employees while containing the associated costs of restrictions to businesses.

In the M-model, customers arrive at a store such as a supermarket or department store according to a Poisson process with rate λ. The number of cashiers in the store is , each with a service 1 c  duration exponentially distributed with mean 1/µ. The authorities have imposed a limit of M ≥ c on the maximum number of customers allowed inside the store at one time. A customer who arrives when there are M customers already in the store must wait outside in a line (an unlimited queue) until permitted to enter. After entering, each customer passes through two "service" phases -shopping and payment. In the first phase, the customer spends a random amount of time exponentially distributed with mean 1/ξ. Upon completing shopping, the customer proceeds to the payment phase and either is served immediately by a free cashier or waits in a line forming in front of the cashiers. Shopping times, payment times, and the arrival process are independent.

This two-phase service process can appear to be a two-site tandem network (see, e.g., Perlman

and Yechiali (2020)), but that is not the case since the two service stages are dependent via the imposed upper limit on the total number of customers allowed inside the store in both phases. In addition, in the current model, the time deterioration considered in Perlman and Yechiali (2020) is replaced by the increased risk of infection associated with customer crowding.

Let L 1 denote the number of customers either in the shopping phase or waiting outside the store. Note that L 1 is unbounded (since we do not restrict the number of customers allowed to wait outside). Let L 2 denote the number of customers in the payment phase who are either being served by a cashier or are waiting in line for a free cashier. The system can be formulated as a two-dimensional quality-by-design process with a state-space of   

customers in the shopping phase. Figure 1 presents a transition-rate diagram of the M-model system. 

where Q is the so-called infinitesimal generator matrix, is a row vector of zeros, and is a 0 e column vector of ones. The generator matrix Q is given by 

where is the element in column n and row k. 

all other elements equal zero; …… and

The matrices A 0 , A 1 , and A 2 are square matrices of order (M + 1) as follows:

Matrix A defines the underlying process of the system, which is depicted in Figure 2 as a linear Markov process with M + 1 states. In fact, the process defined by A can be considered as a machine repair problem in which repairmen maintain machines. The lifetime of 1 c  M c  each machine is exponentially distributed with parameter and the repair time of a machine by a  repairman is exponential with intensity. The state of the system is the number of unbroken μ machines.

Denote by the stationary probability vector satisfying and 0 1 ( , ,..., )

The system stability condition (Neuts, 1981) is , and the system is stable if and

Next, we explore the stability condition stated in Proposition 1 and provide intuition for the results. In particular, the righthand side of the stability condition approaches as μ c  approaches infinity, and the system then becomes Erlang's delay queue: an M(λ) / M( ) / c queue μ with arrival rate λ and c parallel servers who each serve at rate . The stability condition is then μ λ μ.

c  As approaches infinity, the mean total service time for each costumer is so the μ 1 /  system becomes an Erlang's delay queue with parallel servers and the stability condition is M

Similarly, when M approaches infinity, the shopping phase becomes an M(λ) / M( ) /   queue with an output Poisson process (λ). Therefore, the payment phase becomes an 

server (cashier), the right-hand side of the stability condition equals

where is the incomplete Gamma function.

( 1)

As in Neuts (1981), a rate matrix R exists that satisfies

in which the probability vectors satisfy

R is the minimal non-negative solution of equation 3 and is usually calculated numerically via a successive substitution algorithm (see, e.g., Harchol-Balter (2013)). See Hanukov and Yechiali (2020) for cases in which matrix R can be expressed explicitly.

By equations 1 and 2, the balance equations are

The equations 5, 6, and 7 uniquely determine the boundary probability vectors 

Since the risk of infection increases as the number of customers in a store increases, we estimate the risk of infection as proportional to . That is, when L customers are present in the

store, each one can be infected by the other customers. Also, the risk of infection is lower

in more-open areas and could depend on whether social distance can be and is maintained.

Therefore, in this section we calculate the combined risk of infection for customers along their waiting, shopping, and payment routes (phases). Let L 1 SHOP denote the number of shoppers and let L 1 OUT denote the number of customers lining up outside the store with L 1 = L 1 SHOP + L 1 OUT . We start by calculating .

The risk to shoppers of being infected is considered proportional to . The risk

of customers waiting outside the store is proportional to .

, , ,..., , 1, 2,...,1,0 , 0,1,..., ;

2 2 2 2 2 2 2 2 1 , , ,..., ,( 1) ,( 2) ,...,1,0 , 0,1,..., ;

be four sets of column vectors, each of size . Then, 

When the system is stable, the mean rate of arrival rate at the shopping phase is .

λ Similarly, the mean rate of arrival at the payment phase is also . Applying Little's Law, one can λ calculate the mean waiting times:

3. The NM-model: Maximum number of customers at the cashier area and shopping inside the store

We now model a setting in which the store sets aside a separate waiting space near the cashiers for at most N ≥ 0 customers in the payment phase and those customers wait in a single line in the designated area (if necessary) to be admitted by the next free cashier. As in the M-model, the authorities in this model have imposed a limit, M, on the total number of customers allowed inside the store. Thus, in this setting, the store is divided into two separate areas: (i) the payment area with c ≥ 1 parallel cashiers and waiting space of size N customers and (ii) the shopping area, in which the maximum number of customers allowed, K. Thus, the maximum number of customers is the store is . = + + In this model, a customer first spends a random period of time in the shopping phase/area that is exponentially distributed with mean 1/ξ and then proceeds to the payment phase/area.

When there are exactly c + N payers, this customer "orbits" in the shopping area for another exponentially distributed period of time with the same mean 1/ξ (see, e.g., Avrachenkov et al., 2014; Perel and Yechiali, 2014) . Otherwise, when the number of customers in the cashier area is less than c + N, the customer enters the cashier area and becomes a payer. When at least one of the cashiers is not busy, the payer proceeds directly to a cashier and pays. As in the M-model, the payment (service) duration is exponentially distributed with mean 1/µ. All shopping, service, and orbit times are independent of each other and independent of the arrival process.

Let L 1 SHOP denote the number of customers in the shopping area and let L 1 OUT denote the number of customers lining up outside the store. Let L 1 = L 1 SHOP + L 1 OUT . Let L 2 denote the number of customers in the cashier area. Then, the system's state-space is .   1 2 ( , ) ( , ) : 0,1, 2,3,...; 0,1, 2,3,...,

The transition-rate diagram for this system is depicted in Figure 3 . 

Matrix A defines the underlying process of this system and defines a truncated Erlang's model of Poisson arrival with rate , c parallel exponential servers each with rate µ, and an additional K waiting buffer of size N. Figure 4 presents its transition-rate diagram. 

. Corollary 1 specifies the value of

for some special cases. 

As in the M-model, the risk of customers being infected at each area is estimated as , respectively. The

following proposition shows how these measures are calculated. 

(iv) Similar to the proof of Proposition 3. ■ Again, if the system is stable, the mean rate of arrival to the shopping area is . Similarly, λ the mean rate of arrival to the cashier area is also . Applying Little's Law, the mean waiting λ time outside the store is . The mean waiting

time at the shopping area is and the mean waiting time at the payer area is

We next study the effect of the two models' parameters on the performance measures. Let the arrival rate, service rate, and shopping rate, respectively, be customers λ 18, μ 10, and 3     per hour. Set M = 15, N = 5, and c = 2 so that the maximum number of customers in the shopping area is For these values, the right-hand side of the stability condition is 15 5 2 8. cashiers increases the service rate at the payment area. Customers can proceed more rapidly through the payment phase, reducing the amount of time spent waiting in the designated area and reducing the number of customers who must orbit in the shopping area.

The smallest value of N (the number of payers who can occupy the payment space) that sustains the stability condition is 4. When the value of N increases, as depicted in Figure 11b, OUT E W

Several studies have adopted game-theoretic approaches when analyzing safety-related events (see Winkler et al. (2019) for a review). We construct and analyze a COVID-19 queueing game between the authority aiming to reduce the risk of infection while keeping customers and workers safe and a businesses that wants to minimize its costs. Specifically, the authority chooses the maximum number of customers allowed in the store, M. The objective of the authority is (9)   

where denotes the weight the authority assigns to each measure of risk. It is reasonable to α i assume that the authority assigns a smaller weight to queues forming outside a store; therefore, in this case, receives the smallest weighting. Store management cannot exceed the limit set by The store's equilibrium strategy also depends on the values of the weights assigned by the authority to each measure of risk. Set . These weights reflect the

ICU capacity management during the COVID-19 pandemic using a stochastic process simulation

A retrial system with two input streams and two orbit queues

The Covid-19 Crisis and the need for suitable face masks for the general population

Keeping Workers and Customers Safe during COVID-19 in Restaurants

Enabling and enforcing social distancing measures using smart city and its infrastructures: a COVID-19 Use case

Explicit Solutions for Continuous-Time QBD Processes by Using Relations Between Matrix Geometric Analysis and the Probability Generating Functions Method

Performance modeling and design of computer systems: queueing theory in action

OM Forum-COVID-19 Scratch Models to Support Local Decisions

Pooling and Balking: Decisions on COVID-19

Available at SSRN 3628484

The Israeli queue with retrials

On tandem stochastic networks with time-deteriorating product quality

Reporting near-miss safety events: Impacts and decision-making analysis

In this paper, we construct and analyze two special nonclassical multi-server queueing models to control queueing problems generated by social distancing constraints associated with the COVID-19 pandemic such as "Maximum shoppers at store" and "maximum number of customers in checkout area." In both models, a capacity constraint is imposed that limits the number of customers allowed inside the store at one time. The governing authority that imposes the limit acts as a Stackelberg leader in choosing how many customers will be allowed. Then, store management chooses the number of cashiers to employ to reduce its costs in terms of cashier salaries and the cost of dissatisfaction from customers waiting in line. In the second model, store management can also choose a maximum number of customers who can occupy a separate payment area in a queue formed in front of the cashiers. For each model, we derive and analyze the equilibrium strategies in terms of the store's customer capacity and the number of cashiers.Our findings are useful and applicable for both government authorities establishing restrictions