New post at the INFORMS site: “Avoiding Bunches of Buses”:
While the INFORMS conference is big enough to stay within a narrow research area, it is also a great place to get inspiration outside your focus. I hopped in to see a talk given by Don Eisenstein on work he has done with John Bartholdi on “scheduling” buses. Don and I were in graduate school together, and we each had John as our advisor, but we work in completely different areas.
Don talked about a system they have put in place to handle buses, trollies, and other transportation systems that have multiple vehicles going over the same routes. I am sure we have all had the frustration of waiting a long time for a bus, only to have three buses (all running the same route) appear in quick succession. This phenomenon is common enough to form the title for a popular mathematics book. Upon reflection, this situation is not mysterious. If buses are scheduled on a route at, say, 10 minute intervals, then any delay in one bus (a slow entering customer, a traffic jam, and so on), will cause that bus to run even later. Once delayed by two minutes, more passengers will arrive in the now-12 minute gap, further slowing down the bus. Meanwhile, the bus following the delayed bus will go faster than normal due to a dearth of passengers for it. Very quickly, a small increase in the gap will turn into a large gap ahead of the delayed bus and a small gap behind it.
This bunching behavior is very common, and very difficult to schedule around. In fact, as buses try to keep to the schedule, drivers may resort to dangerous or illegal driving, particularly if drivers are evaluated by their ability to keep to a schedule. This situation is made worse if a bus suffers a mechanical failure, leading to a large gap in the schedule until the bus can be replaced.
Overall, trying to keep a bus system running smoothly is a very difficult problem. Lots of people have tried to create better, more robust schedules, but such systems are often complicated and difficult to implement.
John and Don propose a very simple method for handling such a system. The idea is to have a small number of checkpoints in the system (in the example they chose, they had a checkpoint at each end of the route, with the bus going back and forth along the route). When a bus hits a checkpoint, the system checks how far behind the next bus is. If the next bus is expected to hit the checkpoint in 10 minutes, say, then the current bus waits a fixed fraction of that 10 minutes (say .6 times the following time, or six minutes in this case) and then departs. There is a variant when a bus waits at least, say, 3 minutes after the preceding bus had hit the checkpoint. That is the entire system! Ignore schedules, but simply wait a fixed fraction of the time before the next bus arrives.
This simple system has the amazing property that it will self-organize into a nicely spread-out arrangement of buses, and will reorganize itself in the face of bus delays (or speed-ups). If a bus goes out of operation, nothing special needs to be done: the system will automatically move the buses into a evenly spread-out pattern (albeit longer apart, since there are fewer buses). Of course, it also gives up on a fixed schedule, but for systems that arrive often enough, the schedule is generally not relevant to passengers (and in the example they gave, only known to the drivers, not to the passengers).
This research follows their previous work on self-organizing manufacturing systems. The thing I like very much about this entire research direction is how well it includes robustness. While simple, these self-organizing systems respond extremely well to changes in the environment, much better than many optimization approaches.
The presentation was very convincing, and Don and John promise a paper “in a few weeks”. I look forward to reading it in more detail (and perhaps correcting any errors in interpretation I have of their work).
This was just one of the thousands of talks at this conference. I was very glad I went outside of my normal research range to see this talk.
The idea is very interesting but has been introduced to subways in Tokyo.
RE Tokyo: Many transit systems control headways by introducing short delays. What is new here is the way in which the delay is computed, which has the effect of equalizing them all, and without even knowing what the final value will be.