I've long wished that Google Maps would allow you to enter a list of destinations and then optimize a route for you to visit all of them. Only recently did I realize the obvious reason that Google doesn't include this functionality!

Such route/destination optimization is basically a (slight) variant of the travelling salesman problem (TSP), which is NP-hard. This means that every NP-complete problem could be solved in polynomial time if one had access to a TSP oracle.

If Google Maps would solve TSP for you, it wouldn't exactly be an oracle but it would likely be a lot faster than the computer you've got at your desk. People would quickly hack Google Maps' web interface to use Google's vast server farms to solve NP-complete problems. Even a small number of complex TSP problems could bring Google's servers to a crawl and disrupt service for millions of other users.

Hence, Google Maps won't optimize the order that you visit your destinations.

(Note: even if Google limited the number of destinations that could be optimized or put other trivial restrictions on how you could use the algorithm, users could bypass these restrictions by chaining calls in various ways.)

0 TrackBacks

Listed below are links to blogs that reference this entry: Why Google Maps Won't Let You Optimize The Order You Visit Destinations.

TrackBack URL for this entry: http://www.mwilliams.info/mt5/tb-confess.cgi/8069

Comments

Supporters

Email blogmasterofnoneATgmailDOTcom for text link and key word rates.

Site Info

Support