{"id":1255,"date":"2010-11-08T19:53:16","date_gmt":"2010-11-08T23:53:16","guid":{"rendered":"http:\/\/mat.tepper.cmu.edu\/blog\/?p=1255"},"modified":"2010-11-08T19:53:16","modified_gmt":"2010-11-08T23:53:16","slug":"bus-bunching-talk-at-informs","status":"publish","type":"post","link":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/2010\/11\/08\/bus-bunching-talk-at-informs\/","title":{"rendered":"Bus Bunching talk at INFORMS"},"content":{"rendered":"

New post at the INFORMS site: “Avoiding Bunches of Buses”<\/a>:<\/p>\n

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.\u00a0 I hopped in to see a talk given by Don Eisenstein<\/a> on work he has done with John Bartholdi<\/a> on \u201cscheduling\u201d buses.\u00a0 Don and I were in graduate school together, and we each had John as our advisor, but we work in completely different areas.<\/p>\n

\"\"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.\u00a0 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.\u00a0 This phenomenon<\/a> is common enough to form the title for a popular mathematics book<\/a>.\u00a0 Upon reflection, this situation is not mysterious.\u00a0 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.\u00a0 Once delayed by two minutes, more passengers will arrive in the now-12 minute gap, further slowing down the bus.\u00a0 Meanwhile, the bus following the delayed bus will go faster than normal due to a dearth of passengers for it.\u00a0 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.<\/p>\n

This bunching behavior is very common, and very difficult to schedule around.\u00a0 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.\u00a0 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.<\/p>\n

Overall, trying to keep a bus system running smoothly is a very difficult problem.\u00a0 Lots of people have tried to create better, more robust schedules, but such systems are often complicated and difficult to implement.<\/p>\n

John and Don propose a very simple method for handling such a system.\u00a0 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).\u00a0 When a bus hits a checkpoint, the system checks how far behind the next bus is.\u00a0 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.\u00a0\u00a0 There is a variant when a bus waits at least, say, 3 minutes after the preceding bus had hit the checkpoint.\u00a0 That is the entire system!\u00a0 Ignore schedules, but simply wait a fixed fraction of the time before the next bus arrives.<\/p>\n

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).\u00a0 If a bus goes out of operation, nothing special needs to be done:\u00a0 the system will automatically move the buses into a evenly spread-out pattern (albeit longer apart, since there are fewer buses).\u00a0 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).<\/p>\n

This research follows their previous work<\/a> on self-organizing manufacturing systems.\u00a0 The thing I like very much about this entire research direction is how well it includes robustness.\u00a0 While simple, these self-organizing systems respond extremely well to changes in the environment, much better than many optimization approaches.<\/p>\n

The presentation was very convincing, and Don and John promise a paper \u201cin a few weeks\u201d.\u00a0 I look forward to reading it in more detail (and perhaps correcting any errors in interpretation I have of their work).<\/p>\n

This was just one of the thousands of talks at this conference.\u00a0 I was very glad I went outside of my normal research range to see this talk.<\/p><\/blockquote>\n","protected":false},"excerpt":{"rendered":"

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.\u00a0 I hopped in to see a talk given by Don Eisenstein on work he has done with John Bartholdi … Continue reading “Bus Bunching talk at INFORMS”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4,46],"tags":[],"class_list":["post-1255","post","type-post","status-publish","format-standard","hentry","category-applications","category-research"],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/posts\/1255","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/comments?post=1255"}],"version-history":[{"count":0,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/posts\/1255\/revisions"}],"wp:attachment":[{"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/media?parent=1255"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/categories?post=1255"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mat.tepper.cmu.edu\/blog\/index.php\/wp-json\/wp\/v2\/tags?post=1255"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}