Metabolic Path Finding (day of hacking with Jeremy)

My college roommate Jeremy Horwitz visited, and he mentioned that he was trying to figure out how to solve a scavenger hunt path problem in San Francisco. It sounds on the surface exactly like classical Traveling Salesman: 16 points, and what order should you visit them?

But it turns out that walking in San Francisco isn't like LA. There are hills, and you sort of want to optimize for them when you're planning to walk around. So we started wondering if we could model how hard a hill is to climb.

Jeremy found the SF bike route planner, which we used as a base. The author had a friend with GIS software, who associated height data with each street crossing in the city. This height data makes it easy to compute slope for each span (and dx/dy is the standard way, not degrees).

However, the author just put a threshold to avoid ever taking paths that were too steep. There's no real sense in his code that going up or down is either worse or better than biking on a flat surface.

By now we had started Googling for biometric data about how efficiently people walk at different slopes, and it turns out there are some really great studies about this.

Back in 1938, a researcher named Margaria had found that walking at a -10% grade was the most efficient for humans. Fast-forward to 1993, and a paper by Minetti et al measures oxygen intake at different grades, and even does a nice quadratic fit at different speeds!

On to the races.

I was able to make the following two-liner change to the bike route planner to utilize this data. I just assumed the "most efficient" walking speed, but you can tune based on faster velocities or whatever you want.

  inclinepct = 100 * incline
  inclinePenalty = 110.87 + 10.114 * inclinepct + 0.516 * inclinepct * inclinepct


So now, we have a way to compute all the pairs of asymmetric weights for a graph, and the path finder will use it to compute routes around San Francisco!


But as you recall, the original problem is to do a walking tour to a number of points in San Francisco in minimal time. This is a "traveling salesman problem" and it's very expensive in the brute force case (O(n!) even). Most approximate solutions assume points are either Euclidean (i.e. simple edges weighted only by distance), or they assume symmetric weights (i.e. going from A to B costs the same as going B to A).


We found that most of the good approximate solvers at least made the symmetric assumption. However, we also learned about a technique to split the set of points into two digraphs (with twice the points total), such that each graph is only connected to the opposite side's nodes. This makes it possible to simulate an asymmetric graph using a symmetric solver.


We were able to convince ourselves using Georgia Tech's Concorde TSP solver that the whole thing could be solved for 16 points to visit using only seconds of CPU.


Time to prototype: ~12 hours to make scavenger hunts more efficient.

Most awesome thing: knowing how much oxygen you might use, walking between two places.