Shortest Route to Visit the Parklets of San Francisco

A few months ago Curbed SF published an article on 43 Awesome San Francisco Public Parklets.  These parklets are a public-private partnership, where the land is publicly owned (usually part of a sidewalk) but a nearby business (usually a cafe) maintains it.  The parklet becomes part of the outdoor seating for the business, but anyone can hang out there, even if they are not customers of the business.

Some are quite unusual, such as the one at the Rapha Cycling Club:

Rapha Cycling Club Parklet

I thought it would be interesting to calculate the shortest cycling route that visits all the parklets (the classic Travelling Salesman computer science problem).  Since I have been recently working with Mapbox, the rapidly growing alternative to Google Maps et al, I thought it would be a good test case for Mapbox’s relatively new driving directions feature (to calculate the distance of the best route between any pair of parklets, which then goes into the Travelling Salesman algorithm).  Unfortunately this only supports vehicle mode right now (no cycling mode) so for now this is the driving version of the shortest route.

The best result I have found so far is 44.46 miles:

Shortest Driving Route

Method:

  • I located a KML of the parklets (actually a set of 63 of them, so different from the Curbed SF set) via http://pavementtoparks.sfplanning.org/
  • I found a Python implementation of a Travelling Salesman algorithm.  As the Wikipedia article discusses, this is a surprisingly difficult problem to solve, because the number of permutations grows exponentially as one adds locations.
  • Hence the route above is not the perfect solution, but merely the best that the algorithm can find in a reasonable amount of time.
  • I wrote a Python script to pull in the parklets KML, use the Travelling Salesman algorithm together with the Mapbox Driving Directions API to find the best route, and output it to KML.
  • Finally I created a Mapbox map and used their Omnivore Javascript library to overlay the KML on the map.

Now I need to create the cycling version…