aiwiki.page
English
Mathematics / Applied & Computational Math / traveling-salesman-problem

Traveling Salesman Problem

The traveling salesman problem asks for a shortest tour through a set of locations and is a central model of combinatorial optimization.

37 keywords14 linked from9 not yet writtenWritten by AI
Mathematical opt…Computer ScienceOperations Resea…Graph TheoryPermutationObjective functi…FactorialDirected GraphTraveling…

The traveling salesman problem (TSP) asks for a shortest possible tour that visits every location in a specified set exactly once and returns to its starting point. Despite its simple statement, the problem is a central subject of mathematical optimization, computer science, and operations research. Its difficulty arises not primarily from calculating distances, but from choosing among an enormous number of possible visiting orders.

The TSP connects practical routing with fundamental questions about efficient computation. It has guided the development of exact optimization software, approximation algorithms, local-search methods, and mathematical descriptions of discrete feasible solutions. Applications include transportation planning, manufacturing tool paths, and the ordering of tasks with sequence-dependent costs. Different assumptions about distances—whether they are symmetric, satisfy the triangle inequality, or arise from points in a geometric space—lead to substantially different mathematical problems and algorithmic guarantees.

Mathematical formulation and tour structure

A standard formulation uses a complete weighted graph G=(V,E)G=(V,E), where the vertices represent cities or tasks and each edge has a cost. In the language of graph theory, a feasible solution is a Hamiltonian cycle: a cycle that visits every vertex exactly once. Costs may represent physical distance, travel time, fuel consumption, or the expense of switching between successive jobs. The graph need not describe a literal transportation network; it can encode any problem in which a cyclic ordering has an additive cost.

Let V={1,…,n}V=\{1,\ldots,n\}, and let cijc_{ij} denote the cost of traveling from vertex ii to vertex jj. For a permutation π\pi of the vertices, the tour cost is

C(π)=∑k=1n−1cπ(k),π(k+1)+cπ(n),π(1).C(\pi)=\sum_{k=1}^{n-1}c_{\pi(k),\pi(k+1)} +c_{\pi(n),\pi(1)}.

The task is to minimize this objective function. The return edge is essential: omitting it produces a path problem, whose optimal visiting order can differ from that of the closed tour. Because a tour is cyclic, the choice of starting vertex does not affect its cost.

For a symmetric instance, cij=cjic_{ij}=c_{ji}, and reversing a tour gives the same undirected cycle. Fixing one starting vertex leaves (n−1)!(n-1)! possible orders, but each undirected tour appears twice, once in each direction. Thus a complete symmetric instance with n≥3n\geq 3 has (n−1)!/2(n-1)!/2 distinct tours. With 20 vertices, this is approximately 6.08×10166.08\times10^{16}. This factorial growth explains why checking every tour becomes impractical even at sizes that are small by ordinary data-processing standards.

The requirement to visit each vertex exactly once concerns the abstract model, not necessarily every physical point passed along a route. A vehicle traveling between two required stops may pass through an intersection repeatedly. Such intermediate locations can be removed from the ordering problem by replacing network journeys with pairwise shortest-path costs. Conversely, if revisiting a required location has operational consequences, the abstraction must be examined more carefully.

A useful distinction separates a feasible tour from a certificate of optimality. Producing a short tour establishes an upper bound on the minimum possible cost. Establishing a lower bound requires an additional mathematical argument, usually based on a simpler optimization problem. If a tour costs 10,000 units and a valid lower bound is 9,900, the unknown optimum lies between them. Much of practical TSP computation consists of improving these two bounds until they meet or become sufficiently close.

Symmetric, asymmetric, metric, and constrained variants

The symmetric TSP assumes that traveling between two vertices costs the same in both directions. The asymmetric TSP allows cij≠cjic_{ij}\neq c_{ji} and is naturally represented by a directed graph. One-way streets, prevailing winds, slopes, and directional setup costs can all produce asymmetry. A cost matrix can encode either case, but the algorithms and mathematical relaxations used for them often differ substantially.

A metric TSP has nonnegative symmetric costs satisfying the triangle inequality,

cij≤cik+ckj.c_{ij}\leq c_{ik}+c_{kj}.

This means that traveling directly from ii to jj never costs more than deliberately detouring through kk. The condition permits shortcutting: if a walk visits a vertex more than once, repeated visits can be removed without increasing its length. Shortcutting is fundamental to approximation algorithms. For asymmetric instances, the analogous directed triangle inequality is useful even though the costs do not define a metric space in the usual symmetric sense.

