Arrival Process

Arrival Process in Simulation and Queueing Models of Health Services

In a discrete event simulation or queuing model of a health service, the arrival process decides when each new patient, referral or donor organ appears and how much those appearances bunch together. Two services with the same average daily demand can have very different queues and costs if one receives patients steadily and the other in peaks. How arrivals are specified therefore feeds through to capacity, waiting and cost, a link drawn in the ISPOR-SMDM good practice report on discrete event simulation. In an illustrative example, a daytime peak raises the expected cost of overflow cover by about 80%.

Counts, arrival times and gaps as views of one stream

An arrival process can be described by the running count of patients, by the clock time of each arrival, or by the gaps between arrivals, and the three carry the same information. Data often come as counts per hour, whereas a simulation is usually driven by sampling the gaps.

$$S_n = X_1 + X_2 + \dots + X_n, \qquad N(t) = \max\{ n : S_n \le t \}$$

where $S_n$ is the time of the $n$th arrival measured from the start of the observation period, $X_i$ is the inter-arrival time between arrival $i-1$ and arrival $i$ (with $S_0 = 0$), and $N(t)$ is the number of arrivals in the interval from 0 to $t$.

When the gaps $X_1, X_2, \dots$ are independent and identically distributed, the process is a renewal process. Gallager's text on stochastic processes defines it in these terms and treats the Poisson process as the special renewal process whose gaps are exponential.

The Poisson process and its exponential gaps

The homogeneous Poisson process is the usual starting point because it matches a simple picture of many potential patients, each acting independently, each with a small chance of arriving in any short interval. The number of arrivals in a window of length $t$ follows a Poisson distribution and the gaps follow an exponential distribution.

$$P\{N(t) = n\} = \frac{(\lambda t)^n e^{-\lambda t}}{n!}, \qquad f_X(x) = \lambda e^{-\lambda x}, \quad x \ge 0$$

where $\lambda$ is the arrival rate (expected arrivals per unit of time), $t$ is the length of the window, $n$ is a whole number of arrivals, and $f_X(x)$ is the probability density of a gap of length $x$. The expected number of arrivals in the window is $\lambda t$ and the mean gap is the reciprocal of $\lambda$.

Three properties make the Poisson process convenient in health economic models. The exponential gap is memoryless, so the waiting time until the next arrival does not depend on how long it has been since the last one. Independent Poisson streams merge into a Poisson stream whose rate is the sum of their rates, so referrals from several general practices can be pooled into one input. Splitting a Poisson stream at random, for example routing each arriving patient to a fast track with a fixed probability, gives independent Poisson streams.

Time-varying demand and the non-homogeneous Poisson process

Kim and Whitt observe that service systems such as hospitals typically have strongly time-varying arrivals. It follows that a single constant rate will often fit a whole day of emergency attendances or admissions poorly. The non-homogeneous Poisson process keeps the independence of arrivals in separate intervals but lets the rate vary with time. Counts in any interval are still Poisson, with a mean equal to the area under the rate curve.

$$m(a, b) = \int_a^b \lambda(u)\, du, \qquad P\{N(a, b) = n\} = \frac{m(a, b)^n e^{-m(a, b)}}{n!}$$

where $\lambda(u)$ is the arrival rate at time $u$, $m(a, b)$ is the expected number of arrivals between times $a$ and $b$, and $N(a, b)$ is the number of arrivals in that interval. Lewis and Shedler note that, unlike the homogeneous case, the gaps in a non-homogeneous Poisson process are neither independent nor identically distributed. For that reason, fitting a single gap distribution to data pooled across busy and quiet periods is not appropriate.

Kim and Whitt applied Kolmogorov-Smirnov tests to hospital emergency department and banking call centre arrival data and found them consistent with a non-homogeneous Poisson process only when the data were analysed carefully. Their initial tests rejected the model because of three features of the data, namely timestamps rounded to the second, subintervals over which the rate varied too much, and overdispersion created by pooling the same hour across weeks with different arrival rates.

Generating arrival times inside a discrete event simulation

The ISPOR-SMDM report on discrete event simulation, by Karnon and colleagues, notes that entities can be created at the start of a run or whenever the problem requires, for example when a new patient arrives at a clinic or develops a disease, and can enter and leave between the start and end of the model. In a typical implementation each arrival is placed on the event queue; when it is processed, the simulation creates the patient and schedules the next arrival.

