Building a roadways graph from OpenStreetMap data

Today we extracted a graph of roadways from the for the city of . Why Lima? It's fairly large but not whole world so we can ramp up the problem size. This process turned out to be pretty straightforward and after cleaning up a few minor mistakes we got the problem running.

First we tried IDA* and that turned out to be really slow to make progress because there are a lot of very minor improvements in the distance with this larger dataset. We'll have to consider some alternatives to that in the future but in order to keep making progress today we just switched over to vanilla A*. There are roughly 800,000 edges in this final graph so A* shouldn't take very long even if it has to explore a large number of them. For the heuristic we used to calculate straight line distance on the surface of a sphere.

Guess what? IT WORKED! And we plotted the route on Google Maps! This felt like such an accomplishment and it was really incredible, so thanks to everyone who joined me on this journey so far. <3

• Please share with everyone!
• Wed, Thur, Fri from 12 to 2PM EST.