Home About Email Resume Links

08 Oct 2017
Tour de BCycle - Madison

I want to complete a Tour de BCycle: a circuit passing through each BCycle station in Madison. What is the optimal route? How many miles will it be? This is a classic traveling salesperson problem (TSP) and it can be solved in a few steps: obtain the locations of each station, compute the distances between each pair of stations, solve the TSP, and visualize the solution. Luckily all the heavy lifting can be done using a few python packages off PyPi, the great free Google APIs, and some python and javascript stitchwork.

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 distance_matrix() function with 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!

Google FTW again here. Their maps API is the easiest way to put a quick map plot together, even for someone like me with minimal javascript experience. These paths look about like what I would have drawn up by eye. Madison’s isthmus makes the optimal path more obvious than it would be for a city with a more circular layout.

The total distance of this path is 29 miles from first station to last station. Quite doable!

Home About Email Resume Links