Scheduling Algorithms, or Looking At the Back of a Bus

Efficient public transportation is a thing of beauty. Normal public transportation is a pain in the caboose. I was reminded of this last week in London when attending the Symbian Smartphone Show. Step off one Underground train, step onto another. From Gatwick to the Docklands, I'm here to tell you that I flogged that day pass. But then back in the U.S. and catching a bus from the airport terminal to longterm parking, I watched three empty buses go by with nary a glance. So you wonder: If London can precisely schedule hundreds of trains, what's so hard about an airport scheduling a handful of buses?

This is exactly the kind problem that Jiamin Zhao, Maged Dessouky, and Satish Bukkapatnam tackled in their paper Optimal Slack Time for Schedule-Based Transit Operations which recently won a "Best Paper for 2007" award from the Institute For Operations Research and Management Science Transportation Science and Logistics Society.

The question they addressed was: How much "slack time" should be schedulers of a bus or tram line add to keep operations from bunching up? (Slack time is extra time built into a bus schedule to accommodate unexpected delays.) In the paper, the authors note that "if slack time is insufficient, buses are unlikely to be able to catch up with the schedule when they fall behind, deteriorating reliability. But too much slack time reduces service frequency, which may inconvenience passengers."

For the simplest case, a single vehicle traveling in a loop, their algorithm gives an exact number, based on the size of the loop and the distribution of the of the travel time delay. The analysis also provides a way to approximate the effect of adding more busses to the loop.

The effects that the equations model involve human behavior that is easy to describe, but hard to quantify. For example, if trains or buses are spaced close together (less than 10 minutes apart, typically), travelers tend not to consult schedules or expect vehicles to arrive exactly on time, and buses can leave early without upsetting travel plans. If buses are an hour apart, this isn't true.

And delays tend to be cumulative. "Buses on frequent lines have a tendency to bunch…when a bus falls slightly behind schedule it tends to pick up more passengers, causing it to slow further" -- which is exactly what I had to put up with at the airport.

The author's research is based on studies that Dessouky did in analyzing bus operations at the Los Angeles Metropolitan Transit District. At the time Dessouky, who with Zhao and Bukkapatnam were members of the University of Southern California Viberti School of Engineering, measured an average slack time ratio of 0.25 on three MTA lines; a bus trip scheduled to take an hour generally was accomplished in 45 minutes, with the extra 15 minutes in the schedule built in to accommodate possible delays.

But was the 15 minutes more than necessary? Dessouky later worked with the MTA to incorporate these delay measurements into more effective scheduling, while continuing to try to build the dynamics he found into equations to find out what the optimal level might be.

Dessouky et al. use the equations to create curves to correlate average levels of delay and slack time ratios and, by further transpositions, with resulting waiting time for passengers, leading to an approximation of how much slack time is optimal, depending on total round trip travel time. The bottom line? Build in between 15 and 20 percent slack, more for longer trips.

-- Jonathan Erickson
jerickson@ddj.com

Posted by Jon Erickson at 10:02 AM  Permalink