巡回セールスマン問題

TSPは、都市を頂点、経路を辺、経路の距離を辺の重みとする無向重み付きグラフとしてモデル化できます。これは、指定された頂点を出発点とし、他のすべての頂点をちょうど一度ずつ訪問した後に、その頂点で終了するという最小化問題です。多くの場合、モデルは完全グラフ（つまり、すべての頂点のペアが辺で接続されている）です。2つの都市間に経路が存在しない場合、十分な長さの辺を追加することで、最適な経路に影響を与えることなくグラフを完成させることができます。

対称型TSPでは、2つの都市間の距離はどちらの方向でも同じで、無向グラフを形成します。この対称性により、可能な解の数は半分になります。非対称型TSPでは、両方向に経路が存在しない場合や、距離が異なる場合があり、有向グラフを形成します。交通渋滞、一方通行の道路、出発地と到着地で料金が異なる都市間の航空運賃などは、非対称型のTSP問題を生み出す可能性のある現実的な要因です。

• グラフ理論の観点から同等の定式化を行うと、次のようになります。完全重み付きグラフ（頂点は都市、辺は道路、重みはその道路のコストまたは距離を表す）が与えられたとき、重みが最小のハミルトン閉路を見つけます。これは、完全でない重みなしグラフにハミルトン路（または閉路）が存在するかどうかを問うハミルトン路問題よりも一般的です。
• 出発都市に戻るという要件は、問題の計算複雑性を変化させません。ハミルトン経路問題を参照してください。
• 関連するもう 1 つの問題は、ボトルネック巡回セールスマン問題です。これは、最も重みのあるエッジの重みが最小となる重み付きグラフのハミルトン閉路を見つける問題です。現実世界の例としては、大型バスで狭い道路を避けることが挙げられます。^{[ 15 ]}この問題は、明らかな輸送および物流分野以外にも、実用上非常に重要な問題です。典型的な例は、プリント基板製造です。PCB に穴を開けるためのドリルマシンのルートのスケジューリングです。ロボットによる機械加工や穴あけアプリケーションでは、「都市」は機械加工する部品または穴あけする (さまざまなサイズの) 穴であり、「移動コスト」にはロボットの再調整時間が含まれます (単一機械ジョブシーケンス問題)。^{[ 16 ]}
• 一般化された巡回セールスマン問題（「巡回政治家問題」とも呼ばれる）は、(1 つ以上の)「都市」を持つ「州」を扱い、セールスマンは各州からちょうど 1 つの都市を訪問しなければならない。 1 つの応用例は、刃の交換を最小限に抑えるために、切削ストック問題の解を順序付ける際に見られる。もう 1 つは、半導体製造における穴あけに関するものである。たとえば、米国特許第 7,054,798 号を参照。 Noon と Bean は、一般化された巡回セールスマン問題を、都市の数は同じだが距離行列が変更された標準的な TSP に変換できることを示した。
• 順序付け問題とは、都市間に優先順位関係が存在する一連の都市を訪問する問題を扱うものである。
• Googleの面接でよく聞かれる質問の一つに、データ処理ノード間でデータをどのようにルーティングするかというものがあります。ルーティングはデータ転送にかかる時間によって異なりますが、ノードの計算能力やストレージ容量も異なるため、データの送信先を決定する問題が複雑化します。
• 巡回購買者問題とは、一連の製品を購入する責任を負う購買者に関する問題です。購買者は複数の都市でこれらの製品を購入できますが、価格は都市によって異なり、またすべての都市で同じ製品が販売されているわけではありません。目的は、総コスト（移動コスト＋購入コスト）を最小限に抑えつつ、必要なすべての製品を購入できるような、都市間の経路を見つけることです。

