Open Source Optimization and the Traveling Salesman Problem
Every computer science student learns about the Traveling Salesman Problem
, where a salesman needs to determine the shortest route for visiting a set of locations. It's a classic NP-hard problem, having no known polynomial-time solution: double the number of locations, and the route will take a lot more than twice as long to compute. But visiting a set of locations quickly is a common problem for businesses (or carpools!), and so we provide a solution via the Google Directions API. For instance, the optimal tour of South Australia's main wine regions, originating from Adelaide, can be computed via the API simply by visiting: http://maps.googleapis.com/maps/api/directions/json?origin=Adelaide,SA&destination=Adelaide,SA&waypoints=optimize:true|Barossa+Valley,SA|Clare,SA|Connawarra,SA|McLaren+Vale,SA&sensor=false
. The result is expressed in JSON, but if you squint a bit you can unravel the path.
The Traveling Salesman Problem is an example of combinatorial optimization
, and our Paris-led Operations Research team has written a slew of optimization code for graphs, knapsacks, linear programming, and constraint programming—including the routing code that backs the Directions API. They've open sourced their work in the or-tools
package, available at https://code.google.com/p/or-tools/
and usable from C++, Python, Java, or .NET.
If you're interested in more details, information about using the API for Traveling Salesman problems is available at: https://developers.google.com/maps/documentation/directions/#Waypoints
If you're curious about how Google calculates traveling salesman routes, read: http://code.google.com/p/or-tools/source/browse/trunk/examples/cpp/tsp.cc
or the more general vehicle routing library at: http://code.google.com/p/or-tools/source/browse/trunk/src/constraint_solver/routing.h
Finally, you can find the or-tools team on G+ at: https://plus.google.com/u/0/108010024297451468877/about