quboResult2tsp

Convert QUBO result to traveling salesperson solution

Since R2025b

Installation Required: This functionality requires MATLAB Support Package for Quantum Computing.

Syntax

order = quboResult2tsp(result)

[order,tourGraph] = quboResult2tsp(result,G)

Description

order = quboResult2tsp(result) converts the result of solving a traveling salesperson QUBO formulation to a solution for the corresponding problem, returned as a numeric index vector of the order the cities are visited. Use this function after solving a QUBO formulation created using the tsp2qubo function.

[order,tourGraph] = quboResult2tsp(result,G) converts the traveling salesperson QUBO formulation result to a solution for the corresponding problem specified by the graph G. In addition to the city-order vector, the function returns a graph of the optimal tour. If G has node names, the order is a cell array of names. Otherwise, it is a numeric vector.

Examples

Convert Traveling Salesperson Problem Matrix to QUBO

Define a traveling salesperson problem by creating a matrix of distances in miles between five cities. Assign names to the cities. The (i,j)th element of the matrix represents the distance between city i and city j. For example, D(1,2) = 284 indicates that the distance between London and Paris is 284 miles.

D = [0 284 1071 681 1100;
     284 0 792 655 885;
     1071 792 0 1442 1344;
     681 655 1442 0 935;
     1100 885 1344 935 0];
names = ["London" "Paris" "Madrid" "Berlin" "Rome"];

Convert the distance matrix to a QUBO problem.

qprob = tsp2qubo(D)

qprob = 
  qubo with properties:

    QuadraticTerm: [25×25 double]
       LinearTerm: [25×1 double]
     ConstantTerm: 14420
     NumVariables: 25

Solve the QUBO problem.

result = solve(qprob)

result = 
  quboResult with properties:

                BestX: [25×1 double]
    BestFunctionValue: 4036
      AlgorithmResult: [1×1 tabuSearchResult]

Convert the result of the QUBO problem to the traveling salesperson formulation. The returned numeric index vector indicates the order the cities are visited.

order = quboResult2tsp(result)

order = 1×5

     3     2     1     4     5

names(order)

ans = 1×5 string
    "Madrid"    "Paris"    "London"    "Berlin"    "Rome"

Convert Traveling Salesperson Problem Graph to QUBO

Create and plot a fully connected graph of five connected cities with weighted edges corresponding to the distances in miles between the cities. Assign names to the cities.

D = [0 284 1071 681 1100;
    284 0 792 655 885;
    1071 792 0 1442 1344;
    681 655 1442 0 935;
    1100 885 1344 935 0];
names = ["London" "Paris" "Madrid" "Berlin" "Rome"];
G = graph(D,names,"omitselfloops");
plot(G,EdgeLabel=G.Edges.Weight);

Convert the graph to a QUBO problem and solve it.

qprob = tsp2qubo(G);
result = solve(qprob)

result = 
  quboResult with properties:

                BestX: [25×1 double]
    BestFunctionValue: 4036
      AlgorithmResult: [1×1 tabuSearchResult]

Convert the result of the QUBO problem to the traveling salesperson formulation.

[order,tourGraph] = quboResult2tsp(result,G)

order = 5×1 cell
    {'Madrid'}
    {'Paris' }
    {'London'}
    {'Berlin'}
    {'Rome'  }

tourGraph = 
  graph with properties:

    Edges: [5×2 table]
    Nodes: [5×1 table]

Plot the resulting tour over the fully connected graph by specifying greater line widths for edges in G.Edges that correspond to the edges in tourGraph.Edges.

idxTour = findedge(G,order,circshift(order,-1));
LWidths = 0.5*ones(1,numedges(G));
LWidths(idxTour) = 5;
plot(G,EdgeLabel=G.Edges.Weight,LineWidth=LWidths)

Input Arguments

result — Solution of traveling salesperson QUBO problem

quboResult object

Solution of the traveling salesperson QUBO problem, specified as a quboResult object. Create result using the solve function for a QUBO problem generated using tsp2qubo.

G — Cities graph

graph object

Cities graph, specified as a graph object. The graph must be fully connected and cannot contain self-loops. Each graph node represents a city. The weight of an edge between two nodes of the graph represents the distance between two cities.

Output Arguments

order — City visit order

numeric vector | cell array of character vectors

City visit order, returned as a numeric vector or cell array of character vectors. If you specify just the result input argument, then the function returns a numeric vector. If you specify both the result and G input arguments, then the function returns a cell array of character vectors if G has node names.

If the traveling salesperson problem is specified using a graph object G, each element of the city visit order vector corresponds to a node in G. If G has node names, the elements of order will also be the node names. If G does not have node names, the nodes are automatically assigned numeric values and the elements of order will also be numeric.

Data Types: double | cell

tourGraph — Optimal tour graph

graph object

Optimal tour graph, returned as a graph object.

More About

Traveling Salesperson Problem

The classic traveling salesperson problem involves a group of cities (locations) that a salesperson must visit. Given the distances between each city, the problem is to minimize the total distance the salesperson travels while visiting each city only once and returning to the starting city.

Version History

Introduced in R2025b