7.1.4 Simulating Event Times from a Time-Dependent Poisson Process



Suppose that, as in Section 4.11, we have demands for an urban service which are generated in a Poisson manner but with an average rate, , which is a function of time. This is a most common case for urban service systems. We would, therefore, like to be able to simulate this type of demand accurately and efficiently for any given time interval [0, T]. In the following it will be assumed that the average demand rate is known for all t (0 ‹/= t ‹/= T). A typical pattern for is shown in Figure 7.12.

The most obvious approach is to use (7.5), substituting for We begin at time t = 0 and generate the first demand using for in (7.5). Assume that the first demand occurs at time t1. We then use (7.5) with to generate the time for the second demand, t2. We proceed in the same way, using, ... successively in (7.5) until eventually a demand's time of occurrence falls outside the interval T, at which point we can stop.

On second thought, however, this procedure turns out to be faulty. To see why, consider the case when a demand is simulated to occur at time t*, as shown in Figure 7.12. To generate the next demand we would then use= with (7.5). But because is small, the simulated interval until the next demand will tend to be a long one (its expected value is and thus we may "skip" (without generating any new demands) a good part of the period of time that follows t*, when there is an increase (a "hump") in demand. In the extreme case when is close to 0, we may in fact "jump" all the way to the end of the interval T.


The following four-step procedure overcomes these problems:
STEP 1: Estimate the mean arrival rate throughout the interval T,


STEP 2: Using a constant rate with (7.5), generate a sample value of N(T), say k, the number of Poisson events in T, in a manner identical to that of Example 5 (and Figure 7.9). Note that k is distributed as


STEP 3: Use the rejection method and the function with c= (Figure 7.12), a = 0, and b = T to generate exactly k unordered time instants in [0, T]. These are the instants when demands occur (cf. "unordered arrival times" for a Poisson process, Section 2.12). Note that can be greater or less than.
STEP 4: Rearrange (sort) the time instants into an ordered set{t1,t2,...,tk} where t1 is equal to Min t2 is equal to the second smallest of and so on. The instants {t1,t2,...,tk} are the simulated time instants for the occurrence of demands according to the time-dependent Poisson process with average rate
Exercise 7.3 Argue why the four-step procedure outlined above works correctly. What does each one of the four steps of the procedure accomplish?

The procedure presented above is somewhat inefficient because it makes two passes over T: once to generate k and a second time to generate the time instants, A single-pass procedure is developed in Problem 7.3. We also note that an efficient sorting algorithm that can be useful for Step 4 is described in Section 7.2.1.