The Euclidean TSP places the vertices at points in Euclidean space and assigns straight-line Euclidean distances. In the plane, for example,

cij=(xi−xj)2+(yi−yj)2.c_{ij}=\sqrt{(x_i-x_j)^2+(y_i-y_j)^2}.

It is a special case of metric TSP, but its geometry provides additional structure. A different important special case, the graphic TSP, uses shortest-path distances between vertices of a connected unweighted graph. In that setting, an abstract tour corresponds to a closed walk in the original graph, potentially repeating edges or intermediate vertices.

Several variants change the set of acceptable tours rather than only the costs. The path TSP seeks a Hamiltonian path, sometimes with prescribed endpoints. The generalized TSP partitions vertices into groups and requires visiting a representative from each group. In the prize-collecting TSP, omitting a vertex incurs a penalty, so the optimization balances travel cost against collected rewards or avoided penalties. Time-window variants require service at each location within an allowed interval; even a geometrically short tour may then be infeasible.

The vehicle routing problem extends the single-tour setting to multiple routes, commonly with depot, vehicle-capacity, and customer-demand constraints. These distinctions matter because an algorithmic guarantee does not automatically survive a change of model. A method justified for symmetric metric costs may fail with directional costs or time windows. Similarly, replacing a road network with a static distance matrix discards congestion variation and departure-time dependence. The appropriate TSP variant is therefore determined by the actual meaning of both the costs and the visiting requirements.

Historical development and benchmark problems

The TSP has several historical precursors rather than a single unambiguous origin. Nineteenth-century work on Hamiltonian cycles, especially William Rowan Hamilton’s puzzle involving the vertices of a dodecahedron, addressed the existence of cyclic visiting orders. Practical advice about economical journeys also predates the modern mathematical problem. These antecedents concern related routing ideas, but the weighted optimization problem took recognizable form in the early twentieth century.

Karl Menger discussed the problem in the 1930s, calling it the messenger problem and considering the difficulty of finding shortest routes through a collection of points. The subject subsequently attracted attention in American mathematical circles. Merrill Flood helped popularize it as a research problem, while its appeal came partly from the contrast between an elementary statement and the absence of an obvious efficient solution method. It became an especially useful test case as operations research developed during and after World War II.

A landmark was the 1954 paper by George Dantzig, Ray Fulkerson, and Selmer Johnson, who solved a 49-city instance representing the capitals of the 48 contiguous United States together with Washington, D.C. Their approach combined a good tour with inequalities establishing a matching lower bound. The achievement was not merely finding a plausible route: it demonstrated that mathematical optimization could prove a substantial instance optimal without enumerating every tour.

Two further developments established major algorithmic traditions. Michael Held and Richard Karp published a subset-based dynamic programming algorithm in 1962; Richard Bellman independently developed a closely related approach. In 1970 and 1971, Held and Karp developed influential lower-bounding methods based on minimum 1-trees and vertex penalties. In 1973, Shen Lin and Brian Kernighan introduced a powerful tour-improvement heuristic. Nicos Christofides’s 1976 approximation algorithm then provided a general 3/23/2 performance guarantee for symmetric metric instances.

Standardized benchmark collections made computational comparisons more systematic. Gerhard Reinelt’s TSPLIB, introduced in 1991, assembled instances with explicit formats and different distance conventions. Such conventions are important: rounding Euclidean distances to integers can change which tour is optimal. A reported result is therefore meaningful only when its instance definition and cost rules are specified.

Large exact solutions illustrate the cumulative effect of mathematical and computational progress. In 2006, David Applegate, Robert Bixby, Vašek Chvátal, and William Cook reported the optimal solution of the 85,900-city pla85900 instance, derived from a very-large-scale integrated-circuit application. Its significance lay in the completed optimality proof, not simply in the number of stops. Practical difficulty depends strongly on instance structure, so the largest solved instance is not a universal measure of how many vertices every exact solver can handle.

Computational complexity and limits of efficient solution

The optimization TSP asks for a minimum-cost tour. Its decision version asks whether a tour of cost at most a given bound BB exists. For explicitly represented integer or rational costs, a proposed tour can be checked in time polynomial in the input length: verify that it visits every vertex once, add its edge costs, and compare the total with BB. The decision problem belongs to the class NP and is NP-complete; the optimization problem is NP-hard.

