Jerry Jariyasunant (jjariyas_at_gmail) and Dan Work (dbwork_at_berkeley)
There are many tools available for automobile navigation, but relatively little attention has been paid to public transportation. Neither Yahoo Maps or Microsoft Live Search Maps offer transit info (as of may 14, 2008). Current applications for public transportation such as Google Transit use schedules (implemented for Muni April 27, 2008), but only about 70% of the buses in the Bay Area run on time.
Real-time bus positioning information is available through NextBus. NextBus also offers a transit map, but does not plan routes for users. Google Transit and 511.org plan routes, but do not use real-time bus information.
This project aims to address the above issues by linking NextBus with routing capabilities on mobile devices such as the Nokia N810.
Poster: real_time_transit.pdf
Demo video: http://www.youtube.com/watch?v=IrnwsTdh524
Source Code: transit.zip - Contains GE_Start.jsp, GE_Stop.jsp, and transit.jsp.
GE_Start.jsp is the home page of the application. It reads from a database to place the current GPS location on the map and also allows the user to select his desired destination through a point drag and click interface. The GPS location is sent to the database with the program provided by the GPS group in the short project, called gpstracer gps. After the starting point and destination are input, the user is redirected to GPS_Stop.jsp , where the fastest route is determined by transit.jsp, and the results are displayed.
The transit program (transit.jsp) is used by GE_Stop.jsp , which translates the text results of transit.jsp and converts the information into a familiar Google Maps visual interface. Transit.jsp uses two databases: one which has information about fastest static routes, and the other has travel time information to be used in conjunction with NextBus information to build dynamic routes. The routing database was constructed by performing an all-pairs shortest path algorithm for all bus stops in the SF Muni and AC Transit network. Because an all-pairs shortest path algorithm using Dijkstra's algorithm or the Floyd-Warshall algorithm is computationally intensive for a network with over 3,000 bus stops, we created another algorithm that uses characteristics of the transit network to significantly speed up this task.
The transit time database was constructed by gathering historic travel time data from transit schedules. Combining the transit time information with the location of the bus stops, candidate routes were built statically. For transfer points, the estimated wait time was calculated using half the average bus headway. Transit.jsp accesses this database and combines the top candidate routes between two points with data gathered from NextBus to provide the best possible route, which is returned to GE_Stop.jsp and displayed on the map.
Go to http://128.32.196.78/transit/jerry/GE_Start.jsp to see a live demo. The project location may change as we continue to improve it.