Google just announced some enhancements to their Directions in Maps API. One addition, “avoiding tolls and highways” doesn’t really affect me much: we have only one toll road in the area, and it is pretty well needed to go either east or west. But the other two are exciting!
First, the API now adds bicycle routing. I don’t know if it will let you go the wrong way down one way streets or hop on a crowded sidewalk to make a shortcut, but it does contain at least some of the long-distance bike paths. Check out the path from my house to my buddy Barack’s place. There is a bike path starting from about 20 miles from Pittsburgh all the way to Washington, DC. I turn 50 this year, and have promised myself that I will do that trip. Of course, I have broken promises before, and if I don’t start training soon, it won’t happen. But it is nice to see Google will be by my side if I do set off.
The second, and more relevant to OR, enhancement adds Traveling Salesman routing capability. From the announcement:
Route optimization. Have many places to go but no preference as to the order you visit them in? We can now reorder the waypoints of your route to minimize the distance and time you must travel. Very useful for traveling salesman I hear.
Now I would love to experiment with this! There have been similar efforts before. Gebweb has offered routing since 2007, and promises optimal solutions for up to 15 cities with 2-opting solutions for larger problems. I would love to know how far Google guarantees optimality before resorting to a heuristic (the demo on the announcement page limits you to 11 points). Unlike the other additions, this has not yet made it to Google Maps, but when it does, let’s see how Google competes with Concorde.
Looking at the page source for the demo, it appears that the limit on the number of points is enforced there rather than in the underlying code. It could be that the underlying code has a different limit (or it could be the same limit, and the check is just to handle it gracefully in the demo). I don’t see a limit documented in the API:
http://code.google.com/apis/maps/documentation/v3/reference.html#DirectionsService
It wouldn’t be too hard for someone to use the Maps API to set up a similar demo and remove the limit to see if there is an underlying limit.
There does appear to be a 25-point upper limit as part of the directions API, however, including the origin and destination:
http://code.google.com/apis/maps/documentation/v3/reference.html#DirectionsStatus
Brady
(Note: I work for Google but in a completely different area.)
Doubtful that Google is solving this routing to provable optimality. Even Google doesn’t have that much free CPU cycles! But a good heuristic would still be valuable.