The QuBlog

The Traveling Salesperson Challenge

The traveling salesperson problem (also called the traveling salesman problem, abbreviated as TSP) is a well-known problem in combinatorial optimization. Given a list of travel destinations and distances between each pair of destinations, it tries to find the shortest route visiting each destination exactly once and returning to the origin. The Azure Quantum optimization sample gallery contains a sample for solving this problem. There, you pass in a cost matrix (describing a generic “travel cost” between pairs of travel points) and get back an ordered list of destinations. Imagine, you could use physical addresses as input, consider traveling times (including current traffic conditions), and ultimately get driving directions for your optimized route as a result. Integrating Azure Maps into the solution makes this possible. Learn how to implement an API via Azure Functions, that ultimately takes physical addresses and returns an ordered list of these travel destinations representing the optimum travel route.

The Solution

The solution architecture contains a Function App making the functionality accessible via API, an Azure Maps account used to retrieve geo-information about travel destinations, and an Azure Quantum workspace (with an associated Azure Storage account) providing access to optimization solvers doing the actual route optimization. The architecture can be illustrated as follows:

Architecture of the overall solution

The whole solution is accessible as a public GitHub repository: hsirtl/traveling-salesperson-qio-maps.

Azure Maps

TSP solutions often require you to pass in destinations via geo-coordinates and/or distances in miles/kilometers. It can be cumbersome to determine this information. Typically, you have a list of addresses and desire a web service to do the rest. This is exactly where Azure Maps comes into play. Azure Maps is a collection of geo-spatial services and SDKs that use fresh mapping data to provide geographic context to client applications. You can use a set APIs to work with addresses, places, and points of interest around the world, taking traffic flow into consideration and ultimately support visualization of data on maps.

For the TSP-solution, following Map services are relevant:

• Search Service - returning information to a given address (including latitude and longitude) via its GetSearchAddress-API.
• Route Service - returning information about distances between geo-locations via its GetRouteDirections-API.

Both these APIs used in sequence can be used to first get geo-locations to given addresses and then calculate a distance matrix containing distance information for each pair of destination points. The distance can either be expressed as physical distance (length in meters) or travel time (in seconds). In the sample solution on GitHub you’ll find all Azure Maps access methods in the mapsaccess.py-file.

def getCostMatrix(destinations, optCriterion):
    matrix = []
    for startLocation in destinations:
        costRow = []
        for endLocation in destinations:
            route = getRoute(startLocation.get('lat'), startLocation.get('lon'), endLocation.get('lat'), endLocation.get('lon'))
            lengthInMeters = route.get("routes")[0].get("summary").get("lengthInMeters")
            travelTimeInSeconds = route.get("routes")[0].get("summary").get("travelTimeInSeconds")
            if(optCriterion == "travelTimeInSeconds"):
                costRow.append(travelTimeInSeconds)
            elif(optCriterion == "lengthInMeters"):
                costRow.append(lengthInMeters)
        matrix.append(costRow)
    
    return matrix

Code for generating the cost matrix (distances between pairs of destination points).

Quantum Inspired Optimization (QIO) with Azure Quantum

Azure Quantum optimization solvers simulate certain quantum effects like tunneling on classical hardware. By exploiting some of the advantages of quantum computing on existing, classical hardware, they can provide a speedup over traditional approaches. For solving an optimization problem like TSP, you need to specify a cost function representing the quantity that you want to minimize (in our case: travel time or travel distance). So, you can summarize the challenge to be solved as follows:

• Quantity to be minimized: travel time or travel distance
• Constraints:
  • The salesperson can only be at one node at a time.
  • The salesperson must be at a node at any given time.
  • The salesperson must not visit a node a second time.
  • All destination points must be visited at some point in time.
  • The journey must start and end at one specific destination.

You’ll find the code for generating the cost function in the travelingsalesperson.py-file. It is derived from the traveling-salesperson-sample my esteemed colleague Frances Tibble created. So, lots of Kudos to Frances!

A serverless API via Azure Functions

The easiest way to make the overall solution accessible to non-quantum developers is via an API. Azure Functions have some tempting qualities that make them an ideal tool for this purpose:

• They are serverless, so you don’t need to worry about underlying infrastructure.
• The programming model is simple, so you can focus on the core functionality (calling Azure Maps and then Azure Quantum).
• Functions can be called via (authenticated) http-requests.

You’ll find the main implementation code for the function in the __init__.py-file. These are the most relevant lines of code calling Azure Maps and Azure Quantum for solving the TSP for a given set of travel destinations.

...
destinations = inputProblemData.get("destinations")
extDestinations = maps.addCoordinates(destinations)
costMatrix = maps.getCostMatrix(extDestinations, inputProblemCrit)