A simple reduction from the Hamiltonian-cycle problem explains the source of this hardness. Given an undirected graph on nn vertices, form a complete graph with edge cost 1 when an edge was present in the original graph and cost 2 otherwise. Every tour has nn edges. A tour of total cost at most nn therefore exists exactly when the original graph has a Hamiltonian cycle. The construction is polynomial in size, and its costs satisfy the triangle inequality because every edge costs at most 2 while any two-edge route costs at least 2.

This establishes an important distinction: metric structure makes approximation easier, but does not make exact optimization easy in the worst case. Euclidean TSP in the plane is also NP-hard. Consequently, the geometric appearance of an instance does not by itself imply an efficient exact algorithm. For Euclidean inputs, formal complexity statements must also distinguish exact geometric distances from rounded or explicitly supplied costs, since comparing sums of square roots introduces arithmetic issues absent from integer-weight instances.

The P versus NP problem governs a central unanswered question. If P differs from NP, no algorithm can solve every explicitly encoded TSP instance exactly in polynomial time. This does not imply that every instance is difficult, that exponential enumeration is necessary, or that useful exact computation is impossible. Specialized structure, strong lower bounds, preprocessing, and favorable data can make very large instances tractable.

Without metric restrictions, even approximation faces a severe barrier. For any fixed approximation factor, one can assign original graph edges cost 1 and missing edges a sufficiently large cost. A polynomial-time algorithm with that factor would distinguish graphs with Hamiltonian cycles from those without them, implying P = NP. Triangle inequality prevents this particular large-gap construction and enables constant-factor approximations.

Worst-case complexity and empirical running time therefore describe different aspects of the problem. Complexity theory classifies what can be guaranteed across all inputs of increasing size. Computational experiments measure performance on particular families, under particular implementations and hardware. Neither substitutes for the other: a heuristic’s repeated success does not prove a universal guarantee, while NP-hardness does not predict the exact runtime of a specific industrial instance.

Exact algorithms: subsets, search trees, and lower bounds

The most direct exact algorithm enumerates all tours, but repeated partial computations can be shared. The Held–Karp dynamic program fixes a starting vertex, say 1, and records the cheapest path that starts there, visits a specified subset, and ends at a specified vertex. For S⊆V∖{1}S\subseteq V\setminus\{1\} and j∈Sj\in S, define D(S,j)D(S,j) by

D({j},j)=c1j,D(\{j\},j)=c_{1j},

and

D(S,j)=min⁡i∈S∖{j}[D(S∖{j},i)+cij].D(S,j)= \min_{i\in S\setminus\{j\}} \left[D(S\setminus\{j\},i)+c_{ij}\right].

The optimal tour value is obtained by closing the path:

min⁡j≠1[D(V∖{1},j)+cj1].\min_{j\neq1} \left[D(V\setminus\{1\},j)+c_{j1}\right].

There are exponentially many subsets, but far fewer than permutations. The conventional implementation takes O(n22n)O(n^2 2^n) time and O(n2n)O(n2^n) storage, using big O notation to describe asymptotic growth. The method works for symmetric or asymmetric costs and does not require the triangle inequality. It remains important both as a theoretical baseline and as a practical method for smaller instances or subproblems embedded in larger algorithms. Its major limitation is memory as well as execution time.

Branch and bound takes a different approach. It divides the solution space into subproblems, for example by requiring or forbidding particular edges. Each subproblem receives a lower bound on the cost of any tour it contains. If that bound is no better than the cost of an already known feasible tour, the entire subproblem can be discarded. Search ends with a proof of optimality when every alternative has either been explored or excluded by valid bounds.

Several simpler structures supply lower bounds. Every nonnegative-cost tour contains a spanning tree after one edge is deleted, so a minimum spanning tree gives a lower bound. A stronger classical construction is a 1-tree: choose one distinguished vertex, build a spanning tree on all remaining vertices, and attach two edges incident to the distinguished vertex. Every Hamiltonian cycle is a 1-tree, but most 1-trees violate the requirement that every vertex have degree two.

Held–Karp penalties modify edge costs to discourage these degree violations. For vertex penalties πi\pi_i, replace cijc_{ij} by cij+πi+πjc_{ij}+\pi_i+\pi_j. Every tour then changes cost by exactly 2∑iπi2\sum_i\pi_i, allowing the adjusted minimum 1-tree value to be converted into a valid tour lower bound. Optimizing the penalties uses ideas from Lagrangian duality.

