Solving the Travelling Salesman Problem with Python and Google tools

Travelling salesman for German cities (source Wikipedia)

Introduction

The Travelling Salesman Problem (TSP, or travelling salesperson problem) is one of the most common problems in the area of operations research. The problem can be defined as follows:

”Given a list of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?

Symmetric TSP with four cities (source: Wikipedia)

In the above image, we see a simple definition of the TSP with 4 cities (A,B,C,D). Assuming the salesperson has to start from and return to city A, which is the optimal sequence of visiting cities B,C,D?

If you hear this problem for the first time, it might intuitively sound easy to solve and in case of 4 cities it really is. However, it can become complex and computationally intensive very quickly. The TSP is defined as an NP-hard problem.

How the problem scales: Assuming the salesperson has to visit 5 cities, the total combination of visit sequences that need to be calculated, are 4! (4*3*2*1) = 24. For 10 cities, the number of combination is 9! (9*8*7*6*5*4*3*2*1) = 362,880 and for 20 cities it is 19! = 1.216451e+17.

Hands-on: Solving the TSP

We will use python and Google tools to define mathematically and solve the TSP. We will combine following tools in one python class:

• Google Distance Matrix API:
  This is an API that returns a matrix with the distances between 2 or more locations. It can return the distance matrix for different modes of travelling and other preferences.
• Google OR-Tools:
  This is an open source software suite for optimization, which offers algorithms to solve various difficult problems in the area of Operations Research. Some examples are the travelling salesman problem, vehicle routing problem, knapsack problem, and job-shop scheduling.
  The OR-Tools from google can “hide” the complexity of the algorithmic solving of these problems and allow us to work on the mathematical modelling.

By combining these two tools we are able to:

1. Define a list of cities or locations where the sales person must travel
2. Get the distance matrix between those locations by the google distance API
3. Get the best route from the TSP-Solver of the google OR-tools

Disclaimer:

• I have used most of the code from the google documentation of how to get started with these tools.
• If you want to test this yourself, you would need a Google Cloud Platform (GCP) account to get an API Key. You can start a free trial with 300$ credit for testing. Be aware that a credit/debit card is required, so be careful to not spin up some infrastructure that might cost you your full budget or more.
• Be aware that every API-call to Google distance matrix API costs a very small amount on Google Cloud Platform, but the budget should be more than enough for small use cases.

I decided to create a class that allows me to define and solve this problem in a modular way. For this I require following functionality:

1. Define list of cities (Python class)
2. Get the distance matrix between the cities (Google API)
3. Get the optimal route, given a list of cities and its distance matrix (Google OR-Tools)

Steps to define and solve the TSP with python

The main class I have created to execute the above steps can be seen below. This class uses submodules for the distance matrix and OR-Tools. You can find the complete code in my repository:

from or_tools.travelling_salesman_problem import optimize_routes
from distance_api.distance_matrix import create_distance_matrix
from constants import api_key

class RoutingOptimizer:
    def __init__(self,addresses = [],depot= 0, api_key = api_key):
        self.addresses = addresses
        self.depot = depot
        self.api_key = api_key
        self.distance_matrix = None

    def add_address(self,address):
        self.addresses.append(address)

    def remove_address(self,address):
        self.addresses.remove(address)

    def create_distance_matrix(self):
            self.distance_matrix = create_distance_matrix(self.addresses, self.api_key)

    def optimize_routes_tsp(self,):
        results = optimize_routes(self.distance_matrix, self.depot)
        return results

Finally, over the command line I am using this class as follows:

Using the Class on the command line to solve the TSP

Finally, by using the library Bokeh (which uses Google Maps) we are able to visualize all of the address points on a map. I have created a method create_map as part of the main class, that uses this library.
As a next step it would be interesting to visualize the routes as a graph on this map.

Map created using Bokeh, showing all the addresses (cities) that need to be visited

Conclusion

This was a simple version of solving the TSP that can be extended in many ways. We could extend the class for following challenges:

• Add constraints and different modes of transport
• Calculate the benefit of using this vs. not
• Extend this class to other problems like the Vehicle Routing Problem
• Improve the map to show more information on the solution (e.g. sequence, network graph, etc.)
• …

Feel free to reach out and connect if you are interested in this or similar topics! :)

Sources

• https://developers.google.com/maps/documentation/distance-matrix/overview
• https://developers.google.com/optimization
• https://github.com/google/or-tools
• https://github.com/amarinos/operations_research
• https://docs.bokeh.org/en/test/docs/user_guide/geo.html