Solving the Travelling Salesman Problem (TSP) with Python

In this tutorial, we would see how to solve the TSP problem in Python. The following sections are covered.

1. Approach to Solving the TSP Problem
2. The Routing Model and Index Manager
3. The Distance Callback
4. Travel Cost and Search Parameters
5. Function to the Print the Solution
6. Putting it all Together

1. Approach to Solving the TSP Problem

To be able to solve a TSP problem in Python, we need the following items:

• List of cities
• List of distances between the cities
• Number of vehicles
• Starting location of the vehicles

List of Cities

In this problem we have a list of 12 cities. They are listed below. The indices of the cities are provided against the name.

0. New York – 1. Los Angeles – 2. Chicago – 3. Minneapolis – 4. Denver – 5. Dallas – 6. Seattle – 7. Boston – 8. San Francisco – 9. St. Louis – 10. Houston – 11. Phoenix – 12. Salt Lake City

List of Distances

It is normally better to represent the list of distances as a square matrix with intersecting cells holding distance between the row and column headers. If we use indexes i and j for this matrix, then data[i][j] is the distance between city i and city j.

data['distance_matrix'] = [
    [0, 2451, 713, 1018, 1631, 1374, 2408, 213, 2571, 875, 1420, 2145, 1972],
    [2451, 0, 1745, 1524, 831, 1240, 959, 2596, 403, 1589, 1374, 357, 579],
    [713, 1745, 0, 355, 920, 803, 1737, 851, 1858, 262, 940, 1453, 1260],
    [1018, 1524, 355, 0, 700, 862, 1395, 1123, 1584, 466, 1056, 1280, 987],
    [1631, 831, 920, 700, 0, 663, 1021, 1769, 949, 796, 879, 586, 371],
    [1374, 1240, 803, 862, 663, 0, 1681, 1551, 1765, 547, 225, 887, 999],
    [2408, 959, 1737, 1395, 1021, 1681, 0, 2493, 678, 1724, 1891, 1114, 701],
    [213, 2596, 851, 1123, 1769, 1551, 2493, 0, 2699, 1038, 1605, 2300, 2099],
    [2571, 403, 1858, 1584, 949, 1765, 678, 2699, 0, 1744, 1645, 653, 600],
    [875, 1589, 262, 466, 796, 547, 1724, 1038, 1744, 0, 679, 1272, 1162],
    [1420, 1374, 940, 1056, 879, 225, 1891, 1605, 1645, 679, 0, 1017, 1200],
    [2145, 357, 1453, 1280, 586, 887, 1114, 2300, 653, 1272, 1017, 0, 504],
    [1972, 579, 1260, 987, 371, 999, 701, 2099, 600, 1162, 1200, 504, 0],
] 

Number of Vehicles

In this case, since it a TSP, the number of vehicles is 1. The Python code is

data['no_of_vehicles'] = 1

Starting Point

In this example, the starting point or ‘depot’ is location 0, that is New York.

data['depot'] = 0

2. The Routing Model and Index Manager

To solve the TSP in Python, you need to create the RoutingIndexManager and the RoutingModel. The RoutingIndexManager manages conversion between the internal solver variables and NodeIndexes. In this way, we can simply use the NodeIndex in our programs.

The RoutingIndexManager takes three parameters:

• number of location, including the depot (number of rows of the distance matrix
• number of vehicles
• the starting node (depot node)

The code below creates the  routing model and index manager

data = create_data_model() # call the create_data_model() function

manager = pywrapcp.RoutingIndexManager(
    len(data['distance_matrix']), 
    data['no_of_vehicles'],
    data['depot'])

routing = pywrapcp.RoutingModel(manager)

3. The Distance Callback

To be able to use the solver,  we need to create a distance callback. What is a distance callback? This is a function that takes two locations and returns the distance between them. Since these distances are available in the distance matrix, then we can use the distance matrix. The two functions passed to the distance callback are routing variable indexes, so we need to convert them to distance matrix NodeIndex using IndexToNode() method from the RoutingIndexManager.

The code below does that

# Gives the distance between two nodes
def distance_callback(from_index, to_index):
    
    # Convert routing variable Index to distance matrix NodeIndex.
    from_node = manager.IndexToNode(from_index)
    to_node = manager.IndexToNode(to_index)
    return data['distance_matrix'][from_node][to_node]

transit_callback_index = routing.RegisterTransitCallback(distance_callback)

4. The Travel Cost and Search Parameters

The cost of travel is the cost to travel the distance between two nodes. In the case of the solver, you need to set an arc cost evaluator function that does this calculation. This function takes as parameter the transit_callback_index returned by the distance_callback. In our case, the travel cost is simply the distance between the locations.

However, in a real world scenario, there may be other factors to be considered.

routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

We also need to set the search parameters as well as the heuristic for finding the first solution. In this case, the strategy is PATH_CHEAPEST_ARCH. This heuristic repeatedly adds edge with the least weight that don’t lead to a previously visited node..

search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.first_solution_strategy = (
    routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)

5. Function to Print the Solution

The function below prints out the solution to the screen by extracting the route from the solution

# Displays the solution to the output
def print_solution(manager, routing, solution):
    print('Objective: {} miles'.format(solution.ObjectiveValue()))
    index = routing.Start(0)
    
    plan_output = 'Best route found for vehicle 0:\n'
    route_distance = 0
    
    while not routing.IsEnd(index):
        plan_output += ' {} ->'.format(manager.IndexToNode(index))
        previous_index = index
        index = solution.Value(routing.NextVar(index))
        route_distance += routing.GetArcCostForVehicle(previous_index, index, 0)
    plan_output += ' {}\n'.format(manager.IndexToNode(index))
    
    print(plan_output)
    plan_output += 'Total distance for route: {}miles\n'.format(route_distance)

6. Putting it all together

Finally, call the SolveWithParameters() method of the routing model and then call the print_solution function.

# Call the SolveWithParameters() and print the solution
solution = routing.SolveWithParameters(search_parameters)
if solution:
    print_solution(manager, routing, solution)

The final output of the program is given below:

Objective: 6465 miles
Best route found for vehicle 0:
 0 -> 7 -> 2 -> 3 -> 9 -> 10 -> 5 -> 4 -> 12 -> 11 -> 1 -> 8 -> 6 -> 0