Open Source Google Maps Running Locally (Project OSRM)
Road navigation is one of the largest and hardest real-life graph theory problems. The Open Source Routing Machine (OSRM) project has two algorithms for shortest path discovery. Multi-Level Dijkstra (MLD) adds precomputed hierarchical partitions to the graph search in order to reduce the size of the search space for the shortest path. The other algorithm is contraction hierarchies (CH), which is a strategy for simplifying a graph by removing nodes.
It worked right off the bat in docker, but to develop the project I needed to compile it outside of a container. Since OSRM, like any reasonable open source project, doesn't support Arch Linux, I had to install an Ubuntu virtual machine to run it. After a few hours of configuration and dependency issues and port forwarding weirdness I got it running locally!
Next, I want to write my own custom routing algorithms, and try to get better at C++ while I'm at it.