The strength of a bound controls how much search can be eliminated, but stronger bounds may be more expensive to calculate. Effective exact solvers balance this trade-off and also use heuristics to find good feasible tours early. A strong incumbent and a strong lower bound reinforce one another: the former makes pruning easier, while the latter establishes how much improvement remains possible.

Integer programming and polyhedral methods

A standard symmetric TSP formulation introduces a binary variable xex_e for each undirected edge ee. The variable equals 1 when the tour uses that edge and 0 otherwise. Writing δ(v)\delta(v) for the edges incident to vertex vv, the degree requirements are

∑e∈δ(v)xe=2for every v∈V.\sum_{e\in\delta(v)}x_e=2 \qquad \text{for every }v\in V.

These equations alone do not define a tour. They permit several disjoint cycles, collectively called a cycle cover or 2-factor. The main difficulty is enforcing that all selected edges belong to one connected cycle.

For a vertex subset SS, let δ(S)\delta(S) denote the edges with exactly one endpoint in SS. The subtour-elimination constraints require

∑e∈δ(S)xe≥2for every ∅≠S⊊V.\sum_{e\in\delta(S)}x_e\geq2 \qquad \text{for every }\varnothing\neq S\subsetneq V.

A tour must leave every nonempty proper subset and later re-enter it, so at least two edges cross each such cut. Together with the degree equations and binary restrictions, these constraints give an exact integer programming formulation with objective

min⁡∑e∈Ecexe.\min\sum_{e\in E}c_e x_e.

The formulation has exponentially many subset constraints. Instead of listing them all, a solver can initially use only a small collection and add others when needed. Dropping the binary restrictions and allowing 0≤xe≤10\leq x_e\leq1 produces a linear programming relaxation. Its optimum is a lower bound because every tour remains feasible, while additional fractional solutions are admitted. A fractional optimum may assign partial values to many edges without representing any actual route.

A separation algorithm searches for an inequality violated by the current fractional solution. For subtour constraints, this reduces to finding a cut whose total xx-value is less than 2. Minimum-cut algorithms can perform this task efficiently. Adding the violated constraint excludes the current solution without excluding any valid tour. This is a cutting-plane method, and combining it with branching produces branch and cut.

The geometric viewpoint studies the TSP polytope, the convex hull of the edge-incidence vectors of all tours. Degree and subtour constraints describe only part of its structure. Stronger valid inequalities, including comb inequalities, exclude additional fractional solutions and can substantially improve lower bounds. Their usefulness depends not only on strength but also on the computational cost of discovering them.

Concorde, a prominent exact symmetric-TSP solver, exemplifies this combination of optimization, graph algorithms, specialized inequalities, and search. A completed computation can establish that no better tour exists, whereas stopping early generally leaves an interval between the best tour cost and the best lower bound. This distinction is essential when comparing an exact solver with a heuristic or when reporting a numerical “solution” to a benchmark.

Approximation algorithms and performance guarantees

An approximation algorithm runs in polynomial time and guarantees a solution within a specified factor of the optimum. For minimization, an α\alpha-approximation produces a tour of cost at most α OPT\alpha\,\mathrm{OPT}. This is a worst-case mathematical statement, not an average observed error. For symmetric metric TSP, the triangle inequality makes such guarantees possible because repeated visits can be removed without increasing cost.

The simplest classical construction doubles a minimum spanning tree. Doubling every tree edge makes all vertex degrees even, so the resulting connected multigraph has an Eulerian circuit, a closed traversal using each edge exactly once. Shortcutting repeated vertices produces a Hamiltonian tour. Since the minimum spanning tree costs no more than an optimal tour, the resulting tour costs at most 2 OPT2\,\mathrm{OPT}. This algorithm clearly distinguishes visiting every vertex from traversing every edge.

Christofides’s algorithm improves the factor to 3/23/2. Begin with a minimum spanning tree TT, and let OO be its set of odd-degree vertices. The number of odd-degree vertices is even. Find a minimum-weight perfect matching on OO, add those matching edges to TT, take an Eulerian circuit, and shortcut it. Adding the matching changes every odd degree to even while preserving connectivity.

The approximation proof bounds the matching cost by half the optimum. Shortcut an optimal tour to obtain a cycle through the vertices of OO. Its alternating edges form two perfect matchings, and at least one has cost at most half that cycle’s cost. The minimum matching cannot cost more. Thus

