Playing with models: quantitative exploration of life.

The waiting game.

Posted in Game theory, Transportation by Alexander Lobkovsky Meitiv on December 20, 2010
People waiting at a bus stop.

When two buses can take you where you need to go should you let the slow bus pass and wait for the fast bus?

The Metro has changed the bus schedule this morning with no prior notice whatsoever. The 9 am J1 bus, I usually take, did not come. As I found out later, it was dropped from the schedule altogether. For about 20 minutes I was assuming (with diminishing conviction) that the J1 was merely late. While waiting for the J1, I let two J2’s go by. The J2’s take about 15 minutes longer to reach my destination. While I was waiting, I began to wonder what the best waiting strategy would be if there were two modes of transport with different travel times and different service frequencies. There is a math problem in there with a clear cut answer.

It is simpler to consider the situation in which buses do not have a fixed schedule but arrive at a fixed rate per unit time \mu. Intervals between consecutive buses in this situation obey Poisson statistics, which means that no matter when I arrive at the stop the average waiting time before the bus arrives is 1/\mu.

In what follows I will present a few results without much derivation. If you are interested in the nitty-gritty, contact me for details.

Suppose there are two buses A and B that arrive at a stop with rates \mu_A and \mu_B. The probability that A arrives before B is

P(A\mathrm{\ before \ } B) = \displaystyle{\frac{\mu_A}{\mu_A + \mu_B}}.

The mean waiting time for bus A provided that A has arrived first is

t_A =\displaystyle{\frac{\mu_A}{(\mu_A + \mu_B)^2}}.

Now if the travel times to destination on buses A and B are \tau_A \geq \tau_B, we can compute the expected travel time if the traveler boards the first bus that comes to the stop. We will call it T_0 because the strategy is to let zero buses pass (even if they take longer).

T_0 = \displaystyle{\frac{\mu_A \tau_A}{\mu_A + \mu_B} + \frac{\mu_A}{(\mu_A + \mu_B)^2} + \frac{\mu_B \tau_B}{\mu_A + \mu_B)} + \frac{\mu_B}{(\mu_A + \mu_B)^2} = \frac{1 + \mu_A \tau_A + \mu_B \tau_B}{\mu_A + \mu_B}}.

We can interpret this formula as follows. The total bus arrival rate is \mu_A + \mu_B and therefore the mean waiting time for a bus, any bus is 1/(\mu_A + \mu_B). Then with probability \mu_A/(\mu_A + \mu_B) the A bus has arrived and the travel time is \tau_A. Likewise, with probability \mu_B/(\mu_A + \mu_B) the B bus arrives so that the travel time is \tau_B.

It is a only marginally trickier to derive the mean trip duration (will call it T_1) when we are willing to let one A bus pass by in the hopes that the next bus will be the faster B bus. The answer is

T_1 = \displaystyle{\frac{1}{\mu_A + \mu_B} + \frac{\mu_A T_0}{\mu_A + \mu_B} + \frac{\mu_B \tau_B}{\mu_A + \mu_B}}.

The explanation of the second term in the above formula is that if A arrives first, we let it pass and we are back to the “let zero buses pass” strategy. The rest of the terms in the equation for T_1 are the same as before.

In general, for any n \geq 1 we have a recursion relation:

T_{n+1} = \displaystyle{\frac{1}{\mu_A + \mu_B} + \frac{\mu_A T_n}{\mu_A + \mu_B} + \frac{\mu_B \tau_B}{\mu_A + \mu_B}}.

We can now start asking questions like: “Under what conditions does letting the slow bus pass make sense (i.e. results in a shorter expected trip)?” What about letting two buses pass? When does that strategy pay off?

When does T_1 \leq T_0? Comparing the formulas above we arrive at a simple condition on the arrival rate of the fast bus which is independent of the arrival rate of the slow bus

\displaystyle{\mu_B \geq \frac{1}{\tau_A - \tau_B}} \quad \mathrm{(1)}.

For example, if the slow bus takes 30 minutes and the fast bus takes 20 minutes to arrive at the destination, it makes sense to let the slow bus pass if the fast bus arrives more frequently than once in 10 minutes. No big surprise there, anybody with a modicum of common sense could tell you that.

What is surprising is that the condition (1) does not depend on the arrival rate of the slow bus. Did I make a mistake? It turns out that when T_1 = T_0, the expected travel times for other strategies are exactly the same! I will leave the proof to my esteemed reader as homework :)

Therefore, since it does not matter how frequently the slow bus comes, if the fast bus comes frequently enough (condition (1) is satisfied), it makes sense to wait for the fast bus no matter how many slow buses pass.