Routing Problems (TSP & CVRP)

Divi provides specialized TSPProblem and CVRPProblem classes for solving routing problems with QAOA. Both are QAOAProblem subclasses and work with the same QAOA constructor described in Combinatorial Optimization with QAOA and PCE. They implement the Constraint-Enhanced QAOA (CE-QAOA) protocol [1], which uses block one-hot encoding with W-state initialization and an XY mixer to keep quantum amplitude concentrated on the feasible (permutation) subspace.

Why CE-QAOA?

For routing problems like TSP and CVRP, standard penalty-QAOA wastes most of its measurement shots on infeasible bitstrings — the feasible set (e.g. valid tours, or permutations more generally) is an exponentially small fraction of the full Hilbert space. CE-QAOA avoids this by co-designing the encoding, initial state, and mixer:

  • W-state initialization: starts each qubit block in a uniform superposition over one-hot basis states (exactly one city per slot).

  • XY mixer: all-to-all XY coupling within each block swaps excitations without creating or destroying them, preserving the one-hot constraint with a constant spectral gap.

  • Reduced phase operator: row constraints are enforced structurally, so only column and capacity penalties appear in the cost Hamiltonian.

Traveling Salesman Problem (TSP)

Given a symmetric cost matrix, find the shortest tour visiting every city exactly once and returning to the start.

import numpy as np
from divi.qprog import QAOA
from divi.qprog.problems import TSPProblem
from divi.qprog.optimizers import GridSearchOptimizer
from divi.backends import MaestroSimulator

cost = np.array([
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0],
])

problem = TSPProblem(cost, start_city=0)
backend = MaestroSimulator(shots=5000)

qaoa = QAOA(
    problem,
    optimizer=GridSearchOptimizer(
        param_ranges=[(0, 3.14), (0, 3.14)],
        grid_points=10,
    ),
    max_iterations=1,
    backend=backend,
)
qaoa.run()
print(qaoa.solution)  # decoded tour or bitstring

The start_city is fixed and excluded from the encoding, reducing the problem from n² to (n−1)² qubits. Penalty strengths constraint_penalty (constraints) and objective_weight (objective) can be tuned.

Capacitated Vehicle Routing (CVRP)

Route multiple vehicles from a depot to customers, respecting vehicle capacity constraints.

from divi.qprog.problems import CVRPProblem

cost_matrix = np.array([
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0],
])
demands = np.array([0, 3, 4, 2])  # depot demand = 0

problem = CVRPProblem(
    cost_matrix,
    demands=demands,
    capacity=10.0,
    n_vehicles=2,
    depot=0,
)

qaoa = QAOA(problem, backend=backend, max_iterations=10)
qaoa.run()

Binary Encoding

For larger instances, the one-hot encoding becomes impractical (e.g. 1,600 qubits for 20 customers with 4 vehicles). The binary encoding reduces qubit count from O(N) to O(log N) per routing slot:

problem = CVRPProblem(
    cost_matrix,
    demands=demands,
    capacity=10.0,
    n_vehicles=2,
    encoding="binary",   # compact binary encoding
)

This produces a higher-order binary optimization (HUBO) problem that is automatically quadratized. See the binary_block_config utility for qubit count estimates at various scales.

Feasibility, Repair, and Energy

Both problem classes implement:

  • is_feasible() — check whether a bitstring represents a valid tour/route.

  • repair_infeasible_bitstring() — project an infeasible bitstring to the nearest valid solution using the Hungarian algorithm (scipy.optimize.linear_sum_assignment).

  • compute_energy() — evaluate the actual travel cost.

These are used by QAOA’s get_top_solutions with the feasibility parameter:

# PHQC mode (arXiv:2511.14296, Algorithm 4): keep only feasible
# solutions, rank by objective energy (not probability).
solutions = qaoa.get_top_solutions(n=5, feasibility="filter")

# Repair infeasible solutions before ranking by energy.
solutions = qaoa.get_top_solutions(n=5, feasibility="repair")

Loading Benchmark Instances

The parse_tsplib_file utility reads standard TSPLIB/CVRPLIB .vrp files, as used by benchmarks like QOBLIB:

from divi.qprog.problems import parse_tsplib_file, parse_vrp_solution

inst = parse_tsplib_file("XSH-n20-k4-01.vrp")
# inst.cost_matrix, inst.demands, inst.capacity, inst.n_vehicles, ...

opt_routes, opt_cost = parse_vrp_solution("XSH-n20-k4-01.opt.sol")

Qubit Scaling

Qubit count by encoding

Customers

Vehicles

One-hot

Binary (full)

Binary (tight)

3

2

18

12

12

10

3

300

120

60

20

4

1,600

400

120

50

10

25,000

3,000

360

The “tight” binary column assumes max_steps ≈ customers / vehicles + 1.

Next Steps

References