08 Oct 2017
Tour de BCycle - Madison
1. Station Locations
The stations are shown on this map and the latitudes and longitudes are inside a script tag in the html.
2. Distance Matrix
It would be simple to compute the geodesic distances between each station
coordinate, but as the idea is to bike from station to station, Google cycling
directions would serve better. The distances can be computed using the python
googlemaps package to interface the Google Maps API. In order to use this
library, an API key is needed. The Google Maps Distance Matrix and Geocoder
APIs must be enabled on the Google Developer Console. The
mode='bicycling' from the googlemaps package is sufficient to
generate the matrix. I did get API limit errors from this function using a free
API key, which forced me to sign up for a Google Developer one year trial.
Another solution would be computing the matrix elements one by one in a loop
with a delay.
3. Solve the TSP
As there are only 44 stations, a simple implementation of the textbook greedy TSP solution is sufficient for finding a good, but not necessarily optimal, path. I used the tsp-solver implementation off of PyPi. The distance and time edge weightings yielded nearly identical outputs, only a few stations downtown were transposed.
4. Visualize the Solutions!
The total distance of this path is 29 miles from first station to last station. Quite doable!