Commuting with delay prone buses
DSpace at IIT Bombay
View Archive InfoField | 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
|
|