I’m trying to implement a small routing engine using OSM data. I looked at the OSM wiki and found only resources to existing routing API’s. I really want to understand how routing works in general and build my own routing engine from scratch. I looked into Valhalla’s logic for routing within their Github repo, but it was not easy to digest coming from a non-GIS background.
My end goal is to take a starting point (lat.,long. coordinates), provide X amount of miles in any direction, and then go X amount of miles to find the destination (again, in lat.,long. coordinates). I want to geofence this route, save it as an object and then pass it around in a separate service.
First up, OSM data needs to be preprocessed for routing purposes. A routing graph is a series of “edges” (connections) between “nodes” (junctions). That’s not how OSM’s default data storage works.
Fortunately, someone has written a preprocessor for you that will take an OSM extract (say, a city or county, downloaded from Geofabrik) and make a node-based graph out of it. So that’s the first step done. Here it is:
This means you can concentrate on writing the routing engine itself. The foundation of pretty much all routing is Dijkstra's algorithm - Wikipedia. Try to implement this - it’s not at all hard to get a basic version working, though to make it performant requires more thought.
Once you’ve got this up and running, you can choose where to focus next. A faster routing algorithm? (A* is the usual “next step” after Dijkstra.) Some work on your front-end? Better road costings? A smarter graph incorporating turn restrictions etc.?
What you probably want to do is break down the data you want to route over into a “connected graph” that shows where the choices involved from going from one place to another.
The edges of that graph have attributes such as “what can travel along it” and “how fast”.
You’d then typically apply an off the shelf routing algorithm or a variation of one to that data, and it’ll give you the “best” route.**
A little light web searching for e.g. “road routing algorithms” will turn up plenty of help.
** or you can just try “trial and error” or “random” or anything else you want - the algorithm is to get you an answer quickly; trying all the options will get you an answer eventually.