In a follow-up to yesterday’s post about Portland’s bike path plans, Brandon Martin-Anderson explains how his least-hilly bike trip finder works on Seattle’s BadHill:
The backend router works by finding a path which minimizes the total sum of energy expended riding from origin to destination. This is actually relatively simple, as there are well-established algorithms for finding the “least” path between two points in a network, and in my case the “least” that it finds is ‘energy expended on road link’.
Because you theoretically spend the same amount of energy climbing a given altitude no matter what the slope is, BadHill’s routing engine doesn’t really *care* what the slope is, as long as you never have to waste elevation gain. Say you have to travel five miles with 500 feet of elevation gain. BadHill would rather you shoot up those 500 feet in a block with crampons and caribiners if that meant it was totally flat the rest of the way, as alternative to a gentle slope upward which occasionally dips down a little bit.
This is obviously a problem in some circumstances, but it ends up being mathamatically simple and “workable” for the beta. I’ll fix it eventually.
Incidentally I went out riding last night to test out some of BadHill’s recommended routes and discovered that my algorithm needs some tweaking. There was a hill where there shouldn’t have been. It was bad.
If anyone else ever tries to patent this, you’ve got your prior art right here. Not sure whether Portland’s Metro is working on a similar solution and showing the results in Google Earth, or whether they are reying on Google for the backend. I’ll try to find out.