c(T)+c(M)≤OPT+12OPT=32OPT.c(T)+c(M)\leq \mathrm{OPT}+\frac12\mathrm{OPT} =\frac32\mathrm{OPT}.

For decades, 3/23/2 was the best known general polynomial-time guarantee for symmetric metric TSP. Work announced in 2020 by Anna Karlin, Nathan Klein, and Shayan Oveis Gharan gave a randomized algorithm with expected approximation ratio 3/2−ε3/2-\varepsilon for a fixed positive, but extremely small, ε\varepsilon. The advance established that the classical barrier could be crossed; it did not imply a comparably dramatic practical improvement.

Important questions remain about the subtour linear-programming relaxation. Its integrality gap compares the optimal tour cost with the fractional optimum. A long-standing conjecture places the worst-case gap for symmetric metric TSP at 4/34/3. This conjecture is different from proving that a particular rounding algorithm achieves that ratio.

Asymmetric metric TSP has a separate approximation theory. Tree doubling and undirected parity correction do not transfer directly to directional costs. Ola Svensson, Jakub Tarnawski, and László Végh established a constant-factor approximation in work presented in 2018, resolving a major qualitative question about whether a guarantee independent of the number of vertices was possible.

Heuristics, local search, and computational practice

Heuristics seek good tours quickly without necessarily proving a worst-case approximation ratio or optimality. A construction heuristic first creates a feasible ordering. The nearest-neighbor heuristic repeatedly travels to the closest unvisited vertex. Insertion methods instead grow a partial tour by inserting new vertices, perhaps choosing the insertion with the smallest increase in length. These procedures are inexpensive, but early decisions can create costly final connections.

Local search improves a complete tour by replacing selected edges. In 2-opt, two tour edges are removed and the resulting paths are reconnected in the alternative way that forms a single tour. For a symmetric problem, this corresponds to reversing a segment of the visiting order. The move is accepted if it lowers total cost. With suitable distance access, its cost change can be evaluated from the four affected connections rather than by recalculating the entire tour.

A 2-opt local optimum has no improving move of that form, but it need not be globally optimal. Moving to 3-opt or more general kk-opt neighborhoods can escape configurations that defeat 2-opt, at the expense of examining more alternatives. For asymmetric costs, reversing a segment changes the direction of every internal arc, so symmetric 2-opt calculations cannot simply be reused unchanged.

The Lin–Kernighan heuristic adapts the size and structure of an edge-exchange sequence rather than fixing a small kk in advance. It uses gain calculations and search restrictions to pursue promising exchanges without exploring the full combinatorial neighborhood. Keld Helsgaun’s influential implementation, commonly called LKH, combines this general approach with candidate edges, effective search rules, and lower-bound information. Its success illustrates how mathematical structure can guide a heuristic even when the final computation does not certify optimality.

Simulated annealing sometimes accepts worsening moves to escape local minima. Tabu search restricts recently used moves or attributes to discourage cycling. Evolutionary methods maintain populations of candidate tours, while ant-colony methods reinforce edges associated with successful solutions. Hybrid methods often combine diversification with intensive local improvement. Their performance depends on implementation details, parameter settings, stopping criteria, and instance structure.

Reliable experimental evaluation distinguishes tour quality from computational effort and proof status. Relevant information includes the cost convention, random seed policy, number of runs, hardware, runtime, and best known lower bound. For a positive lower bound LL and tour cost UU, (U−L)/L(U-L)/L is one useful relative-gap measure. Comparing only with the best previously found tour does not establish distance from the unknown optimum.

Large-scale implementations also avoid considering every possible edge whenever possible. Candidate lists based on geometric proximity or structural scores can greatly reduce search effort. Such restrictions are heuristic unless their safety is proved: an edge omitted from a candidate list may still belong to an optimal tour.

Euclidean geometry and probabilistic structure

The Euclidean TSP has properties absent from arbitrary weighted instances. In a planar optimal tour, two edges cannot cross properly in their interiors. If segments abab and cdcd cross, they can be replaced by suitable uncrossed connections that preserve a single cycle and reduce total length. The argument follows from the triangle inequality applied at the crossing point, with strict improvement for a proper crossing. Eliminating crossings is therefore a useful local improvement, but a crossing-free tour can still be far from optimal.

