歴代の巡回セールスマン問題の歴史を簡潔に箇条書きにすると？
巡回セールスマン問題の起源は不明なのだ。1832年に出版された巡回セールスマンのためのハンドブックには、この問題に言及し、ドイツとスイスのツアーの例が掲載されているが、数学的な処理は含まれていない。


ウィリアム・ローワン・ハミルトン
TSPは、19世紀にアイルランドの数学者William Rowan Hamiltonとイギリスの数学者Thomas Kirkmanによって数学的に定式化されました。ハミルトンのイコシアンゲームは、ハミルトンサイクルを見つけることに基づくレクリエーションパズルだった。TSPの一般形は、1930年代にウィーンとハーバード大学の数学者によって最初に研究されたようで、特にカール・メンガーは問題を定義し、明白な総当りアルゴリズムを検討し、最近傍発見的なヒューリスティックの非最適性を観察している：

対の距離がわかっている有限個の地点について、その地点を結ぶ最短経路を求める問題を、メッセンジャー問題と呼ぶ（実際には、この問題は各郵便配達人が解決すべきであり、また、多くの旅行者が解決すべきであると考えられるから）。もちろん、この問題は有限回の試行によって解くことができる。試行回数が、与えられた地点の順列の数以下になるようなルールは知られていない。まず出発点から最も近い点に行き、次にこれに最も近い点に行く、などというルールは、一般に最短経路を導き出さない。

1930年代にスクールバスの経路問題を解決しようとしていたMerrill M. Floodによって初めて数学的に考察された。プリンストン大学のHassler Whitneyが「48州問題」と呼ぶこの問題に興味を持たせた。巡回セールスマン問題」という言葉を使った最も古い出版物は、ジュリア・ロビンソンによる1949年のランド・コーポレーションの報告書「ハミルトニアン・ゲーム（巡回セールスマン問題）について」なのだ。

1950年代から1960年代にかけて、サンタモニカのランド研究所がこの問題を解くと賞金が出るというキャンペーンを行ったことから、欧米の科学界でこの問題の人気が高まった。 注目すべきはランド研究所のジョージ・ダンツィグ、デルバート・レイ・フルカーソン、セルマー・M・ジョンソンの貢献で、問題を整数線形計画として表現し、その解法を切断面法で開発。この新しい手法で、49の都市を持つインスタンスを最適に解き、ツアーを構築し、それよりも短いツアーが存在しないことを証明したのなのだ。しかし、Dantzig、Fulkerson、Johnsonは、最適解に近い解があれば、少数の不等式（カット）を追加することで最適解を見つけたり、最適性を証明できるかもしれないと考えた。彼らは、このアイデアを用いて、文字列モデルを用いて最初の49都市問題を解いた。その結果、49都市問題の解を得るために必要なカット数はわずか26個であることがわかった。この論文はTSP問題に対するアルゴリズム的なアプローチを与えるものではありませんでしたが、この論文にあるアイデアは、後にTSPの厳密解法を作り出すのに不可欠なものでした。切断面法だけでなく、Dantzig、Fulkerson、Johnsonは、おそらく初めて分岐・境界アルゴリズムも使用しました。

1959年、ジリアン・ビアードウッド、J.H.ハルトン、ジョン・ハマースリーは、ケンブリッジ哲学協会の雑誌に「The Shortest Path Through Many Points」という論文を発表した。 ベアードウッド-ハルトン-ハマースリーの定理は、巡回セールスマン問題に対する実用解となる。著者らは、自宅や事務所を出発し、一定数の場所を訪問してから出発地点に戻るセールスマンの最短経路の長さを決定する漸近公式を導きました。

その後、数学、コンピュータサイエンス、化学、物理学など、多くの研究者によってこの問題は研究されてきた。しかし、1960年代になると、最適解を求めるのではなく、長さが最適解の倍数に証明的に束縛される解を生成することで、問題の下界を作り、この下界を枝打ちや境界のアプローチに利用する新しいアプローチが生み出された。この方法の一つは、グラフの最小スパニングツリーを作成し、そのすべての辺を2倍にすることで、最適なツアーの長さは最小スパニングツリーの重量の最大2倍であるという境界を作り出すものであった。

