Overview
The Traveling Salesman Problem is one of the most famous problems in computer science. In what follows, we'll describe the problem and show you how to find a solution.
The problem
Back in the days when salesmen traveled doortodoor hawking vacuums and encyclopedias, they had to plan their routes, from house to house or city to city. The shorter the route, the better. Finding the shortest route that visits a set of locations is an exponentially difficult problem: finding the shortest path for 20 cities is much more than twice as hard as 10 cities.
An exhaustive search of all possible paths would be guaranteed to find the shortest, but is computationally intractable for all but small sets of locations. For larger problems, optimization techniques are needed to intelligently search the solution space and find nearoptimal solutions.
Mathematically, traveling salesman problems can be represented as a graph, where the locations are the nodes and the edges (or arcs) represent direct routes between the nodes. The weight of each edge is the distance between the nodes. The goal is to find the path with the shortest sum of weights. Below, we see a simple fournode graph and the shortest cycle that visits every node:
In addition to finding solutions to the classical Traveling Salesman Problem, ORTools also provides methods for more general types of TSPs, including the following:
 Asymmetric cost problems — The traditional TSP is symmetric: the distance from point A to point B equals the distance from point B to point A. However, the cost of shipping items from point A to point B might not equal the cost of shipping them from point B to point A. ORTools can also handle problems that have asymmetric costs.
 Prizecollecting TSPs, where benefits accrue from visiting nodes
 TSP with time windows