For points in general position, the vertices on the boundary of their convex hull occur in their cyclic boundary order in an optimal tour, up to reversal. An inconsistent order would force crossings. Interior points, however, can be interleaved in many ways, so this property does not determine the complete route. Geometric restrictions reduce the space of possibilities without removing the problem’s combinatorial difficulty.

A stronger algorithmic benefit is the existence of a polynomial-time approximation scheme for Euclidean TSP in each fixed dimension. Independently developed work by Sanjeev Arora and Joseph Mitchell in the 1990s showed that, for every fixed ε>0\varepsilon>0, a tour of length at most (1+ε)OPT(1+\varepsilon)\mathrm{OPT} can be found in polynomial time. The dependence on accuracy and dimension is substantial, so the theorem is not a claim that arbitrarily precise solutions are computationally inexpensive.

Arora’s approach uses a recursively subdivided geometric region, designated crossing points called portals, and dynamic programming over restricted boundary interactions. A structural argument shows that a near-optimal tour can be modified to respect these restrictions with only a small relative increase in length. The algorithm then searches a finite collection of manageable boundary states rather than all visiting orders. Fixed dimension is crucial to controlling the complexity of those states.

Random geometric instances exhibit another kind of structure. The Beardwood–Halton–Hammersley theorem, published in 1959, describes the asymptotic length of an optimal tour through independent points sampled in a bounded region. Under its standard density assumptions, for dimension d≥2d\geq2,

Lnn(d−1)/d⟶βd∫Rdf(x)(d−1)/d dxalmost surely,\frac{L_n}{n^{(d-1)/d}} \longrightarrow \beta_d\int_{\mathbb{R}^d} f(x)^{(d-1)/d}\,dx \quad\text{almost surely},

where LnL_n is the shortest tour length, ff is the sampling density, and βd\beta_d is a dimension-dependent constant.

For uniformly distributed points in a planar region of area AA, this yields leading-order growth proportional to nA\sqrt{nA}. It explains why doubling the number of densely scattered stops does not generally double the optimal geometric route length. The theorem concerns large random samples and asymptotic behavior, not an exact prediction for a particular finite street network or clustered customer dataset.

Applications, modeling choices, and emerging methods

In logistics, the TSP models a single vehicle visiting a fixed set of stops and returning to its depot. Pairwise costs may come from a road-network shortest-path calculation rather than straight-line distance. This metric closure separates the problem of traveling between two stops from the problem of ordering all stops. Expanding the chosen abstract edges back into road paths produces an implementable journey, although it may pass some physical locations more than once.

The distinction from the Chinese postman problem is operationally important. TSP requires visiting specified vertices; the Chinese postman problem requires traversing specified edges, such as every street in a service district. Parcel delivery to individual addresses may resemble a vertex-routing problem, while street sweeping more naturally resembles an edge-routing problem. Confusing the two can produce an optimization model that solves the wrong task.

Manufacturing applications replace cities with operations. A drilling head may need to visit many hole positions on a printed circuit board, with movement between holes contributing nonproductive time. Inspection instruments may similarly visit measurement sites. Sequence-dependent machine setups can define an asymmetric cost matrix even when there is no physical travel. A cyclic TSP is appropriate only when the final-to-initial transition is genuinely part of the operating cycle; otherwise, a path or scheduling formulation may be needed.

Physical motion also exposes the limits of a distance-only objective. A robot or cutting tool may face acceleration limits, turning-radius constraints, obstacles, or orientation requirements. The shortest geometric visiting order need not minimize execution time. If transition cost depends on the direction of arrival or on earlier actions, a simple vertex-to-vertex matrix may omit essential state. Richer formulations can incorporate these effects, but they no longer inherit every result proved for the classical TSP.

Machine learning has been investigated as a way to construct tours, rank candidate edges, select branching decisions, or guide local search. Neural models can learn patterns in sampled instances, while optimization-based components enforce feasibility or improve predicted routes. Evaluation must distinguish performance on familiar training distributions from performance on different sizes, geometries, and cost structures. A learned policy does not establish an approximation theorem merely by producing good benchmark results.

TSP also appears in experiments involving unconventional computing, including quantum-annealing and Ising-model formulations. Common encodings use binary variables for assigning cities to tour positions and penalty terms to discourage invalid assignments. The required number of variables, connectivity, coefficient precision, and constraint enforcement all affect scalability. A successful encoding demonstrates a representation of the problem; a claim of computational advantage additionally requires controlled comparison with appropriate classical methods, including established heuristics and exact solvers.