For a homogeneous Poisson process the next gap is sampled by inverting the exponential distribution function.

$$X = -\frac{\ln U}{\lambda}$$

where $X$ is the sampled gap, $U$ is a random number drawn uniformly between 0 and 1, and $\lambda$ is the arrival rate. With $\lambda = 3$ patients per hour and $U = 0.5$, the gap is $\ln 2 / 3 = 0.231$ hours, or about 13.9 minutes.

For a time-varying rate, the thinning method of Lewis and Shedler avoids integrating the rate function. Candidate arrivals are generated from a Poisson process with a constant rate $\lambda^*$ that is at least as high as $\lambda(t)$ throughout the period, and a candidate at time $t$ is kept with probability $\lambda(t)/\lambda^*$. The kept points form a non-homogeneous Poisson process with rate $\lambda(t)$.

Not every arrival stream is random in this way. Booked outpatient appointments and elective operating lists produce arrivals close to the booked times, so they are better generated from the booking pattern than from a Poisson process. Patients who do not attend are then removed, and lateness or early arrival is added as a random deviation from the booked time.

Open and closed cohorts

The arrival process only matters when patients enter at different times. A closed cohort creates every patient at time zero and follows the same group to the end of the time horizon, as a cohort model does; an open cohort keeps admitting new patients throughout the run.

Many health technology assessment models built as individual patient simulations are what the ISPOR-SMDM report calls non-constrained. They follow the usual structural assumption that every required resource is available as needed, with no capacity limits. Patients in such a model do not compete, so, provided nothing depends on calendar time, a closed sample created at time zero gives the same mean costs and QALYs per patient as staggered entry, and the arrival process can be left out of the per-patient results. Population totals, such as those in a budget impact analysis, still need the stream of new patients over time, whether from an arrival process or an incidence rate. In constrained-resource models patients compete for clinic slots, beds or donor organs, and the timing of arrivals determines how long the queue becomes.

For an open model of an existing service, the report recommends a warm-up period that builds the system up from empty when the key parameters can be assumed constant over time or their history can be built in, and otherwise accepts preloading entities with ready-made histories.

How arrivals drive capacity, waiting and cost in economic evaluation

In a constrained-resource model the arrival process is the demand side of the comparison with capacity. The ISPOR-SMDM report lists flow times, wait times, throughput and resource utilisation as common outcomes of such models, and recommends that constrained resources be modelled when levels of access are altered, for example when increased referral rates lead to longer waits for a procedure, and when the time to access has significant effects on costs or outcomes. It also recommends that these models report effects on health-related outcomes and not only on resource use and system capacity.

A standard queueing result shows why the arrival rate feeds through so strongly. For a single server with Poisson arrivals and exponential service, in steady state and with $\lambda < \mu$, the expected time waiting before service is as follows.

$$W_q = \frac{\rho}{\mu - \lambda}, \qquad \rho = \frac{\lambda}{\mu}$$

where $W_q$ is the expected wait before service starts, $\mu$ is the service rate, $\lambda$ is the arrival rate and $\rho$ is the capacity utilisation of the server. As $\rho$ approaches 1 the expected wait grows without limit, so a small rise in arrivals near full utilisation produces a large rise in waiting time and in any cost or health loss tied to it. Services with several servers, such as a ward of beds or a bank of cubicles, show the same steep rise in delay as utilisation approaches full capacity.

Worked example of a daytime peak at an assessment unit

The figures below are illustrative. An acute assessment unit expects 48 patients a day and its staff can absorb up to 4 arrivals in an hour; in any hour with more, an on-call clinician is called in at £150. Each hour is treated separately and backlog between hours is ignored, which a full simulation would capture.

1. Model A, constant rate. Spreading 48 patients evenly over 24 hours gives $\lambda = 2$ per hour. The probability of 4 or fewer arrivals in an hour is the following Poisson sum.

$$P\{N \le 4\} = e^{-2}\left(1 + 2 + 2 + 1.333 + 0.667\right) = 0.1353 \times 7 = 0.947$$

where $N$ is the number of arrivals in one hour and the five terms in brackets are $\lambda^n/n!$ with $\lambda = 2$ and $n$ running from 0 to 4. The probability of overflow in any hour is therefore 0.053, and the expected number of overflow hours per day is 24 × 0.0527 = 1.26.