Solving TSPs with the Google Directions API
Google also provides a way to solve simple TSPs of realworld locations without downloading ORTools. If you have a Google Directions API key, you can solve TSPs of realworld locations with the Directions API, providing the locations in a URL and getting the response back as JSON. You'll need your own free Directions API key for development, or an enterprise key for commercial use.
As an example, here's a URL that can be used to find a short tour of winemaking regions in South Australia, beginning in Adelaide. If you want to try this from your browser, replace API_KEY at the end of the URL with your key.
https://maps.googleapis.com/maps/api/directions/json?origin=Adelaide,SA&destination=Adelaide,SA&waypoints=optimize:trueBarossa+Valley,SAClare,SAConnawarra,SAMcLaren+Vale,SA&key=API_KEY
The result will be a long JSON response detailing the solution, complete with Google Maps directions:
{ "routes" : [ { "bounds" : { "northeast" : { "lat" : 33.8347115, "lng" : 140.8547058 }, "southwest" : { "lat" : 37.3511758, "lng" : 138.4951576 } }, "copyrights" : "Map data ©2014 Google", "legs" : [ { "distance" : { "text" : "139 km", "value" : 139119 }, "duration" : { "text" : "1 hour 51 mins", "value" : 6648 }, "end_address" : "Clare SA 5453, Australia", "end_location" : { "lat" : 33.8333395, "lng" : 138.6117283 }, "start_address" : "Adelaide SA, Australia", "start_location" : { "lat" : 34.9285894, "lng" : 138.5999429 }, "steps" : [ { "distance" : { "text" : "70 m", "value" : 70 }, "duration" : { "text" : "1 min", "value" : 6 }, "end_location" : { "lat" : 34.9285338, "lng" : 138.6007031 }, "html_instructions" : "Head \u003cb\u003eeast\u003c/b\u003e on \u003cb\u003eReconciliation Plaza\u003c/b\u003e toward \u003cb\u003eVictoria Square\u003c/b\u003e", ...
Solving TSPs with ORTools
No solver can find the shortest paths for all problems. Lots of work has gone into techniques for quickly finding nearoptimal solutions, and into proving bounds about how closely these techniques approach optimality.
With ORTools, you can solve TSPs using the constraint programming solver, together with the vehicle routing library, a collection of algorithms designed especially for TSPs and related routing problems. We next present an example that shows how to use ORTools to find the shortest route through the U.S. cities shown on the map below.
The following sections present a Python program that solves the TSP for these cities.
Create the data
The data for the problem is contained in an array, called the distance matrix, whose entry in row i and column j is the distance from city i to city j in miles. The array is shown below.
[[ 0, 2451, 713, 1018, 1631, 1374, 2408, 213, 2571, 875, 1420, 2145, 1972], # New York [2451, 0, 1745, 1524, 831, 1240, 959, 2596, 403, 1589, 1374, 357, 579], # Los Angeles [ 713, 1745, 0, 355, 920, 803, 1737, 851, 1858, 262, 940, 1453, 1260], # Chicago [1018, 1524, 355, 0, 700, 862, 1395, 1123, 1584, 466, 1056, 1280, 987], # Minneapolis [1631, 831, 920, 700, 0, 663, 1021, 1769, 949, 796, 879, 586, 371], # Denver [1374, 1240, 803, 862, 663, 0, 1681, 1551, 1765, 547, 225, 887, 999], # Dallas [2408, 959, 1737, 1395, 1021, 1681, 0, 2493, 678, 1724, 1891, 1114, 701], # Seattle [ 213, 2596, 851, 1123, 1769, 1551, 2493, 0, 2699, 1038, 1605, 2300, 2099], # Boston [2571, 403, 1858, 1584, 949, 1765, 678, 2699, 0, 1744, 1645, 653, 600], # San Francisco [ 875, 1589, 262, 466, 796, 547, 1724, 1038, 1744, 0, 679, 1272, 1162], # St. Louis [1420, 1374, 940, 1056, 879, 225, 1891, 1605, 1645, 679, 0, 1017, 1200], # Houston [2145, 357, 1453, 1280, 586, 887, 1114, 2300, 653, 1272, 1017, 0, 504], # Phoenix [1972, 579, 1260, 987, 371, 999, 701, 2099, 600, 1162, 1200, 504, 0]] # Salt Lake CityThe order of the cities in the array is the following:
city_names = ["New York", "Los Angeles", "Chicago", "Minneapolis", "Denver", "Dallas", "Seattle", "Boston", "San Francisco", "St. Louis", "Houston", "Phoenix", "Salt Lake City"]
The routing model solver
ORTools has a special solver for routing problems, called RoutingModel. For specific information about the methods available to the solver, see the RoutingModel reference page.
The following code declares an instance of the solver and sets some options for it.
# Cities city_names = ["New York", "Los Angeles", "Chicago", "Minneapolis", "Denver", "Dallas", "Seattle", "Boston", "San Francisco", "St. Louis", "Houston", "Phoenix", "Salt Lake City"] tsp_size = len(city_names) num_routes = 1 # The number of routes, which is 1 in the TSP. # Nodes are indexed from 0 to tsp_size  1. The depot is the starting node of the route. depot = 0 # Create routing model if tsp_size > 0: routing = pywrapcp.RoutingModel(tsp_size, num_routes, depot) search_parameters = pywrapcp.RoutingModel.DefaultSearchParameters() # Setting first solution heuristic: the # method for finding a first solution to the problem. search_parameters.first_solution_strategy = ( routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC) # Create the distance callback, which takes two arguments (the from and to node indices) # and returns the distance between these nodes. dist_between_nodes = CreateDistanceCallback() dist_callback = dist_between_nodes.Distance routing.SetArcCostEvaluatorOfAllVehicles(dist_callback)
The solver instance is declared by
routing = pywrapcp.RoutingModel(tsp_size, 1)The first argument (
tsp_size
) is the number of nodes in the graph. The
second is the number of routes allowed, which is 1 for
the classical Traveling Salesman Problem.
(Note that the ORTools solver also handles more general versions of the TSP, in which
multiple routes are allowed.)
Here's a brief summary of how the solver works. First, it creates an initial solution for
the problem — namely,
a route that visits all the nodes. There are several options for how the solver creates
the initial solution,
which you can specify by parameters.first_solution_strategy
. This example uses the
PATH_CHEAPEST_ARC
option.
After generating the initial solution, the solver iteratively modifies the route using local search methods, the goal of which is to improve small ("local") segments of the current route.
The last three lines in the code above call the method that creates the distance callback — a function that takes any pair of nodes in the graph for the problem and returns the distance between them — and then passes the callback to the solver.
Create the distance callback
The following code creates the distance callback.
class CreateDistanceCallback(object): """Create callback to calculate distances between points.""" def __init__(self): """Array of distances between points.""" self.matrix = [ [ 0, 2451, 713, 1018, 1631, 1374, 2408, 213, 2571, 875, 1420, 2145, 1972], # New York [2451, 0, 1745, 1524, 831, 1240, 959, 2596, 403, 1589, 1374, 357, 579], # Los Angeles [ 713, 1745, 0, 355, 920, 803, 1737, 851, 1858, 262, 940, 1453, 1260], # Chicago [1018, 1524, 355, 0, 700, 862, 1395, 1123, 1584, 466, 1056, 1280, 987], # Minneapolis [1631, 831, 920, 700, 0, 663, 1021, 1769, 949, 796, 879, 586, 371], # Denver [1374, 1240, 803, 862, 663, 0, 1681, 1551, 1765, 547, 225, 887, 999], # Dallas [2408, 959, 1737, 1395, 1021, 1681, 0, 2493, 678, 1724, 1891, 1114, 701], # Seattle [ 213, 2596, 851, 1123, 1769, 1551, 2493, 0, 2699, 1038, 1605, 2300, 2099], # Boston [2571, 403, 1858, 1584, 949, 1765, 678, 2699, 0, 1744, 1645, 653, 600], # San Francisco [ 875, 1589, 262, 466, 796, 547, 1724, 1038, 1744, 0, 679, 1272, 1162], # St. Louis [1420, 1374, 940, 1056, 879, 225, 1891, 1605, 1645, 679, 0, 1017, 1200], # Houston [2145, 357, 1453, 1280, 586, 887, 1114, 2300, 653, 1272, 1017, 0, 504], # Phoenix [1972, 579, 1260, 987, 371, 999, 701, 2099, 600, 1162, 1200, 504, 0]] # Salt Lake City def Distance(self, from_node, to_node): return self.matrix[from_node][to_node]
The callback is defined in a Python class called CreateDistanceCallback
. The first part
of the class defines the distance matrix (which you have already seen)
as self.matrix
. Then the callback is defined by the method Distance
,
which takes a pair of nodes (from_node
and to_node
) and returns the
corresponding entry of the distance matrix.
The solver section of the program sets the
distance callback to be the Distance
method in the CreateDistanceCallback
class.
dist_between_nodes = CreateDistanceCallback() dist_callback = dist_between_nodes.Distance
Finally, the program passes the callback to the solver:
routing.SetArcCostEvaluatorOfAllVehicles(dist_callback)Notice that the method that specifies the distance callback is named
SetArcCostEvaluatorOfAllVehicles
. In this case, there is just one vehicle for
the single salesman. But in more general routing problems, there can be multiple vehicles, and
each node
must be visited by one of them. In general, the function to be
minimized is the total cost of all the routes. In this example, we are assuming that
there is just one route, and the cost of each arc is proportional to its
distance — so the minimum cost route is the same as the minimum distance route.
Invoke the solver and display the results
The following code invokes the solver (named routing
) and displays the results.
# Solve, returns a solution if any. assignment = routing.SolveWithParameters(search_parameters) if assignment: # Solution cost. print "Total distance: " + str(assignment.ObjectiveValue()) + " miles\n" # Inspect solution. # Only one route here; otherwise iterate from 0 to routing.vehicles()  1 route_number = 0 index = routing.Start(route_number) # Index of the variable for the starting node. route = '' while not routing.IsEnd(index): # Convert variable indices to node indices in the displayed route. route += str(city_names[routing.IndexToNode(index)]) + ' > ' index = assignment.Value(routing.NextVar(index)) route += str(city_names[routing.IndexToNode(index)]) print "Route:\n\n" + route else: print 'No solution found.' else: print 'Specify an instance greater than 0.'
Displaying the route in the output
To display the route in the output, we first get the starting index of the route.
index = routing.Start(route_number)
index
is the index of the variable that represents the starting
node of the route, called the depot. The index of a node variable is not always the same
as the index of the node itself (its row number in the locations array).
So, when we add nodes to
the route displayed in the output, we convert the indices of node variable to node indices,
using the method routing.IndexToNode()
:
route += str(city_names[routing.IndexToNode(index)]) + ' > '
The program iterates through the nodes of the route by
index = assignment.Value(routing.NextVar(index))which takes an index for a node variable and returns the index for the next node variable in the route.
Here is the output of the program.
A depot must be specified, setting one at node 0 Total distance: 7293 miles Route: New York > Boston > Chicago > Minneapolis > Denver > Salt Lake City > Seattle > San Francisco > Los Angeles > Phoenix > Houston > Dallas > St. Louis > New YorkThe output gives the route and its total distance, 7293 miles. (The depot is the starting and ending point for the tour. Since we don't care where the depot is, ORTools uses the first location.)
The entire program
The entire program is shown below.
from ortools.constraint_solver import pywrapcp from ortools.constraint_solver import routing_enums_pb2 # Distance callback class CreateDistanceCallback(object): """Create callback to calculate distances between points.""" def __init__(self): """Array of distances between points.""" self.matrix = [ [ 0, 2451, 713, 1018, 1631, 1374, 2408, 213, 2571, 875, 1420, 2145, 1972], # New York [2451, 0, 1745, 1524, 831, 1240, 959, 2596, 403, 1589, 1374, 357, 579], # Los Angeles [ 713, 1745, 0, 355, 920, 803, 1737, 851, 1858, 262, 940, 1453, 1260], # Chicago [1018, 1524, 355, 0, 700, 862, 1395, 1123, 1584, 466, 1056, 1280, 987], # Minneapolis [1631, 831, 920, 700, 0, 663, 1021, 1769, 949, 796, 879, 586, 371], # Denver [1374, 1240, 803, 862, 663, 0, 1681, 1551, 1765, 547, 225, 887, 999], # Dallas [2408, 959, 1737, 1395, 1021, 1681, 0, 2493, 678, 1724, 1891, 1114, 701], # Seattle [ 213, 2596, 851, 1123, 1769, 1551, 2493, 0, 2699, 1038, 1605, 2300, 2099], # Boston [2571, 403, 1858, 1584, 949, 1765, 678, 2699, 0, 1744, 1645, 653, 600], # San Francisco [ 875, 1589, 262, 466, 796, 547, 1724, 1038, 1744, 0, 679, 1272, 1162], # St. Louis [1420, 1374, 940, 1056, 879, 225, 1891, 1605, 1645, 679, 0, 1017, 1200], # Houston [2145, 357, 1453, 1280, 586, 887, 1114, 2300, 653, 1272, 1017, 0, 504], # Phoenix [1972, 579, 1260, 987, 371, 999, 701, 2099, 600, 1162, 1200, 504, 0]] # Salt Lake City def Distance(self, from_node, to_node): return self.matrix[from_node][to_node] def main(): # Cities city_names = ["New York", "Los Angeles", "Chicago", "Minneapolis", "Denver", "Dallas", "Seattle", "Boston", "San Francisco", "St. Louis", "Houston", "Phoenix", "Salt Lake City"] tsp_size = len(city_names) num_routes = 1 # The number of routes, which is 1 in the TSP. # Nodes are indexed from 0 to tsp_size  1. The depot is the starting node of the route. depot = 0 # Create routing model if tsp_size > 0: routing = pywrapcp.RoutingModel(tsp_size, num_routes, depot) search_parameters = pywrapcp.RoutingModel.DefaultSearchParameters() # Setting first solution heuristic: the # method for finding a first solution to the problem. search_parameters.first_solution_strategy = ( routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC) # Create the distance callback, which takes two arguments (the from and to node indices) # and returns the distance between these nodes. dist_between_nodes = CreateDistanceCallback() dist_callback = dist_between_nodes.Distance routing.SetArcCostEvaluatorOfAllVehicles(dist_callback) # Solve, returns a solution if any. assignment = routing.SolveWithParameters(search_parameters) if assignment: # Solution cost. print "Total distance: " + str(assignment.ObjectiveValue()) + " miles\n" # Inspect solution. # Only one route here; otherwise iterate from 0 to routing.vehicles()  1 route_number = 0 index = routing.Start(route_number) # Index of the variable for the starting node. route = '' while not routing.IsEnd(index): # Convert variable indices to node indices in the displayed route. route += str(city_names[routing.IndexToNode(index)]) + ' > ' index = assignment.Value(routing.NextVar(index)) route += str(city_names[routing.IndexToNode(index)]) print "Route:\n\n" + route else: print 'No solution found.' else: print 'Specify an instance greater than 0.' if __name__ == '__main__': main()
Add a distance function
In the previous example, we defined the distance callback by explicitly writing down the distances between cities in a matrix. An alternative method is to use a function that calculates the distance between any two nodes in the graph. If the nodes are geographical locations, there is such a function, which calculates the distance between any two points on Earth using their latitudes and longitudes.
The advantage of this approach is that if you want to add a location to the network, you don't need to rewrite the entire distance matrix — you simply add the latitude and longitude of the new location. The next example illustrates this.
The distance function
The function that calculates the distance between locations is based on the Haversine formula, which navigators have used since the 1800s to calculate distances at sea. The function is shown below.
def distance(lat1, long1, lat2, long2): # Note: The formula used in this function is not exact, as it assumes # the Earth is a perfect sphere. # Mean radius of Earth in miles radius_earth = 3959 # Convert latitude and longitude to # spherical coordinates in radians. degrees_to_radians = math.pi/180.0 phi1 = lat1 * degrees_to_radians phi2 = lat2 * degrees_to_radians lambda1 = long1 * degrees_to_radians lambda2 = long2 * degrees_to_radians dphi = phi2  phi1 dlambda = lambda2  lambda1 a = haversine(dphi) + math.cos(phi1) * math.cos(phi2) * haversine(dlambda) c = 2 * math.atan2(math.sqrt(a), math.sqrt(1a)) d = radius_earth * c return d def haversine(angle): h = math.sin(angle / 2) ** 2 return h
Create the distance callback
As in the previous example, the distance callback is created in a class called
CreateDistanceCallback
, shown below.
# Distance callback class CreateDistanceCallback(object): """Create callback to calculate distances between points.""" def __init__(self): # Latitudes and longitudes of selected U.S. cities locations = [[40.71, 74.01], # New York [34.05, 118.24], # Los Angeles [41.88, 87.63], # Chicago [44.98, 93.27], # Minneapolis [39.74, 104.99], # Denver [32.78, 96.89], # Dallas [47.61, 122.33], # Seattle [42.36, 71.06], # Boston [37.77, 122.42], # San Francisco [38.63, 90.20], # St. Louis [29.76, 95.37], # Houston [33.45, 112.07], # Phoenix [40.76, 111.89]] # Salt Lake City """Create the distance matrix.""" size = len(locations) self.matrix = {} for from_node in xrange(size): self.matrix[from_node] = {} for to_node in xrange(size): if from_node == to_node: self.matrix[from_node][to_node] = 0 else: x1 = locations[from_node][0] y1 = locations[from_node][1] x2 = locations[to_node][0] y2 = locations[to_node][1] self.matrix[from_node][to_node] = distance(x1, y1, x2, y2) def Distance(self, from_node, to_node): return self.matrix[from_node][to_node]
First, the program defines an array, locations
, containing the latitudes and
longitudes of the cities in the
problem. Next, it creates the distance matrix, which is once again called self.matrix
.
But in this case, the
entries of the matrix are calculated one by one in a loop. For each pair of cities in the graph,
the program calculates the distance between them using the function
distance
, and assigns the result to
the corresponding entry in the matrix.
Once all the distances are computed, the distance callback is defined just as in the previous example.
Here's the output of the Python code:
Total distance: 7198 miles Route: New York > Boston > Chicago > Minneapolis > Denver > Salt Lake City > Seattle > San Francisco > Los Angeles > Phoenix > Dallas > Houston > St. Louis > New York
We should mention that the function distance
is not exact, because it assumes
that the Earth is a perfect sphere, while in
reality it is wider at the equator than at the poles. This partly accounts for the slightly
different values for the total distance of the route in the two examples. However, the route
returned in both cases is the same.
To add a city to the problem in this example, you simply add its latitude and longitude to the
array locations
. If you hard coded the distances between cities, as
in the previous example, you would need to add a row and column
to the distance matrix, corresponding to the new city.
A drilling problem
The next example is one of the problems in the TSPLIB collection: a280, a set of 280 abstract locations taken from a reallife problem of drilling holes in a circuit board with an automated drill. The problem is to find the shortest route for the drill to take on the board in order to drill all of the required holes .
Here's a Google Scatter Chart of the locations in a280:
The program that finds a solution for this TSP is very similar to the one for the preceding example. But instead of computing the distances between cities, in this case the distance callback calculates distances between points on the circuit board using the standard Euclidean distance.
The program hard codes the data for the TSP as a set of points in the plane. (Ideally, there would be a parser for TSPLIB problems.) Under the hood, the ORTools routing library is written in C++, but it can be used from multiple languages:
 C++: https://github.com/google/ortools/blob/master/examples/cpp/tsp.cc
 Python: https://github.com/google/ortools/blob/master/examples/python/tsp.py
 Java: https://github.com/google/ortools/blob/master/examples/com/google/ortools/samples/Tsp.java
 C#: https://github.com/google/ortools/blob/master/examples/csharp/cstsp.cs
Create the data
The data for the problem consists of 280 points in the plane, shown in the scatter chart above. The program creates a Python array that contains the data. The first few entries of the array are shown below.
def create_data(): locations = [[288, 149], [288, 129], [270, 133], [256, 141], [256, 157], [246, 157], ...
Note that since the data set is fairly large, we have chosen to write a separate function to create the data array.
Create the distance callback
The class that creates the distance callback is the same as in the previous example, except that it calls the Euclidean distance function, instead of a function that calculates distances on Earth. The code is shown below.def distance(x1, y1, x2, y2): dist = math.sqrt((x1  x2)**2 + (y1  y2)**2) return dist # Distance callback class CreateDistanceCallback(object): """Create callback to calculate distances between points.""" def __init__(self): """Initialize distance array.""" locations = create_data_array() size = len(locations) self.matrix = {} for from_node in xrange(size): self.matrix[from_node] = {} for to_node in xrange(size): if from_node == to_node: self.matrix[from_node][to_node] = 0 else: x1 = locations[from_node][0] y1 = locations[from_node][1] x2 = locations[to_node][0] y2 = locations[to_node][1] self.matrix[from_node][to_node] = distance(x1, y1, x2, y2) def Distance(self, from_node, to_node): return self.matrix[from_node][to_node]
The function distance
calculates the Euclidean distance between any two points
(x1, y1) and (x2, y2) in the plane.
Output of the program
Here is the output of the program.
Total distance: 2790 Route: 0 > 1 > 279 > 2 > 278 > 277 > 247 > 248 > 249 > 246 > 244 > 243 > 242 > 241 > 240 > 239 > 238 > 237 > 236 > 235 > 234 > 233 > 232 > 231 > 230 > 245 > 250 > 229 > 228 > 227 > 226 > 225 > 224 > 223 > 222 > 221 > 220 > 219 > 218 > 217 > 216 > 215 > 214 > 213 > 212 > 211 > 210 > 209 > 208 > 251 > 254 > 255 > 257 > 256 > 253 > 252 > 207 > 206 > 205 > 204 > 203 > 202 > 142 > 141 > 146 > 147 > 140 > 139 > 265 > 136 > 137 > 138 > 148 > 149 > 177 > 176 > 175 > 178 > 179 > 180 > 181 > 182 > 183 > 184 > 186 > 185 > 192 > 196 > 197 > 198 > 144 > 145 > 143 > 199 > 201 > 200 > 195 > 194 > 193 > 191 > 190 > 189 > 188 > 187 > 163 > 164 > 165 > 166 > 167 > 168 > 169 > 171 > 170 > 172 > 105 > 106 > 104 > 103 > 107 > 109 > 110 > 113 > 114 > 116 > 117 > 61 > 62 > 63 > 65 > 64 > 84 > 85 > 115 > 112 > 86 > 83 > 82 > 87 > 111 > 108 > 89 > 90 > 91 > 102 > 101 > 100 > 99 > 98 > 97 > 96 > 95 > 94 > 93 > 92 > 79 > 88 > 81 > 80 > 78 > 77 > 76 > 74 > 75 > 73 > 72 > 71 > 70 > 69 > 66 > 68 > 67 > 57 > 56 > 55 > 54 > 53 > 52 > 51 > 50 > 49 > 48 > 47 > 46 > 45 > 44 > 43 > 58 > 60 > 59 > 42 > 41 > 40 > 39 > 38 > 37 > 36 > 35 > 34 > 33 > 32 > 31 > 30 > 29 > 124 > 123 > 122 > 121 > 120 > 119 > 118 > 156 > 157 > 158 > 173 > 162 > 161 > 160 > 174 > 159 > 150 > 151 > 155 > 152 > 154 > 153 > 128 > 129 > 130 > 131 > 18 > 19 > 20 > 127 > 126 > 125 > 28 > 27 > 26 > 25 > 21 > 24 > 22 > 23 > 13 > 12 > 14 > 11 > 10 > 9 > 7 > 8 > 6 > 5 > 275 > 274 > 273 > 272 > 271 > 270 > 15 > 16 > 17 > 132 > 133 > 269 > 268 > 134 > 135 > 267 > 266 > 264 > 263 > 262 > 261 > 260 > 258 > 259 > 276 > 3 > 4 > 0
Here is a graph of the resulting tour:
The ORTools library finds the above tour very quickly: in less than a second on a typical computer. The total length of the above tour is 2790.
Note: In the examples on TSPLIB, the distance between two nodes is calculated using a standard Euclidean 2D distance metric, but with each distance rounded to the nearest integer. Since the distance function in the Python program described above does not round to the nearest integer, its results will differ slightly from the results posted on TSPLIB
Improve the search
The solution shown above is not the optimal solution. One way to find the optimal solution is to use a search parameter called guided local search, which enables the solver to escape a local minimum — a solution that is shorter than all nearby routes, but which is not the global minumum.
To set a guided local search, add the following lines to the main section of the program:
search_parameters.local_search_metaheuristic = ( routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH) search_parameters.time_limit_ms = 400000The first line activates guided local search. The second sets a time limit on the search of 400,000 millseconds (400 seconds). If you don't set a time limit, the search will continue indefinitely. When you run the program after making these changes, you get the following solution, which is optimal.
Total distance: 2577 Route: 0 > 279 > 2 > 278 > 277 > 247 > 248 > 255 > 254 > 253 > 256 > 257 > 258 > 259 > 260 > 261 > 262 > 263 > 264 > 265 > 139 > 138 > 137 > 136 > 266 > 267 > 135 > 134 > 268 > 269 > 133 > 132 > 17 > 16 > 15 > 270 > 271 > 272 > 273 > 274 > 275 > 276 > 3 > 4 > 5 > 6 > 8 > 7 > 9 > 10 > 11 > 14 > 12 > 13 > 23 > 22 > 24 > 21 > 25 > 26 > 27 > 28 > 125 > 126 > 127 > 20 > 19 > 18 > 131 > 130 > 129 > 128 > 153 > 154 > 152 > 155 > 151 > 150 > 177 > 176 > 175 > 159 > 158 > 157 > 156 > 118 > 119 > 120 > 121 > 122 > 123 > 124 > 29 > 30 > 31 > 32 > 33 > 34 > 35 > 36 > 37 > 38 > 39 > 40 > 41 > 42 > 59 > 60 > 61 > 117 > 116 > 114 > 113 > 112 > 115 > 85 > 86 > 83 > 84 > 65 > 64 > 63 > 62 > 58 > 43 > 44 > 45 > 46 > 47 > 48 > 49 > 50 > 51 > 52 > 53 > 54 > 55 > 56 > 57 > 67 > 68 > 66 > 69 > 70 > 71 > 72 > 73 > 75 > 74 > 76 > 77 > 78 > 79 > 80 > 81 > 82 > 87 > 111 > 110 > 109 > 107 > 108 > 88 > 89 > 90 > 91 > 92 > 93 > 94 > 95 > 96 > 97 > 98 > 99 > 167 > 166 > 165 > 171 > 170 > 169 > 168 > 100 > 101 > 102 > 103 > 104 > 106 > 105 > 172 > 173 > 174 > 160 > 161 > 162 > 163 > 164 > 187 > 188 > 189 > 185 > 186 > 184 > 183 > 182 > 181 > 180 > 179 > 178 > 149 > 148 > 147 > 140 > 141 > 146 > 145 > 142 > 143 > 144 > 198 > 197 > 196 > 192 > 190 > 191 > 193 > 194 > 195 > 200 > 199 > 201 > 202 > 203 > 204 > 205 > 207 > 252 > 251 > 208 > 209 > 206 > 211 > 210 > 213 > 212 > 215 > 214 > 217 > 216 > 219 > 220 > 221 > 218 > 222 > 223 > 224 > 225 > 226 > 227 > 228 > 229 > 250 > 249 > 246 > 244 > 245 > 230 > 231 > 232 > 233 > 234 > 235 > 236 > 237 > 238 > 239 > 240 > 243 > 242 > 241 > 1 > 0
The best algorithms can now routinely solve TSP instances with tens of thousands of nodes. (The record at the time of writing is the pla85900 instance in TSPLIB, a VLSI application with 85,900 nodes. For certain instances with millions of nodes, solutions have been found guaranteed to be within 1% of an optimal tour.)
Routing options
Many of these options are available only from C++.
Neighborhood deactivation
Name  Type  Default  Description 

routing_no_lns  bool  false  Forbids use of Large Neighborhood Search. 
routing_no_fullpathlns  bool  true  Forbids use of Fullpath Large Neighborhood Search. 
routing_no_relocate  bool  false  Forbids use of Relocate neighborhood. 
routing_no_relocate_neighbors  bool  true  Forbids use of RelocateNeighbors neighborhood. 
routing_no_exchange  bool  false  Forbids use of Exchange neighborhood. 
routing_no_cross  bool  false  Forbids use of Cross neighborhood. 
routing_no_2opt  bool  false  Forbids use of 2Opt neighborhood. 
routing_no_oropt  bool  false  Forbids use of OrOpt neighborhood. 
routing_no_make_active  bool  false  Forbids use of MakeActive/SwapActive/MakeInactive neighborhoods. 
routing_no_lkh  bool  false  Forbids use of LKH neighborhood. 
routing_no_tsp  bool  true  Forbids use of TSPOpt neighborhood. 
routing_no_tsplns  bool  true  Forbids use of TSPLNS neighborhood. 
routing_use_chain_make_inactive  bool  false  Use chain version of MakeInactive neighborhood. 
routing_use_extended_swap_active  bool  false  Use extended version of SwapActive neighborhood. 
Search limits
Name  Type  Default  Description 

routing_solution_limit  int64  kint64max  Number of solutions limit. 
routing_time_limit  int64  kint64max  Time limit, in milliseconds. 
routing_lns_time_limit  int64  100  Time limit in ms for LNS subdecisionbuilder. 
Metaheuristics
Name  Type  Default  Description 

routing_guided_local_search  bool  false  Use guided local search. 
routing_guided_local_search_lambda_coefficient  double  0.1  Lambda coefficient for guided local search. 
routing_simulated_annealing  bool  false  Use simulated annealing. 
routing_tabu_search  bool  false  Use tabu search. 
Search control
Name  Type  Default  Description 

routing_first_solution  string  First solution heuristic. See RoutingStrategyName() in routing.cc to get a full list. 

routing_optimization_step  int64  1  Optimization step. 
First solution heuristics
Name  Type  Default  Description 

savings_route_shape_parameter  double  1.0  Coefficient of the added arc in the savings definition. Varying this parameter may provide heuristic solutions which are closer to the optimal solution than otherwise obtained via the traditional algorithm where it is equal to 1. 
savings_filter_neighbors  int64  0  Limit the number of neighbors considered for each node in the savings first solution heuristic. 
savings_filter_radius  int64  0  Limit the distance up to which a neighbor is considered for each node in the savings first solution heuristic. 
sweep_sectors  int64  1  The number of sectors the space is divided before it is sweeped by the ray. 
Propagation control
Name  Type  Default  Description 

routing_use_light_propagation  bool  true  Use Constraints with light propagation in routing model. 
Other options
Name  Type  Default  Description 

routing_cache_callbacks  bool  false  Cache callback calls. 
routing_max_cache_size  int64  1000  Maximum cache size when callback caching is on. 
routing_trace  bool  false  Trace search. 
routing_search_trace  bool  false  Use SearchTrace for monitoring search. 