A-to-B routing is simple
in theory. In practice implementing A* on a graph of all the roads in the world is non-trivial. You'd need to figure out some way to split the data up into chunks or to make neighbourhood lookups fast enough to be workable. I'd imagine you'd end up with something of at least the complexity of hierarchical A
, but depending on the size of your chunks you'd need to still special-case the start and end chunks. And that's just the first complexity I can come up with.I imagine the distance is going to be wildly* nontrivial as well. You'd need to factor in traffic density, weather conditions, road works, predicted traffic density, actual distance as well as traffic speed, not to mention fuzzy human things like scenery. Just going for "shortest euclidian distance" will end up with routing through every alley and side-street if it's even the tiniest amount shorter.
I wouldn't be surprised if you end up with a distance metric that looks essentially random unless you're deeply inspecting the graph at the time of routing to see why a certain route is shorter than another.
Of course that doesn't exclude A/B testing, but with google maps they clearly have a routing graph that's updating all the time. It's no surprise that asking for the same route twice can give you different answers. Not to mention they probably include a random factor on purpose so they don't route all the cars through the same street. Of course you'd want the random factor big enough to spread the load, but not so big that random people get shafted by a significantly longer commute.
Seems like an interesting problem to tackle actually, I should look at building an open street map based route planner sometime.