Commuting with delay prone buses

Abstract

What is the fastest way to go from point X to point Y within a\ncity using its public bus service, with bus changes as necessary?\nIf buses ran according to a schedule this is an easy query -\nit can be solved by using classical shortest path algorithms.\nUnfortunately, as everyone knows, buses in most cities hardly\nconfirm to a fixed schedule. Once you get into a bus it usually\ntakes a predictable amount of time to reach its destinb.tion, but\nthe amount of time you spend waiting for it is quite random\nand can usually be estimated only statistically.\nWe present an algorithm to generate travel plans for such\nconditions. Our plans allow actions of the form "wait for buses\nwith route number R1,R2 ... if you get into R1 get off at ...\nand wait for ..., else if you get into R2 ..." and are modeled\nas a tree. We guarantee that the expected time taken by\nthe plan we generate will be minimum over all possible plans\nfor travel between the given starting point and destination.\nThe algorithm has been implemented for the bus system of\nMumbai, and it generates the (optimal) travel plan essentially\ninstantaneously. A transcript of a session with the program is\nincluded.

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 16 citations exist upstream.