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.

Advertisements

Decisions, decisions, decisions…

Posted in Statistics, Transportation by Alexander Lobkovsky Meitiv on February 25, 2010

This entry is about how the amount of information at the time of a decision can increase the efficacy of the outcome.

The specific case I will talk about is public transport.

Have you ever been on a bus that sat at a red light only to stop again at a bus stop right after passing the intersection?
Did you wonder if it would be better to have the bus stop located before the light?

Wonder no more! If you read on, we will answer this question and a few others using simple statistics and a few carefully chosen assumptions.

Let us first compute the average waiting time at a red light. Let’s say the light has only two states: red and green which alternate. The durations of the red and green lights are fixed and are t_r and t_g. Suppose that the bus arrives at a light at a random time. Then its average waiting time at the red light is

\displaystyle t_\ell=\frac{1}{t_r+t_g}\int_0^{t_r}t\,dt=\frac{t_r^2}{2(t_r+t_g)}.

This is because we assume that the bus arrives at the light at a random time. Without any prior information, the distribution of arrival times is uniform. The behavior of the light is periodic with period t_r+t_g and thus the probability of arriving in any time interval dt is dt/(t_r+t_g).

For example, if the red and the green lights are equally long, i.e. t_g=t_r, the average wait at a stop light will be a quarter of the red light duration t_\ell = t_r/4. (To derive that substitute t_g=t_r into the equation above).

Now lets add the bus stop to the equation. We will assume that the bus stops for a fixed time t_s. Fluctuations in the stopping time can be added to the model. However, calculations become a bit more involved and the result does not change qualitatively.

The questions are: 1) What is the total stoppage time t_w: red light + bus stop? 2) Does it depend on whether the bus stop is before or after the red light?

If we know anything about information theory, our answer to the second question is NO without doing any algebra. Why? Because the bus arrival time is random and uncorrelated with the timing of the stop light. There is no information that can distinguish stopping before and after the intersection. If the stop is after the light, the bus has the wait at the red light for a time t_{\ell} just computed above. If the bus stops before the light, the “arrival” time is the time at the end of the stop and it is just as random as the arrival to the stop. Therefore, the average total stoppage time is just t_\ell + t_s regardless of whether the stop is before or after the light.

How can the total stoppage time be reduced?

After all this post is about efficiency of mass transit. The answer, again from the point of view of information theory, is the following. To improve efficiency, we must use available information to make decisions which make the arrival (or departure) time of the bus correlated with the timing of the light.

In Switzerland, public support for mass transit is so strong, that people accept that the trolleys actually change the timing of the stop lights to speed up passage at the expense of cars. Here in America this approach may not fly. However, even if the timing of the stop light cannot be changed by the bus/trolley driver, they still have the power to make decisions that would change the total stoppage time.

In the example above, the bus stop was always before or after the intersection. Suppose the driver could decide, based on some information about the phase of the stop light, whether to stop before or after the intersection?

Let’s call the scenario in which the bus driver does not make a decision where to stop the “null model” or the “no-decision” model. As a better alternative consider the “red-before” scenario in which the driver stops before the intersection if the bus arrives on the red light and after the intersection if the bus arrives on the green light. What is the average stopping time t_w = t_s + \Delta?

I am not going to bore you with the tedious derivation. The result itself is a bit complicated as we have to consider 4 separate cases. I am going to give a formula for the extra waiting time \Delta on top of the regular stop duration t_s.

Let’s first define:

\displaystyle I_1=\frac{(t_r-t_s)^2}{2(t_r+t_g)},

and

\displaystyle I_2=\frac{(t_s-t_g)(t_r-\frac{1}{2}(t_s-t_g))}{t_r+t_g}.

Then the extra waiting time is

\Delta=0 for t_r \le t_s \le t_g
\Delta=I_1 for 0\le t_s \le \min(t_r,t_g)
\Delta=I_2 for \max(t_r,t_g)\le t_s \le t_r+t_g
\Delta=I_1 + I_2 for t_g \le t_s \le t_r

If t_s \ge t_r + t_g, just replace t_s everywhere with its remainder when divided by t_r + t_g.

To illustrate these formulas here is the graphs comparing the extra stoppage time \Delta for the “no-decision” and the “red-before” scenarios as a function of the stop duration t_s for two different ratios of the red to green light durations.

Extra waiting time for t_r = 2 t_g

Comparison of the extra waiting time as a function of the bus stop duration for two different decision scenarios and the red light twice as long as the green light.

Extra waiting time for t_g = 2 t_r

Comparison of the extra waiting time for the green light twice as long as the gred light. Note that for a certain range of bust stop durations, the extra waiting time vanishes completely!

The “red-before” scenario which uses only the information about the current state of the stop light does quite well compared to the “no-decision” scenario. When the green light is longer than the red light, the extra waiting time vanishes altogether if the stop duration is chosen properly.

Can we do better?

Yes! The more information is available to the driver, the better can the strategy be for making the decision where to stop. We can imagine, for example, that when the bus arrives at a red light, the driver knows when it will turn green again. Or, the driver can have complete information and also know the duration of the following green light.

Let us compute the extra waiting time for the best stopping strategy with complete information. How much better does it do than the “red-before” strategy which uses only the information about the current state of the stop light? The best stopping strategy which uses all available information is the following. Suppose the bus arrives on a red light. The time till the light change is the extra waiting time if the driver decides to stop after the intersection. This time needs to be compared to the extra waiting time which might result if the bus stops before the intersection. This might happen if the total stop duration is longer than the remainder of the red light plus the following green light so that the light is red again after the bus stop is completed. The best decision will depending on when the bus arrives, the duration of the red and green lights and the the bus stop.

I am going to leave you with a comparison of the extra waiting time for the”red-before” strategy with the best stopping strategy with perfect information about the phase of the stop light (length of red, green, time till change).

The moral of the story: “Information is power!”

Extra waiting time for the

The perfect information helps reduce the extra waiting time when the red light is longer than the green and when the bus stop duration is longer than the that of the green light.