Massachusetts-Bay-Transportation-Algorithm

An algorithm to collect data to find the best path to break the world record time to visit every MBTA subway stop

Project Info

Architecture

This project was written exclusively in Go. We chose Go because of its easy to use, built in concurrency. We did not end up doing as much parallel work as we originally intended, but it did help us speed up our execution time some.

Package Layout

• main.go - This executes the main program. All it really does is tell our command line code to execute.
• calculation/ - This package holds all of our code for actually calculating out the best route given a dataset.
  • calculation/cubic_spline.go - This file holds all of our code for taking in edge data that we save from the Google Maps API and makes cubic spline approximations for each edge.
  • calculation/route_calculator.go - This file holds all of the code for doing the actual calculation. There is a struct defined called Calculator that holds the methods and data for running the calculation.
• datacollection/ - This package holds all of our code for getting and saving API data from both Google Maps and the MBTA. It also holds the JSON files that we save.
  • datacollection/google_api.go - This file holds all of our code for interfacing with the Google Maps API. Included is functions to get all of the edge timing data that we need and save that data to a file, reconstruct a route using the Google Maps API, and some helper functions dealing with our data structure for holding the edge data.
  • datacollection/mbta_api.go - This file holds our code for interfacing with the MBTA API. It has a function to get and write all of the MBTA stop information we need to a file.
• cmd/ - This package holds the code for all of our command line functions.
• scripts/ - This folder is separate from the actual Go code that we run. It holds some Python scripts that we wrote to visualize some of our data and graph data structures.

How To

Compile the program

Run go build -o mbta main.go

Fastest way to try out calculations

go run main.go calculate -i datacollection/EdgeData 2019-07-31.json

That command will write the results to results.json. Expect it to take somewhere in the realm of 8-12 hours on a good computer.

Command Line Tools

1. ./mbta collectdata - Has some tools for getting our edge data from the Google Maps API. You must have a Google Maps API key to be able to run this. By default, place this key in ./apikey.secret. You can also specify the flag --apikey <filename>. The only required flag to pass is --date, which provides the date on which you want to collect data for. It will save the data to datacollection/EdgeData\ <date>.json. Note that there are already some EdgeData JSON files in that folder to try our program with, so you do not need to run this command if you just want to give the program a try. There are also the update and view subcommands which will give you the ability to update existing edge data or view an edge data file easier.
2. ./mbta calculate - This is the main portion of our program. It takes edge data and runs the calculation algorithm we made to find the fastest route. You must pass an input file of edge data to it using the -i or --input flag. It will begin running all routes for a day to find the fastest and eventually write the results to a JSON file. Expect this to run for 8-12 hours on a good computer.
3. ./mbta reconstruct - This command takes in an input file which should be a results file generated by the calculate command. It will ask for which route you want to reconstruct and then will ask the Google Maps API for directions. It will then print all of the fully reconstructed directions for that route. You must have an API key for this command as well.
4. ./mbta plot - This command will graph out the cubic spline approximation of given edge data from an edge data file and save that graph to an image file. Passing in only the input and output will plot all edges on one graph. You can also specify an edge using --stopA and --stopB.