Optimize This: Introducing Uncertainty

Note: This is part 3 in a series of posts about mathematical modelling of public transit systems. If you haven’t already, I suggest you take a look at the first post where I try to motivate the need for, and validity of mathematical models in public transit. You might also be interested in the second post, where I discuss finding trade-offs in public transit in order to provide mathematical optimization.

Another Note: This post uses both calculus and statistics. Again, I will explain results so that calculus and formal statistics are not required to appreciate the article.

TL;DR: Public transit, especially bus routes, is inherently random. To combat the uncertainty, a strategy is used to hold buses at certain points and build extra time into the schedule. Because this lengthens the overall travel time, a trade-off exists between adding extra slack time and keeping the route time short. This provides room for optimization.

Uncertainty is Certain

Anyone who has ever ridden public transit, especially the bus, can appreciate that transit is inherently unpredictable. On a typical bus route you can find a whole grab-bag of factors that impede a bus from running on time, including (but not limited to) traffic congestion, fluctuations in passenger volumes, making more or fewer stops, and weather. Next time you ride a bus, spend 5 minutes trying to find all the little things that made the bus move faster or slower than it had before. My guess is you will lose count before you reach the end of the block. Now multiply those 5 minutes by an entire bus route’s length, and it’s amazing buses ever run close to their intended schedule.

If uncertainty and randomness play such a big part in a public transit system, it’s probably a good idea to incorporate it into our models when we develop them, and potentially come up with some strategies to reduce some of the uncertainty. One of the most common ways to do this is to introduce special stops along the route called time points. Typically, these time points have published, scheduled departure times, and the stops in between these points just provide some guess of a likely “in-between-time” that the bus will arrive. At these time points, we can build in some slack time, so that the bus is more likely (though not certain) to be ready to leave at or before its scheduled departure time. If the bus is early, it waits until this departure time. This is known as a holding control strategy.

Great! So now we have a way to fight some of that randomness. Here’s the trade-off: the more slack time you add to these time points, the more predictable the bus’ departure will be, but the longer the overall route’s time will be. For someone boarding or alighting at a time point, this doesn’t matter, but for someone riding through a time point, this extra time (in their view) is a complete waste. Now that we have a trade-off, we might be able to optimize. Before diving into math though, it might be nice to have an opinionated discussion.

A Well-Known Problem

Despite the fairly large amount of research done on the subject, there is no real evidence that public transit systems use any of the optimal strategies in their plans1. While the holding control strategy is commonplace, it appears to have been developed in specific cases through a trial-and-error process with no science to back up the decisions. Since this is a blog post and not an academic paper I can speculate wildly that this is in part due to the fact that many transit planners are promoted from within a transit agency, and experience is valued over science and logic. As a result many of the concepts that involve high-level mathematics and abstract concepts are difficult to explain to transit agencies (and, to be fair, are often poorly explained anyway). This is unfortunate, since it requires such a long time to see the effects of changes in a bus route, and that even an educated guess can still be wrong. It would seem sensible to at least attempt to model the changes (even crudely) before applying them to real transit routes.

Considering the trade-off described above, we might be able to draw an intuitive conclusion about where time points should be located. All other factors aside, it would seem that locating time points at stops with very high boarding and alighting rates would be best, for a couple of reasons: First, there will be relatively few passengers travelling through the stop; alighting passengers are not affected by the wait the bus may incur due to arriving early at the time point. Secondly, since a time point increases a bus’ chance of departing on time, boarding passengers at this time point experience a more reliable bus. This experience is compounded by the large amount of boarding passengers who are positively affected by it. It is also practical: places with large boarding and alighting rates (campuses, malls, and central business districts are a few examples) are often a good place for transfers (they attract passengers from all around the city), and have the infrastructure built to accommodate buses as they wait for their scheduled departure time. Practical meets logical.

The research on this is not entirely clear, which is why there’s room for a thesis here (wink wink). It appears to be clear that passenger demand (boarding and alighting) profiles influence where a good time point is2; we can see that from the argument above, and there is some decent consensus on how much slack time to allocate (we’ll talk about that next), but nobody has really put it all together to find the best configuration of these time points on a given route.

Give It Some Slack!

We’re now going to move into a more “mathy” example for optimization. If you decide to stop reading here, I won’t hold it against you. Thanks for reading, and I’d love to hear your thoughts on the above! For those who are with me to the bitter end, let’s have a go!

We’re going to consider a special case3 of a bus route with one link (no stops in between), where passengers are loaded at one end and brought straight to their destination. We are assuming that the bus’ travel time along this link assumes some sort of random variable T, and follows some probability distribution f(t). We will define the scheduled travel time as the mean (average) of the bus’ travel time plus the slack time that we have decided on for the route. We want to find some way to optimize this scheduled travel time (of which we can control only the slack time) according to some objective function. There is no advantage to be gained by running an early  vehicle, since people don’t generally plan for it. This means that the expected actual travel time E[A] should be larger than the scheduled time S.

$\displaystyle E[A] = S + \int_s^\infty (t-S)f(t) dt$

More importantly, the expected delay can be written as

$E[\delta(S)] = E[A] - S$

From this we can see that if we make the scheduled time S as small as possible (usually a minimum possible travel time) the delays grow. On the other hand, if we make the scheduled time as large as possible, the delays get very small, but the total travel time gets very large. There’s the mathematical representation of our trade-off. Now we’ll look at costs. Evidently, passengers prefer not to be delayed, so there should be two different time costs for passengers. We denote budgeted travel time as γ’, and delayed travel time as γ, understanding that generally γ’>γ. The expected cost for travel time is therefore

$\gamma' S + \gamma E[\delta(S)]$

There are other potential costs we can consider. Perhaps this bus is a feeder bus that services a commuter train, and there is a penalty of missing a train if the bus is late. In that case, it doesn’t matter how late the bus is, there is just a fixed penalty γp. The expected penalty is obtained by multiplying this penalty by the probability the bus is late, P(T>S) which is just 1 minus the probability the bus is on time F(S) The total expected cost is combined to show

$E[Z(S)] = \gamma' S + \gamma E[\delta(S)] + \gamma_p[1-F(S)]$

Where F(T) is the cumulative probability distribution of T. This expected total cost can be minimized so that

$F(S) - (\gamma_p/\gamma)f(S) + \gamma'/\gamma = 1$

Essentially, from this, we can choose a “target reliability” and schedule the bus optimally according to this formula, or we can find values for these costs and schedule accordingly, with an implied reliability. We can also adjust γp and γ’ for various scenarios such as feeder buses (large fixed penalty, no time delay penalty), recreational trips (no fixed penalty, some time delay penalty), or various positive and negative versions of these costs. Some excellent numerical examples are given in the paper I cited above.

The take-away message is this: uncertainty is a crucial part of any transit system. It should be embraced as part of the challenge of transit operations, and can be relatively easily incorporated into mathematical models.

So, the next time your bus is late, you’ll have to decide: Is it worth getting to my destination faster?

References

1. Wirasinghe, S. C., & Liu, G. (1995). Optimal schedule design for a transit route with one intermediate time point. Transportation Planning and Technology, 19(2), 121–145.
2. Abkowitz, M. D., & Engelstein, I. (1986). Optimal Control of Headway Variation on Transit Routes. Journal of Advanced Transportation, 20(1), 73–88.
3. Wirasinghe, S. C. (1993). Cost Based Approach to Scheduling Travel Time on a Public Transportation Route. International Symposium on Transportation and Traffic Theory.