# Create cost function based on inputBlobData problem description
terms = travelingsalesperson.createCostFunction({ 'nodes': destinations, 'distances': costMatrix})

# configure the problem and submit it to an optimization solver
problem = Problem(name=inputProblemType, problem_type=ProblemType.pubo, terms=terms)
solver = SimulatedAnnealing(workspace, timeout=100, seed=22)
resultRawData = solver.optimize(problem)

nodes = inputProblemData.get('destinations')

# depending on the problem type extract business solution from job result
resultData = travelingsalesperson.extractSolution({ 'nodes': nodes, 'distances': costMatrix }, resultRawData)

solutionData = {}
solutionData["result"] = resultData
...

Function code calling Azure Maps and Azure Quantum to solve the TSP for a set of destinations.

Deployment of the solution

With several Azure services involved, a manual setup via the Azure portal would be too error-prone. The sample solution is equipped with an Azure Resource Manager (ARM) template representing ‘Infrastructure as Code’, i.e. a deployable specification of all Azure resources needed. The ARM template has following specifications:

• Input parameters
  • appName - used as a prefix for Azure resource names
  • location - datacenter regions the services should be deployed to
• Resources to be deployed
  • Azure Storage Account - needed by the Azure Quantum Workspace
  • Azure Quantum Workspace - providing access to optimization solvers
  • Azure Maps Account - geo-spacial services needed
  • Azure Function App - access point (API) for the functionality

A GitHub action executes the deployment. Its specification is stored in the CD-Full-Deployment.yml-file. If you fork the solution repository to your GitHub account, make sure to create a service principal with Contributor-rights on your Azure subscription and configure two Actions secrets:

• AZURE_CREDENTIALS with the output generated during the service principal creation.
• AZURE_SUBSCRIPTION with the Azure subscription ID.

After that, you can run the action (e.g., manually by using the workflow_dispatch event trigger), which executes following steps:

1. Log into Azure (using the AZURE_CREDENTIALS).
2. Create the resource group (its name specified via the AZURE_RESOURCE_GROUP_NAME-environment variable).
3. Deploy the infrastructure (specified in the azuredeploy.json ARM template).
4. Setup the Python environment
5. Install the Function App
6. Configure the credentials needed by the Azure Quantum workspace (specified in the azuredeploy.rbac.json) ARM template.

Solving Traveling Salesperson Challenges

After the GitHub workflow has successfully completed the setup, you can call the Function-API providing a list of addresses. You can call the Function via following URL:

https://<APP_NAME>.azurewebsites.net

URL you TSP-API is accessible under (APP_NAME specified in the GitHub action)

Make sure you provide that information in the body of the request. A sample workload could look as follows (containing the addresses of all Microsoft regional offices in Germany).

{
    "problem": {
        "type": "travelingsalesperson",
        "optimizeBy": "travelTimeInSeconds",
        "data": {
            "destinations": [
                "Walter-Gropius-Straße 5, 80807 München",
                "Meitnerstraße 9, 70563 Stuttgart",
                "Holzmarkt 2a, 50676 Köln",
                "Axel-Springer-Platz 3, 20355 Hamburg",
                "Friedrich-Ebert-Anlage 49, 60308 Frankfurt",
                "Unter den Linden 17, 10117 Berlin",
                "Altrottstraße 31, 69190 Walldorf"
            ]
        }
    } 
}

Request body to be passed via the Azure Function call.

After a few seconds, the function should return an ordered list of these destinations representing the optimal route. The result also provides the overall cost (travel distance or travel time) of that route. A sample output looks as follows:

{
  "result": {
    "Route": {
      "0": "Walter-Gropius-Straße 5, 80807 München",
      "1": "Meitnerstraße 9, 70563 Stuttgart",
      "2": "Altrottstraße 31, 69190 Walldorf",
      "3": "Friedrich-Ebert-Anlage 49, 60308 Frankfurt",
      "4": "Holzmarkt 2a, 50676 Köln",
      "5": "Axel-Springer-Platz 3, 20355 Hamburg",
      "6": "Unter den Linden 17, 10117 Berlin",
      "7": "Walter-Gropius-Straße 5, 80807 München"
    },
    "RouteCost": {
      "Cost": 62563.0
    }
  }
}

Response containing an ordered list of destinations and travel cost.

Conclusion

Azure Quantum is a great cloud quantum computing service, with a diverse set of quantum solutions and technologies. Its optimization solvers provide a speedup over traditional approaches in many optimization challenges, one of which is the Traveling Salesperson problem. Azure Maps can complement an optimization solution by providing geo-information to physical addresses, which is needed by existing optimization algorithms. By packaging the logic into Azure Functions, it is accessible via a Web-API. In this post, I showed you how, by utilizing these cloud services, you can solve traveling salesperson challenges with given physical addresses and by taking traffic conditions into account.