Record Details

Commuting with delay prone buses

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title Commuting with delay prone buses
 
Creator DATAR, MAYUR
RANADE, ABHIRAM
 
Subject algorithms
mathematical models
theorem proving
problem solving
 
Description What is the fastest way to go from point X to point Y within a
city using its public bus service, with bus changes as necessary?
If buses ran according to a schedule this is an easy query -
it can be solved by using classical shortest path algorithms.
Unfortunately, as everyone knows, buses in most cities hardly
confirm to a fixed schedule. Once you get into a bus it usually
takes a predictable amount of time to reach its destinb.tion, but
the amount of time you spend waiting for it is quite random
and can usually be estimated only statistically.
We present an algorithm to generate travel plans for such
conditions. Our plans allow actions of the form "wait for buses
with route number R1,R2 ... if you get into R1 get off at ...
and wait for ..., else if you get into R2 ..." and are modeled
as a tree. We guarantee that the expected time taken by
the plan we generate will be minimum over all possible plans
for travel between the given starting point and destination.
The algorithm has been implemented for the bus system of
Mumbai, and it generates the (optimal) travel plan essentially
instantaneously. A transcript of a session with the program is
included.
 
Publisher Society for Industrial and Applied Mathematics
 
Date 2009-07-04T06:27:46Z
2011-11-28T08:44:47Z
2011-12-15T09:57:47Z
2009-07-04T06:27:46Z
2011-11-28T08:44:47Z
2011-12-15T09:57:47Z
2000
 
Identifier Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms, (SODA), San Francisco, California, USA, 9-11 January 2000, 22-29
0-89871-453-2
http://hdl.handle.net/10054/1593
http://dspace.library.iitb.ac.in/xmlui/handle/10054/1593
 
Language en