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:,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 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:

If you're curious about how Google calculates traveling salesman routes, read:
or the more general vehicle routing library at:

Finally, you can find the or-tools team on G+ at:
Shared publiclyView activity