4 ms·

It would be nice if Google Maps started doing a decent job, though. I lived for years in NJ and I would typically require 3 roads and 20 minutes to get anywhere

by lnanek2 11y ago

It would be nice if Google Maps started doing a decent job, though. I lived for years in NJ and I would typically require 3 roads and 20 minutes to get anywhere I needed to go shopping because I would drive to the highway, hop on, get off on the road to my destination, then be there. Even if I avoided the highway I would get there in 30 minutes with smaller roads, taking the minimum needed to go the right direction toward the destination. Google Maps? It was a disaster. It would take the small roads since it couldn't bear to drive 2 blocks the wrong direction to get on the highway, then every small road it would alternate taking a left and a right and end up with dozens of turns when a human only needed 3 or 4. I actually met the ex-Googler who bragged about writing that algorithm that alternates left and right, I think he must be responsible for millions of hours of lost time for drivers just because he didn't realize turning has a cost and was trying to draw a diagonal as best he could. Does it really make sense to brag about fast calculation speed when the calculation is a disaster? I'd rather wait a minute for a calculation and get the right one, than have the wrong one back in 3 seconds. I think the Google Maps engineers don't understand this.

lorenzhs 11y ago
Actually, the algorithms used are provably optimal in regard to whatever metric is plugged into them. This means that no matter which of these algorithms you use (including Dijkstra or A*), you will get the exact same result. The difference is in the time and space required for precomputation vs at query time. That includes Contraction Hierarchies, which Google Maps uses (or used?). But if they screw up the optimization metric, then the algorithm can't save them either.
codeka 11y ago
I work on Google Maps and can confirm that it definitely takes the time required to turn left vs. right into account. If you send me an example of a bad route (you can use the web interface, which uses the same backend as Google Maps on your phone) I can take a look as to why it's routing you the way it is. My email address is in my profile.

by lnanek2 11y ago

lorenzhs 11y ago

Actually, the algorithms used are provably optimal in regard to whatever metric is plugged into them. This means that no matter which of these algorithms you use (including Dijkstra or A*), you will get the exact same result. The difference is in the time and space required for precomputation vs at query time. That includes Contraction Hierarchies, which Google Maps uses (or used?). But if they screw up the optimization metric, then the algorithm can't save them either.

codeka 11y ago

I work on Google Maps and can confirm that it definitely takes the time required to turn left vs. right into account. If you send me an example of a bad route (you can use the web interface, which uses the same backend as Google Maps on your phone) I can take a look as to why it's routing you the way it is. My email address is in my profile.