Shared publicly  - 
 
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
52
35
Sylvain Soliman's profile photo
Add a comment...