Skip to content

Traveling Salesman Problem (TSP) API Reference

Data

Data model for Tsp use case.

TspData

Bases: UcData

Data for the Traveling Salesman Problem (TSP) use case.

This class encapsulates all necessary information to define and solve a TSP instance. The TSP is a classic optimization problem where the goal is to find the shortest route that visits all cities exactly once and returns to the starting city.

Attributes:

  • name (Literal['traveling_salesman_problem']) –

    A constant identifier for this data type, always set to "traveling_salesman_problem". Used for registration and type identification in the use case registry.

  • city_names (list[str | int]) –

    A list of city identifiers (strings or integers) representing all cities in the problem instance. The order in this list corresponds to rows/columns in the distance_matrix. Example: ["New York", "Los Angeles", "Chicago"] or [0, 1, 2]

  • distance_matrix (SymMatrix) –

    A 2D NumPy array containing distances between all pairs of cities. The element at [i, j] represents the distance from city i to city j. For undirected TSP, this matrix is typically symmetric (distance[i,j] == distance[j,i]). Shape must be (n_cities, n_cities) where n_cities = len(city_names). Example: 3x3 matrix for 3 cities with distance values.

  • start_city (str) –

    The identifier of the starting city (must be one of city_names). The TSP route begins and ends at this city, returning after visiting all others. Example: "New York" if using string identifiers.

  • city_position ((dict[str, tuple[float, float]] | None, optional)) –

    Optional dictionary mapping each city identifier to its (x, y) coordinates in 2D space. Useful for:

    • Visualizing the TSP instance and its solution
    • Computing Euclidean distances when needed
    • Geographic or spatial analysis of the route

    If None, distances are purely abstract/given by distance_matrix. Example: {"New York": (40.7128, -74.0060), "Los Angeles": (34.0522, -118.2437)}

Examples:

Create a simple 3-city TSP instance:

>>> tsp = TspData(
...     name="traveling_salesman_problem",
...     city_names=["A", "B", "C"],
...     distance_matrix=np.array([[0, 10, 15], [10, 0, 20], [15, 20, 0]]),
...     start_city="A",
...     city_position={"A": (0.0, 0.0), "B": (10.0, 0.0), "C": (5.0, 8.66)},
... )

plot(*, ax: Axes | None = None) -> Axes

Plot the TSP city layout as a NetworkX graph.

Cities are drawn as nodes connected by edges weighted by their distance. When city_position is available the nodes are placed at their given coordinates; otherwise a spring layout is computed automatically. The start city is highlighted in a distinct colour.

Parameters:

  • ax (Axes | None, default: None ) –

    Matplotlib axes to draw on. Creates a new figure if None.

Returns:

  • Axes –

    The axes with the plot.

to_string() -> str

Return a string describing the TSP data.

from_graph(graph: nx.Graph, start_city: str) -> TspData staticmethod

Create TspData from a NetworkX graph.

from_distance_matrix(distance_matrix: np.ndarray, city_names: Sequence[str | int], start_city: str, city_position: dict[str, tuple[float, float]] | None = None) -> TspData staticmethod

Create TspData from a distance matrix.

Formulation

Formulation for Tsp use case.

TspFormulation

Bases: UcFormulation[TspData, TspSolution]

Formulation for the Tsp use case.

to_string(data: TspData) -> str staticmethod

Return a string describing the formulation.

formulate(data: TspData) -> Model staticmethod

Formulate the use case as a quantum optimization model.

interpret(solution: Solution, data: TspData) -> TspSolution staticmethod

Interpret the quantum solution.

Solution

Solution model for Tsp use case.

TspSolution

Bases: UcSolution

Solution for the Tsp use case.

plot(data: TspData | None = None, *, ax: Axes | None = None) -> Axes

Plot the TSP solution tour as a NetworkX graph.

All city-pairs are drawn as background edges; the tour is overlaid as directed (arrowed) edges. When data carries city_position the nodes are placed at their given coordinates; otherwise a spring layout is computed automatically.

Parameters:

  • data (TspData | None, default: None ) –

    Problem data. Required so that city positions can be visualised alongside the tour.

  • ax (Axes | None, default: None ) –

    Matplotlib axes to draw on. Creates a new figure if None.

Returns:

  • Axes –

    The axes with the plot.

Raises:

to_string() -> str

Return a string describing the solution.

Instance

Instance model for Tsp use case.

TspInstance

Bases: UcInstance[TspData, TspFormulation, TspSolution]

Instance combining data and formulation for Tsp.

Collection

Collection of Tsp instances.

TspCircleCollection

Bases: UcInstanceCollection[TspInstance]

Collection of Tsp instances.

generate(min_num_cities: int, max_num_cities: int, radius: float = 100.0, center: tuple[float, float] = (0.0, 0.0), num_instances: int = 1) -> TspCircleCollection classmethod

Generate TSP instances by placing cities equally on a circle.

Args: min_num_cities: Minimum number of cities per instance max_num_cities: Maximum number of cities per instance radius: Radius of the circle (in km) center: Center coordinates (x, y) of the circle num_instances: Number of instances to generate for each city count

Returns:

  • TSPCircleSet: Set containing generated circle-based TSP problems –