Because of the sheer number of bridges we were trying to cross, and because the bridges themselves were high complexity, the approaches for finding (or even just estimating) an optimal route weren’t open to us.
So we settled for something that was within reach: a method that would let us at least find a complete path, even if that path did end up re-crossing bridges more than once. We used a greedy search method, which is exceedingly simple:
First, we make a list of all the possible edges we needed to cross, grouped together if they belonged to the same bridge. Then, starting at a random point, we repeated this loop:
- Find a path to the nearest edge bundle
- Cross that bridge, and remove all of that bridge’s associated edges from the list of edges that need crossing
- Find a path to the next nearest bridge we haven’t crossed
- Don’t re-cross an already-crossed bridge to do this
- UNLESS we have no choice, then we’ll re-cross one or more bridges to get to the next uncrossed one.
- Cross that bridge, removing its edges…
- And repeat.
Watch it in action and you’ll see the downside right away:The algorithm is totally focused on getting to the next closest bridge, and has no capacity to “plan ahead” and judge if going to a slightly further-away bridge will let it cross a whole bunch more without doubling back frequently. Therefore, it ends up leaving behind sets of bridges that it then has to backtrack to get to, often by crossing back over a bridge it already crossed. The upside, however, is that it doesn’t require intensive computation to make each decision, and so it can give you a path through the city in a matter of seconds or minutes, rather than years of computation.
To implement this algorithm as code, we used R to build out a few different code packages. The first, pathfinder, is an internal library that actually does the greedy search across a graph, relying on the igraph library to do most of the distance calculations and pathfinding. Pathfinder works in 3 steps:
- It calculates 3 distance matrices between all the endpoints of bundles in the graph. The first matrix calculates the distance between bundles without crossing any intermediary bundles, used when we need to cross roads from one bridge to another. The second matrix calculates distances across bundles, which we need to know in order to choose a path that will actually go all the way across a bridge instead of doing a u-turn in the middle of it (an occasional issue in our experiments!). Finally, the third matrix calculates distances between bundles again, but allows for cases when we need to “cheat” and cross an intermediate bundle or two.
- Alternating between these matrices, the pathfinder program follows the greedy search algorithm and produces a list of steps from node to node through the graph.
- From this node sequence, we finally calculate the actual turn-by-turn directions on the full graph.
Pathfinder is only concerned with the graph data – it assumes that we’ve already done the spatial computing to pick which edge bundles need crossing, and what numeric distance (in whatever unit) to assign to each edge. To do all the other bridge&map specific processing on top of this, we built konigsbergr, which does all the OSM data pre-processing including calculating road distances, creating a graph object from the map data, running the pathfinder functions, and then plotting the results back onto a map. Konigsbergr is the package that you’ll want to use if you want to try out this code on your own city or town, and we’ve written up a how-to guide on how to use its functions on your own computer. (Warning: this package does assume that you already know how to get R up and running on your computer.)
We end up with a pathway that’s a whole lot lengthier than it probably needed to be, but it does hit all the bridges, and it manages to do so without too much recrossing: to go to all of the car-accessible bridges in Pittsburgh (ignoring highway on/off ramps)w takes about 650 kilometers. This does mean that it ends up crossing 28 of the 178 bridges more than once, with (unsurprisingly) the large and centrally-located Veterans’ Bridge getting crossed 3 times in our path.
See the full data and the build script used for this project on CMU’s KiltHub repository.