2. Model B, daytime peak. The same 48 patients arrive at 3 per hour from 08:00 to 20:00 and 1 per hour overnight, so $m = 3 \times 12 + 1 \times 12 = 48$ and the daily mean is unchanged. For a daytime hour the probability is as follows.

$$P\{N \le 4\} = e^{-3}\left(1 + 3 + 4.5 + 4.5 + 3.375\right) = 0.04979 \times 16.375 = 0.815$$

where the bracketed terms are $\lambda^n/n!$ with $\lambda = 3$. For a night-time hour, with $\lambda = 1$, it is as follows.

$$P\{N \le 4\} = e^{-1}\left(1 + 1 + 0.5 + 0.1667 + 0.0417\right) = 0.3679 \times 2.708 = 0.996$$

where the bracketed terms are $\lambda^n/n!$ with $\lambda = 1$. The overflow probabilities are 0.185 by day and 0.004 by night, so the expected overflow hours per day are 12 × 0.1847 = 2.22 by day plus 12 × 0.0037 = 0.04 overnight, a total of 2.26.

3. Cost consequences. At £150 per overflow hour, the expected daily cost is 1.26 × 150 = £189 under Model A and 2.26 × 150 = £339 under Model B. Over a year that is 189 × 365 = £68,985 against 339 × 365 = £123,735.

4. Interpretation. Both models have the same expected demand, yet the time-varying model expects about 80% more overflow hours and cost. A model using the daily average would understate the cost of the current service and could misjudge an intervention that mainly removes daytime arrivals. Adding backlog carried between hours would be expected to widen the gap, because queues build up during the peak.

Estimating and checking an arrival process

Arrival rates are usually estimated from routinely collected timestamps, such as referral dates or emergency department registration times, as arrivals divided by observed time for each hour or day of week, subject to the data problems reported by Kim and Whitt. Recorded activity is not always demand. Admissions or appointments already limited by capacity record what the service could absorb, so using them as arrivals understates pressure. In disease models, arrivals may instead come from an incidence rate applied to a population at risk, which also supports demand forecasting.

A single run of an open model gives a noisy result. The ISPOR-SMDM report notes that where the number of entities is sampled, such as patients presenting at a clinic, and the time horizon is fixed, multiple replications with the same inputs can be run to reduce variability, and it recommends testing output stability across random number seeds. This keeps Monte Carlo error separate from genuine uncertainty about the arrival rate itself.

Where arrival processes are misread

A common error is to use a single average rate for a service whose demand peaks, which, as the worked example shows, understates congestion and the cost of cover. Fitting one gap distribution to pooled data from such a service is a variant of the same error.

A second group of errors concerns independence. A Poisson process assumes that one arrival does not trigger another, which fails when one incident brings several casualties, and that arrivals do not respond to the state of the service, which fails when patients leave long queues. Counts that vary more than a Poisson model allows are a sign that one of these assumptions has broken down.

A third error is to hold the arrival process fixed across strategies that change it. A screening programme or new referral criteria alter who arrives and when. The departure process is the counterpart on the way out; in a constrained model it depends on arrivals, service times and capacity, so it cannot be specified independently of them.

Sources

• Gallager RG. Discrete Stochastic Processes, course text for MIT 6.262, chapter 2 (Poisson processes) and chapter 6 (Markov processes with countable state spaces). MIT OpenCourseWare; 2011. https://ocw.mit.edu/courses/6-262-discrete-stochastic-processes-spring-2011/
• Karnon J, Stahl J, Brennan A, Caro JJ, Mar J, Möller J. Modeling using discrete event simulation: a report of the ISPOR-SMDM Modeling Good Research Practices Task Force-4. Value in Health. 2012;15(6):821-827. https://doi.org/10.1016/j.jval.2012.04.013
• Kim SH, Whitt W. Are call center and hospital arrivals well modeled by nonhomogeneous Poisson processes? Manufacturing and Service Operations Management. 2014;16(3):464-480. https://doi.org/10.1287/msom.2014.0490
• Lewis PAW, Shedler GS. Simulation of nonhomogeneous Poisson processes by thinning. Naval Research Logistics Quarterly. 1979;26(3):403-413. https://doi.org/10.1002/nav.3800260304