Implement a Bus Trip Planner For Auto-Selecting Best Routes from A to B

[epicstar]

In generalized terms... given a set of two points, find a set of bus routes that gets you from point one to point two. For a general set use-case, the first point... or the "from point" is your current location and the second point, or the "destination point", is the point of interest you are trying to get to by using the bus. We will, however, try to code this by traveling to any two points within pittsburgh.

[epicstar]

Google Places API is a nice start to find a repo of points of interests that are searchable. This may however cost money if it is used a lot.

[epicstar]

Seems we could use the Port Authority trip planner... let's see if they will open it

[epicstar]

The implications of this is that we will need to find a workable search space to connect two points to each other via bus routes.

I believe the fastest and most feasible way to search this is through bus stop metadata. Each bus stop is assigned a list of bus route numbers.

I think this is how this will work and feel free to veto/throw out other ideas:

1. find the closest bus stops on both points at a certain radius
2. create a set of bus routes from all bus routes that are attached to the closest stops of each point. Each point will have a set of bus routes. Note that this requirement should intersect with another issue where I want to automatically select all visible bus routes of a given point.
3. find all intersecting bus routes on both lists of bus routes for both points. The final result should give you the final list of bus routes that will directly take you from the "from-point" to the "destination point"

Limitations:

1. This will not currently work on points that require a connection, or routes that require 2+ buses to get from the "from-point" to the "destination point". I still need to figure out how to do this, but we could probably extrapolate this data based on another structure that will give you a list of bus routes that share bus stop information of a current bus route.

Required data:

1. figure out how to get all relevant bus stop data into the app considering the minimum memory constraints of the phone
2. find a way to do a search on all bus stop data to find the closest stops of one point in minimal time... preferably not O (N).

[epicstar]

Constraints here:

1. API to get updated static data easily
2. Exploration of GTFS data directly in app -- out of the question?.... However I found an article that discusses saving GTFS data on a mobile phone... Investigating this in a comment below
3. Associating routes for a given stop in GTFS requires a join on GTFS data by the stops, stop_times, trips, and routes data. See comment below for details on this.
4. Found a way to get the map's visible region's visible latitude and longitude bounds: http://stackoverflow.com/a/34045495/4425374

[epicstar]

On the note of GTFS directly on our app.... Seems we will have to process GTFS on a server, make it small enough for use, then send it to the mobile app and have it store that small data. I think storing a binary RTree of the data we need to make the trip planning possible will be a trivial amount of MBs but we have to find a cloud server that will be able to securely and with minimal money, send this data to the client.

EDIT: Maybe not... see below

[RitwikGupta]

This could possibly be done on a micro AWS instance?

[epicstar]

Yes, this is a possibility. The only problem with AWS is that it's only free for a year. This is why I'm trying to find ways to get this GTFS data to be able to be read on an android phone. Google and Azure seem to have free options, but Amazon may be a good idea to get the iOS version of the app running.

[epicstar]

I just pushed a branch gtfs-prototype that takes in a zipped gtfs file (~6MB) and creates a stop to routes mapping. The process on my computer took 3.5 seconds and the output file is only 1.7 MB to store as an unminified json with the aid of the OneBusAway API which read the zip files in a stream. This seems to be completely reasonable to store this data in a java object on an android phone.

However, I'll be interested to see if the OneBusAway library will actually work on an android device (the limitation is that the API requires sl4j for no reason....). After that, I need to see the feasibility of using the rtree library linked above with this data on my computer then on an android phone.

If we find that the rtree is too much to handle for both ends, we can just do an O(N) search on finding the best buses between 2 points as opposed to a 2 log n search.

These guys here have an API to get the latest info for a certain GTFS data in zip format which I already have a key of: http://transitfeeds.com/api/