Robert E. West

Google Transit is an amazing service for finding the fastest route to a destination using local transit systems. However, their website states that a transportation service can only participate if it is "open to the public". Many universities, including the University of Virginia (UVA), have heavily-used transportation services that do not qualify for inclusion in Google Transit because they are limited to university students.

The goal of this project was to create a Google Transit-like service for UVA students that can find the fastest route to a destination via UVA's University Transit Service (UTS). However, it could easily be used with any transit service whose information is available in the TransLoc PublicAPI. At the time of this writing, there are 91 such transit services, including those at Harvard University, Princeton University, and Duke University.

The algorithm works by representing the user's current location, the destination, and all bus stops as nodes in a graph. Then, for each route, all of the nodes in that route are connected in order with directed edges. Finally, edges are added from the user's location to every stop and from every stop to the destination so that there is always the option of walking instead of riding (because that does turn out to be faster surprisingly often). All information about bus stops, routes, and real-time bus arrival estimates are provided by TransLoc. Once the problem has been encoded as a graph, Dijkstra's algorithm is used to find the shortest path through the graph, which corresponds to the fastest route.

While this may sound straightforward, there are a variety of challenges. First, bus routes change over time. In the short term, there are both night-only stops and routes that only run in the morning or evening. In the long term, universities will add, remove, or rename both stops and entire routes. Also, while TransLoc provides which bus stops are on which routes, it does not provide the order in which bus stops occur on a given route. Finally, the weights of the edges in the graph (corresponding to the time required to traverse that edge) change over time. After choosing to walk to a stop that is 10 minutes away, for example, all of the buses have moved. If you chose instead to walk to a stop that is 15 minutes away, the buses will have moved further. Deciding which is faster is a fascinating problem. A more in-depth technical description of the project, including how these challenges were addressed and more, can be found here. Also, if you have any questions or would like to know more about this project, please don't hesitate to Contact Me!