Travelling Salesman Problem (TSP) Example

Download Notebook

The Travelling Salesman Problem (TSP) asks for the shortest round-trip through a set of cities, visiting each exactly once and returning to the start. It is NP-hard.

import getpass
import os

import matplotlib.pyplot as plt
import numpy as np
from dotenv import load_dotenv
from luna_quantum.algorithms import SCIP

from luna_usecases.traveling_salesman_problem import TspCircleCollection, TspData, TspFormulation, TspInstance

load_dotenv()
if "LUNA_API_KEY" not in os.environ:
    os.environ["LUNA_API_KEY"] = getpass.getpass("Enter your Luna API key: ")

Create Data

Define distances between 4 German cities as a symmetric distance matrix.

dist_matrix = np.array(
    [
        [0.0, 58.00553679823033, 152.52000388133354, 248.84855373209675],
        [58.00553679823033, 0.0, 190.1970628748754, 212.16684065507212],
        [152.52000388133354, 190.1970628748754, 0.0, 261.6296330832349],
        [248.84855373209675, 212.16684065507212, 261.6296330832349, 0.0],
    ]
)
city_names = ["Cologne", "Essen", "Frankfurt", "Hanover"]

data = TspData.from_distance_matrix(
    distance_matrix=dist_matrix,
    city_names=city_names,
    start_city=city_names[0],
)
print(data.to_string())

Travelling Salesman Data:
  Cities: 4
  City names: ['Cologne', 'Essen', 'Frankfurt', 'Hanover']
  Start city: Cologne
  Distance matrix shape: (4, 4)

Plot Data

Visualize the cities and their connections as a NetworkX graph.

ax = data.plot()
plt.show()

png

Create Formulation

Set up binary decision variables assigning each city to a position in the tour.

formulation = TspFormulation()
print(formulation.to_string(data))

Travelling Salesman Problem Formulation:
  Cities: 4
  Start city: Cologne

Decision Variables:
  x[i,p] in {0,1} for i = 0, ..., 3, p = 0, ..., 3
  x[i,p] = 1 if city i is at position p in the tour
  Total: 16 binary variables

Objective:
  minimize sum_{i,j,p} d[i,j] * x[i,p] * x[j,(p+1) mod 4]  for i != j

Constraints:
  1. Each city at exactly one position (4 constraints):
     sum_p x[i,p] == 1  for all i = 0, ..., 3
  2. Each position has exactly one city (4 constraints):
     sum_i x[i,p] == 1  for all p = 0, ..., 3

Create Instance

Combine data and formulation into a solvable instance.

instance = TspInstance(data=data, formulation=formulation)
print(instance.to_string())

Data:Travelling Salesman Data:
  Cities: 4
  City names: ['Cologne', 'Essen', 'Frankfurt', 'Hanover']
  Start city: Cologne
  Distance matrix shape: (4, 4)
Formulation:Travelling Salesman Problem Formulation:
  Cities: 4
  Start city: Cologne

Decision Variables:
  x[i,p] in {0,1} for i = 0, ..., 3, p = 0, ..., 3
  x[i,p] = 1 if city i is at position p in the tour
  Total: 16 binary variables

Objective:
  minimize sum_{i,j,p} d[i,j] * x[i,p] * x[j,(p+1) mod 4]  for i != j

Constraints:
  1. Each city at exactly one position (4 constraints):
     sum_p x[i,p] == 1  for all i = 0, ..., 3
  2. Each position has exactly one city (4 constraints):
     sum_i x[i,p] == 1  for all p = 0, ..., 3

Formulate Model

Translate the instance into a mathematical optimization model.

model = instance.formulate()

Solve and Interpret

Solve the model with SCIP and interpret the raw result into a use-case-specific solution.

scip = SCIP()
job = scip.run(model)
sol = job.result()
uc_solution = instance.interpret(sol)
print(uc_solution.to_string())

/Users/maximilianjanetschek/PycharmProjects/luna-usecases/.venv/lib/python3.13/site-packages/rich/live.py:260:
UserWarning: install "ipywidgets" for Jupyter support
  warnings.warn('install "ipywidgets" for Jupyter support')

Travelling Salesman Solution:
  Tour: Cologne -> Essen -> Hanover -> Frankfurt -> Cologne
  Total distance: 684.32
  Valid: True

Plot Solution

Visualize the optimal solution.

ax = uc_solution.plot(data)
plt.show()

png

Collections

Generate a benchmark collection of random instances for batch processing.

collection = TspCircleCollection.generate(min_num_cities=2, max_num_cities=8, radius=1)
model = collection.instances[0].formulate()
print(model)

Model: traveling_salesman_problem<traveling_salesman_problem>
Minimize
  4 * x_City_2_0_0_0 * x_City_2_0_1_1 + 4 * x_City_2_0_0_1 * x_City_2_0_1_0
Subject To
  city_one_position_0: x_City_2_0_0_0 + x_City_2_0_0_1 == 1
  city_one_position_1: x_City_2_0_1_0 + x_City_2_0_1_1 == 1
  position_one_city_0: x_City_2_0_0_0 + x_City_2_0_1_0 == 1
  position_one_city_1: x_City_2_0_0_1 + x_City_2_0_1_1 == 1
Binary
  x_City_2_0_0_0 x_City_2_0_0_1 x_City_2_0_1_0 x_City_2_0_1_1