1976年，ChristofidesとSerdyukovは，互いに独立して，この方向で大きな進歩を遂げた： Christofides-Serdyukovアルゴリズムは，最悪の場合，最適解より最大1.5倍長い解をもたらす。このアルゴリズムは単純かつ迅速であったため、多くの人が最適解に近い解法が得られると期待した。しかし、この改善への期待はすぐには実現せず、2011年に「グラフィカル」TSPのサブセットに対して（非常に）わずかに改善された近似アルゴリズムが開発されるまで、Christofides-Serdyukovは最悪のシナリオを持つ手法のままでした。2020年にこの小さな改善が完全（メートル）TSPに拡張されました。

Richard M. Karpは1972年、ハミルトンサイクル問題がNP完全であることを示し、TSPのNP困難性を示唆した。これにより、最適なツアーを見つけることが計算上困難であることを数学的に説明することができた。

1970年代後半から1980年にかけて、Grötschel、Padberg、Rinaldiらが、切断平面とbranch and boundを用いて、最大2,392都市を持つインスタンスを正確に解くことに成功し、大きな進歩をとげた。

1990年代、Applegate、Bixby、Chvátal、Cookが開発したプログラムConcordeは、最近の多くの記録解に使用されている。1991年にはGerhard Reineltが難易度の異なるベンチマークインスタンスを集めたTSPLIBを発表し、多くの研究グループが結果を比較するために使用している。2006年、Cookらはマイクロチップのレイアウト問題で与えられる85,900都市のインスタンスで最適なツアーを計算し、現在TSPLIBで最も大きな解を得たインスタンスとなった。数百万の都市を持つ他の多くのインスタンスでは、最適ツアーの2-3%以内が保証される解を見つけることができる。
* 19世紀、アイルランドの数学者ウィリアム・ローワン・ハミルトンとイギリスの数学者トーマス・カークマンによって初めて数学的に定式化されるなのだ。
* 1930年代 - ウィーンの数学者とハーバード大学で初めて研究され、特にカール・メンガーとメリル・M・フラッドがスクールバスの経路問題を解決するために研究したのだ。
* 1959年 - ジリアン・ビアードウッド、J.H.ハルトン、ジョン・ハマースリーが、ケンブリッジ哲学協会誌に「The Shortest Path Through Many Points」と題する論文を発表し、最初の実用的な解決策を提供するのだ。
* 1960年代 - 新しいアプローチで、長さが最適長さの倍数で証明可能な解を生成なのだ。
* 1972年 - リチャード・M・カープがハミルトンサイクル問題がNP完全であることを示し、巡回セールスマン問題がNP困難であることを示唆するのだ。
* 1976年 - ChristofidesとSerdyukovがそれぞれ新しいアルゴリズムを考案し、最悪の場合、最適解の1.5倍以上の長さの解を得るなのだ。
* 1990年代 - Applegate, Bixby, Chvátal, and Cookは、最近の多くの記録解に使用されているプログラムConcordeを開発したのだ。
* 1991年 - Gerhard ReineltがTSPLIBを発表、様々な難易度のベンチマークインスタンス集で、多くの研究グループによって結果比較に利用されている
* 2006年 - マイクロチップレイアウト問題で与えられる85,900都市のインスタンスで、現在TSPLIBで最大の解を持つインスタンスで最適なツアーを計算したのだ。
* 2011年 - グラフィカルな巡回セールスマン問題の部分集合に対して、わずかに改良された近似アルゴリズムが開発されるなのだ。
* 2020年 - 「グラフィカル」巡回セールスマン問題のサブセットで開発された近似アルゴリズムが、完全な巡回セールスマン問題をカバーするように拡張されるなのだ。