I got that impression, too. On multiple occasions I ignored a suggested turn because I was pretty certain it would be slower, and as soon as Waze adjusted the route based on my turn, the ETA went down. So it should have sent me the right way to begin with, but wanted to experiment with me to test an alternate route.

After enough of those, I reluctantly stopped using Waze.

Yep, I have the same experience. Sometimes it keeps telling me to do a U turn and turn around on their original route. I need to hit stop and reroute sometimes. Definitely not smart...

I use Waze mostly for the police presence. And there was a lot today (end of month...).

A nice feature would be if it sees more police presence than usual you just get a general warning "there's more police presence on your route than usual".

perhaps it's load balancing for other cars. If one entity controls a significant enough portion of the total traffic in the system they might sometimes make a decision that negatively impacts one packet if it helps a sufficient number of other packets.

Absolutely sure Google Maps A/B tests routes too.

Even when sitting next to each other in the same car, Google Maps suggests radically different routes to the same destination on my wife’s phone than it does on mine, often with a 15+ min difference in arrival time. It must be testing different routing algorithms as otherwise they should be the same.

Could also be an optimal routing thing too. If google maps sends everyone down the same path it might become too congested. Especially if the route is a detour around construction or and accident or something.

I think routing is one of those computationally expensive problems (possibly np-complete) to solve. As a result, there's a bunch of clever non-deterministic approaches that get you "pretty good" answers, but depending on the implementation can produce variable results.

A-to-B routing is simple and not very expensive. You can implement it without very much graph theory knowledge. It's when visiting a number of destinations in an arbitrary order that things get difficult.

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.

I wouldn't have thought that was necessary, surely. There will be enough Android phones travelling any point in the road network to generate enough data, without Google attempting to generate more data.

The flipside to me is that Waze will send lots of people down the "time saving" path, which is usually a small road, and kinda defeats the purpose.

I think Waze only really saved time when it wasn't popular. Once everyone takes the same shortcut, you're back where you started.

Waze takes more risks, that's for sure. It's still the best one if you know the area you're driving and are willing to ignore the maps.

I still use Google Maps when I'm unfamiliar with the drive for the reasons you mention (ie, it needlessly took me down a busy grid-locked road once).

But otherwise nothing beats Waze for the additional features like construction and police reporting plus it does a good job of finding fast routes far more often than not.