それに加えて${\displaystyle x_{ij}}$上記の変数にはそれぞれ${\displaystyle i=1,\ldots ,n}$ダミー変数$u_i$都市訪問の順序を記録し、都市から数える${\displaystyle 1}$解釈は$u_{i}<u_{j}}$都市を意味する${\displaystyle i}$都市を訪れる前に${\displaystyle j.}$特定のツアー（値にエンコードされたもの）${\displaystyle x_{ij}}$変数）に対して満足のいく値を見つけることができる$u_i$変数を作成する$u_i$都市から出発する場合、そのツアーに沿ったエッジの数に等しい。${\displaystyle 1}$市内へ${\displaystyle i.}$^{[ 22 ]}

線形計画法は非厳密な不等式を好むため（${\displaystyle \geq }$) 厳格すぎる(${\displaystyle >}$）我々は、次のような制約を課したいと考えている。

${\displaystyle u_{j}\geq u_{i}+1}$もし${\displaystyle x_{ij}=1.}$

単に要求するだけで${\displaystyle u_{j}\geq u_{i}+x_{ij}}$それでは達成できない、なぜならそれには${\displaystyle u_{j}\geq u_{i}}$いつ${\displaystyle x_{ij}=0,}$これは正しくありません。代わりにMTZは${\displaystyle n(n-1)}$線形制約

${\displaystyle u_{i}-u_{j}+1\leq (n-1)(1-x_{ij})}$すべての異なる${\displaystyle i,j\in \{2,\dotsc ,n\},}$

ここで定数項${\displaystyle n-1}$十分な余裕を持たせることで${\displaystyle x_{ij}=0}$関係を課さない${\displaystyle u_{j}}$そして${\displaystyle u_{i}.}$

そのやり方${\displaystyle u_{i}}$変数は、単一のツアーがすべての都市を訪れることを強制し、少なくとも増加します${\displaystyle 1}$ツアーの各ステップごとに、ツアーが都市を通過する場合にのみ減額が許可される ${\displaystyle 1.}$その制約は、都市を通らないすべてのツアーで違反されるだろう。 ${\displaystyle 1,}$だからそれを満たす唯一の方法は、ツアーが通過する都市 ${\displaystyle 1}$また、他のすべての都市も通過します。

したがって、MTZによるTSPの定式化は、以下の整数線形計画問題となる。

${\displaystyle {\begin{aligned}\min \sum _{i=1}^{n}\sum _{j\neq i,j=1}^{n}c_{ij}x_{ij}&\colon &&\\x_{ij}\in {}&\{0,1\}&&i,j=1,\ldots ,n;\\\sum _{i=1,i\neq j}^{n}x_{ij}={}&1&&j=1,\ldots ,n;\\\sum _{j=1,j\neq i}^{n}x_{ij}={}&1&&i=1,\ldots ,n;\\u_{i}-u_{j}+1\leq {}&(n-1)(1-x_{ij})&&2\leq i\neq j\leq n;\\2\leq u_{i}\leq {}&n&&2\leq i\leq n.\end{aligned}}}$

最初の等式は、各都市へは他の都市からちょうど1つだけ到達できることを要求し、2番目の等式は、各都市から他の都市へはちょうど1つだけ出発できることを要求する。最後の制約は、すべての都市を網羅するツアーは1つだけであり、すべての都市をまとめて網羅する2つ以上の互いに素なツアーは存在しないことを保証する。

都市に1、…、nの番号を付け、以下を定義してください。

${\displaystyle x_{ij}={\begin{cases}1&{\text{the path goes from city }}i{\text{ to city }}j\\0&{\text{otherwise.}}\end{cases}}}$

取る${\displaystyle c_{ij}>0}$を都市iから都市jまでの距離とする。すると、TSP は次の整数線形計画問題として記述できる。

${\displaystyle {\begin{aligned}\min &\sum _{i=1}^{n}\sum _{j\neq i,j=1}^{n}c_{ij}x_{ij}\colon &&\\&\sum _{i=1,i\neq j}^{n}x_{ij}=1&&j=1,\ldots ,n;\\&\sum _{j=1,j\neq i}^{n}x_{ij}=1&&i=1,\ldots ,n;\\&\sum _{i\in Q}{\sum _{j\neq i,j\in Q}{x_{ij}}}\leq |Q|-1&&\forall Q\subsetneq \{1,\ldots ,n\},|Q|\geq 2.\\\end{aligned}}}$

DFJ 定式化の最後の制約 (部分巡回路除去制約と呼ばれる) は、どの真部分集合 Q も部分巡回路を形成できないことを保証するため、返される解は単一の巡回路であり、より小さな巡回路の和集合ではありません。直感的には、都市の各真部分集合 Q に対して、この制約は Q 内の都市の数よりもエッジの数が少ないことを要求します。Q 内のエッジの数と Q 内の都市の数が同じであれば、それは Q 内の都市の部分巡回路を表すことになります。これは可能な制約の数を指数関数的に増加させるため、実際には行生成によって解決されます。^{[ 23 ]}

最も直接的な解決策は、すべての順列（順序付き組み合わせ）を試して、どれが最も安価かを確認することです（総当たり探索を使用）。このアプローチの実行時間は、多項式係数の範囲内です。${\displaystyle O(n!)}$、これは都市数の階乗なので、この解決策は20都市だけでも非現実的になります。

動的計画法の初期の応用例の一つに、問題を時間で解くヘルド・カープアルゴリズムがある。${\displaystyle O(n^{2}2^{n})}$[ ^{24 ]​}

これらの時間制限を改善するのは難しいようです。たとえば、TSP の古典的な厳密アルゴリズムが時間で実行できるかどうかはまだ決定されていません。${\displaystyle O(1.9999^{n})}$存在する。^{[ 25 ]} AmbainisらによるTSPに対する現在の最良の量子厳密アルゴリズムは時間で実行される。${\displaystyle O(1.728^{n})}$[ ^{26 ]​}

その他のアプローチとしては、以下のようなものがある。

• 数千の都市を含む巡回セールスマン問題（TSP）を処理するために使用できる、さまざまな分岐限定法アルゴリズム。

• 線形計画法に似た手法を用いる漸進的改善アルゴリズム。これは最大200都市までの範囲で有効である。
• 分枝限定法と問題固有のカット生成の実装（分枝限定法^{[ 27 ]}）；^{[ 28 ]}これは、大規模なインスタンスを解決するための最適な方法です。このアプローチは、85,900の都市を持つインスタンスを解決する現在の記録を保持しています（Applegate et al. (2006)を参照） 。

TSPLIB の 15,112 のドイツの町に対する正確な解は、1954 年にGeorge Dantzig、Ray Fulkerson、およびSelmer M. Johnsonによって提案された線形計画法に基づく切断平面法を使用して 2001 年に発見されました。計算は、ライス大学とプリンストン大学にある 110 個のプロセッサのネットワークで実行されました。総計算時間は、単一の 500 MHz Alpha プロセッサで 22.6 年に相当するものでした。2004 年 5 月には、スウェーデンのすべての 24,978 の町を訪問する巡回セールスマン問題が解決されました。約 72,500 キロメートルの長さのツアーが発見され、より短いツアーは存在しないことが証明されました。^{[ 29 ]} 2005 年 3 月、回路基板上の 33,810 点すべてを訪問する巡回セールスマン問題がConcorde TSP Solver を使用して解決されました。長さ 66,048,945 ユニットの巡回経路が見つかり、より短い巡回経路は存在しないことが証明されました。計算には約 15.7 CPU 年かかりました(Cook et al. 2006)。2006 年 4 月には、85,900 点のインスタンスがConcorde TSP Solverを使用して解決され、136 CPU 年以上かかりました。Applegate et al. (2006)を参照してください。  

さまざまなヒューリスティックと近似アルゴリズムが考案されており、これらは迅速に良好な解をもたらします。これらには、マルチフラグメントアルゴリズムが含まれます。最新の手法では、非常に大規模な問題（数百万の都市）に対して、妥当な時間内に、最適解からわずか2～3%しか離れていない解を高い確率で見つけることができます。^{[ 14 ]}

ヒューリスティックにはいくつかのカテゴリーが認められている。

構成的ヒューリスティクス

最近傍法（NN）アルゴリズム（貪欲法の一種）では、セールスマンは次に訪れるべき最も近い未訪問都市を選択します。このアルゴリズムは、効果的に短いルートを迅速に生成します。平面上にランダムに分布するN個の都市の場合、このアルゴリズムは平均して最短経路よりも25%長い経路を生成します。^{[ 30 ]}ただし、NNアルゴリズムが最悪のルートを生成するような、特別な都市分布が多数存在します。^{[ 31 ]}これは、非対称TSPと対称TSPの両方に当てはまります。^{[ 32 ]} Rosenkrantzら^{[ 33 ]}は、NNアルゴリズムの近似係数が${\displaystyle \Theta (\log |V|)}$三角不等式を満たすインスタンスの場合。NN アルゴリズムの変形である最近傍フラグメント (NF) 演算子は、最も近い未訪問都市のグループ (フラグメント) を接続し、連続する反復でより短いルートを見つけることができます。^{[ 34 ]} NF 演算子は、より良い解のみが受け入れられるエリート主義モデルでさらに改善するために、NN アルゴリズムによって得られた初期解にも適用できます。

点の集合のビトニックツアーとは、それらの点を頂点とする最小周長の単調多角形のことであり、動的計画法を用いて効率的に計算することができる。

もう1つの構成的ヒューリスティックであるMatch Twice and Stitch (MTS)は、2つの連続したマッチングを実行します。2番目のマッチングは、最初のマッチングのすべてのエッジを削除した後に実行され、サイクルのセットを生成します。次に、サイクルをステッチして最終的なツアーを生成します。^{[ 35 ]}

クリストフィデスとセルジュコフのアルゴリズム

ChristofidesとSerdyukovのアルゴリズムは同様の概要に従いますが、最小全域木と別の問題である最小重み完全マッチングの解法を組み合わせています。これにより、最適解の最大1.5倍のTSPツアーが得られます。これは最初の近似アルゴリズムの1つであり、扱いにくい問題に対する実用的なアプローチとして近似アルゴリズムに注目を集めるきっかけの一つとなりました。実際、「アルゴリズム」という用語は、後になるまで近似アルゴリズムに一般的に拡張されることはありませんでした。Christofidesアルゴリズムは当初、Christofidesヒューリスティックと呼ばれていました。^{[ 10 ]}

このアルゴリズムは、グラフ理論の結果を利用することで物事を異なる視点から捉え、最小全域木のコストを2倍にすることで得られたTSPの下限を改善します。オイラーグラフが与えられた場合、オイラーツアーを見つけることができます。${\displaystyle O(n)}$時間、 ^{[ 6 ]}したがって、TSP の都市を頂点とするオイラーグラフがあれば、オイラー巡回路を見つけるためのこのような方法を使用して TSP の解を見つけることができることが容易にわかります。三角不等式により、TSP 巡回路はオイラー巡回路より長くはならないことがわかっているので、TSP の下限が得られます。このような方法は以下に説明します。

1. この問題に対する最小全域木を求めなさい。
2. オイラーグラフを作成するために、すべての辺の複製を作成します。
3. このグラフのオイラー路を求めなさい。
4. TSPに変換する：ある都市が2回訪問された場合、ツアー内でその都市の前の都市から次の都市へのショートカットを作成する。

下限値を改善するには、オイラーグラフを作成するより良い方法が必要です。三角不等式により、最適なオイラーグラフは最適な巡回セールスマンツアーと同じコストを持つ必要があります。したがって、最適なオイラーグラフを見つけることは、TSP と同程度に困難です。これを行う 1 つの方法は、複雑度が のアルゴリズムを使用して最小重みマッチングを行うことです。${\displaystyle O(n^{3})}$[ ^{6 ]​}

グラフをオイラーグラフにするには、まず最小全域木から始めます。次に、奇数次の頂点をすべて偶数にする必要があります。そのため、奇数次の頂点のマッチングを追加し、すべての奇数次の頂点の次数を 1 増やします。^{[ 6 ]}これにより、すべての頂点の次数が偶数になるグラフが得られ、これはオイラーグラフとなります。上記の方法を適用すると、Christofides と Serdyukov のアルゴリズムが得られます。

1. この問題に対する最小全域木を求めなさい。
2. 奇数個の都市の集合を用いて、この問題のマッチング問題を作成してください。
3. このグラフのオイラー路を求めなさい。
4. ショートカットを使用してTSPに変換します。

ペアワイズ交換

ペアワイズ交換法、または2-opt法は、2つのエッジを繰り返し削除し、それらを2つの異なるエッジで置き換えて、エッジ削除によって生じた断片を再接続し、より短い新しい巡回路を形成する手法です。同様に、3-opt法は3つのエッジを削除し、それらを再接続してより短い巡回路を形成します。これらはk -opt法の特殊なケースです。Lin -Kernighanという名称は、2-opt法の誤称としてよく耳にしますが、実際にはLin-Kernighan法はより一般的なk -opt法です。

ユークリッド空間のインスタンスの場合、2-optヒューリスティックは平均してクリストフィデスのアルゴリズムよりも約5%優れた解を与えます。貪欲アルゴリズムで得られた初期解から始めると、平均移動回数は再び大幅に減少し、${\displaystyle O(n)}$ただし、ランダムスタートの場合、平均移動回数は${\displaystyle O(n\log(n))}$⁠。これはサイズの増加としては小さいものの、小さな問題の場合、ランダムスタートの初期移動回数は、貪欲ヒューリスティックから開始した場合と比較して 10 倍になります。これは、このような 2-opt ヒューリスティックが、交差などのソリューションの「悪い」部分を利用するためです。このようなタイプのヒューリスティックは、車両経路問題のヒューリスティック内で、経路ソリューションを再最適化するためによく使用されます。 ^{[ 30 ]}

アリコロニー最適化

人工知能研究者のマルコ・ドリゴは1993年に、 ACS（アリコロニーシステム）と呼ばれるアリコロニーのシミュレーションを使用してTSPの「良い解」をヒューリスティックに生成する方法を説明した。 ^{[ 37 ]}これは、実際のアリが食料源と巣の間の最短経路を見つける行動をモデル化しており、各アリが他のアリによって残された道しるべフェロモンに従うことを好むことから生じる創発的な行動である。

ACSは、マップ上の多数の仮想アリエージェントを送り出し、様々な経路を探索させます。各アリは、都市までの距離と、その都市への境界線上に堆積された仮想フェロモンの量を組み合わせたヒューリスティックに基づいて、次に訪れる都市を確率的に選択します。アリは探索を続け、通過する境界線ごとにフェロモンを堆積させ、すべてのアリがツアーを完了するまで続けます。この時点で、最短のツアーを完了したアリが、完了したツアー経路に沿って仮想フェロモンを堆積させます（グローバルトレイル更新）。堆積されるフェロモンの量はツアーの長さに反比例します。つまり、ツアーが短いほど、堆積されるフェロモンの量が多くなります。

メトリックTSP（デルタTSPまたはΔ-TSPとも呼ばれる）では、都市間の距離は三角不等式を満たします。

TSPの非常に自然な制約は、都市間の距離が三角不等式を満たすような距離を形成することを要求することです。つまり、AからBへの直接接続は、中間地点Cを経由する経路よりも決して遠くならないということです。

${\displaystyle d_{AB}\leq d_{AC}+d_{CB}}$。

すると、辺は頂点の集合上に距離関数を構築する。都市を平面上の点とみなすと、多くの自然な距離関数が距離関数となるため、多くの自然なTSP（巡回セールスマン問題）の事例がこの制約を満たす。

以下に、さまざまな指標に対するメトリックTSPの例をいくつか示します。

• ユークリッドTSP（下記参照）では、2つの都市間の距離は、対応する点間のユークリッド距離です。
• 直線型TSPでは、2つの都市間の距離は、それぞれのx座標とy座標の差の絶対値の合計で表されます。この距離は、マンハッタン距離またはシティブロック距離と呼ばれることがよくあります。
• 最大距離法では、2点間の距離は、それらのx座標とy座標の差の絶対値の最大値となる。

最後の2つの指標は、例えば、プリント基板に所定の穴をあける機械の経路設計などに用いられます。マンハッタン距離は、まず一方の座標を調整し、次に他方の座標を調整する機械に対応し、新しい点への移動時間は両方の移動時間の合計となります。最大距離は、両方の座標を同時に調整する機械に対応し、新しい点への移動時間は、2つの移動のうち遅い方となります。

TSPの定義では、都市を2回訪問することは許可されていませんが、多くのアプリケーションではこの制約は必要ありません。そのような場合、対称的で非メトリックなインスタンスをメトリックなインスタンスに縮小できます。これにより、元のグラフが都市間の距離が完全なグラフに置き換えられます。${\displaystyle d_{AB}}$は、元のグラフにおけるAとB間の最短経路長に置き換えられます。

ユークリッド平面上の点の場合、巡回セールスマン問題の最適解は、すべての点を通る単純な多角形、つまり点の多角形化を形成します。 ^{[ 38 ]}交差のある非最適解は、局所最適化によって交差のないより短い解にすることができます。ユークリッド距離は三角不等式に従うため、ユークリッドTSPはメトリックTSPの特殊なケースを形成します。しかし、入力点が整数座標を持つ場合でも、それらの距離は一般に平方根の形をとり、ツアーの長さは根号の和となるため、異なるツアーの長さを正確に比較するために必要な記号計算を実行することは困難です。

一般的な TSP と同様に、正確なユークリッド TSP は NP 困難ですが、根号の和の問題が、決定バージョンが NP に属し、したがって NP 完全であることを証明する際の障害となっています。距離を整数に丸めた問題の離散化バージョンは NP 完全です。^{[ 39 ]}有理座標と実際のユークリッド距離では、ユークリッド TSP はPSPACEのサブクラスである計数階層^{[ 40 ]}に属することが知られています。任意の実座標では、可能な入力が非可算個あるため、ユークリッド TSP はそのようなクラスには属せません。これらの複雑さにもかかわらず、ユークリッド TSP は、一般的な距離の場合よりも近似がはるかに容易です。^{[ 41 ]}例えば、ユークリッドTSPのインスタンスに関連付けられたグラフの最小全域木はユークリッド最小全域木であり、 n個の点（エッジの数よりかなり少ない）に対して期待されるO ( n log n )の時間で計算できます。これにより、上記の三角不等式を持つTSPの単純な2近似アルゴリズムがより高速に動作します。

一般に、任意のc > 0 に対して、dはユークリッド空間の次元数であるが、TSP の幾何学的インスタンスに対して、最適値の最大 (1 + 1/ c ) 倍の長さのツアーを見つける多項式時間アルゴリズムが存在する。

${\displaystyle O{\left(n(\log n)^{O(c{\sqrt {d}})^{d-1}}\right)}}$

時間。これは多項式時間近似スキーム（PTAS）と呼ばれます。^{[ 42 ]} Sanjeev AroraとJoseph SB Mitchellは、ユークリッドTSPのPTASを同時に発見した功績により、2010年にゲーデル賞を受賞しました。

実際には、より単純な、保証の弱いヒューリスティックが引き続き使用されている。

ほとんどの場合、TSPネットワーク内の2つのノード間の距離は両方向で同じです。AからBまでの距離とBからAまでの距離が等しくない場合を非対称TSPと呼びます。非対称TSPの実用的な応用例としては、道路レベルのルーティング（一方通行、スリップロード、高速道路などによって非対称になる）を用いた経路最適化が挙げられます。

スタッカークレーン問題は、非対称TSPの特殊なケースと見なすことができます。この問題では、入力は距離空間内の点の順序付きペアで構成され、ツアーはこれらのペアを順番に訪問する必要があります。これらの点のペアは、非対称TSPのノードと見なすことができ、非対称な距離は、ペアの最初の点から2番目の点まで、そして2番目の点から次のペアの最初の点まで移動する際のコストの合計を反映しています。

幾何学的測度論には、次のような類似の問題があります。ユークリッド空間の部分集合Eが可測曲線に含まれるのはどのような条件下でしょうか（つまり、 Eのすべての点を通る有限長の曲線が存在するのはどのような場合でしょうか）？この問題は、アナリストの巡回セールスマン問題として知られています。

仮定する${\displaystyle X_{1},\ldots ,X_{n}}$は${\displaystyle n}$正方形内の一様分布を持つ独立な確率変数${\displaystyle [0,1]^{2}}$、そして${\displaystyle L_{n}^{\ast }}$通常のユークリッド距離に従って、この点^の集合に対する最短経路長（つまりTSP解）となる^。ほぼ確実^に、

${\displaystyle {\frac {L_{n}^{*}}{\sqrt {n}}}\rightarrow \beta \qquad {\text{when }}n\to \infty ,}$

どこ${\displaystyle \beta }$は明示的には不明な正の定数です。${\displaystyle L_{n}^{*}\leq 2{\sqrt {n}}+2}$（下記参照）有界収束定理から、${\displaystyle \beta =\lim _{n\to \infty }\mathbb {E} [L_{n}^{*}]/{\sqrt {n}}}$したがって、下限と上限は${\displaystyle \beta }$境界から追従する${\displaystyle \mathbb {E} [L_{n}^{*}]}$。

ほぼ確実な限界${\displaystyle {\frac {L_{n}^{*}}{\sqrt {n}}}\rightarrow \beta }$として${\displaystyle n\to \infty }$独立した場所が存在しない場合${\displaystyle X_{1},\ldots ,X_{n}}$は、一様な周辺分布を持つ定常エルゴード過程からの観測値に置き換えられます。^{[ 44 ]}

一般的には、最短巡回セールスマンツアーを見つけることはNPO完全です。^{[ 52 ]}距離尺度がメトリック(したがって対称) である場合、問題はAPX完全になります。 ^{[ 53 ]} Christofides と Serdyukov のアルゴリズムは、 1.5以内で近似します。^{[ 54 ] [ 55 ] [ 10 ]}

距離が 1 と 2 に制限されている場合 (ただし、依然として距離尺度である場合)、近似比は 8/7 になります。^{[ 56 ]}三角不等式を伴う非対称ケースでは、2018 年に Svensson、Tarnawski、および Végh によって定数係数近似が開発されました。^{[ 57 ]} Vera TraubとJens Vygenによるアルゴリズムは、パフォーマンス比を達成しています。${\displaystyle 22+\varepsilon }$[ ^{58 ]}この要素はさらに改善され^、${\displaystyle 17+\varepsilon }$[ ^{59 ]} 最もよく知られている近似不可能性の限界は 75/74 です^{。[ 60 ]}

対応する最長巡回セールスマンツアーの最大化問題は、63/38 の精度で近似可能です。 ^{[ 61 ]}距離関数が対称であれば、最長ツアーは決定論的アルゴリズムによって 4/3 の精度で近似でき、^{[ 62 ]}および${\displaystyle (33+\varepsilon )/25}$ランダム化アルゴリズムによって。^{[ 63 ]}