巡回セールスマン問題の歴史を箇条書きにすると？
巡回セールスマン問題の起源は不明である。1832年に出版された巡回セールスマンのためのハンドブックには、この問題が記載され、ドイツとスイスのツアーの例が掲載されているが、数学的な扱いはない。


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

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

これは1930年代に、スクールバスの経路問題を解決しようとしていたメリル・M・フラッドによって初めて数学的に考察された。プリンストン大学のハスラー・ホイットニーがこの問題に興味を持ち、彼は「48州問題」と呼んだ。巡回セールスマン問題」という言葉を使った最も古い出版物は、ジュリア・ロビンソンによる1949年のランド・コーポレーションの報告書 "On the Hamiltonian game (a traveling salesman problem) "である。

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

1959年、Jillian Beardwood、J.H. Halton、John Hammersleyの3人は、ケンブリッジ哲学協会誌に "The Shortest Path Through Many Points "という論文を発表した。Beardwood-Halton-Hammersleyの定理は巡回セールスマン問題の実用的な解を提供するものである。著者らは、自宅や事務所を出発点とし、出発点に戻るまでに一定数の場所を訪問するセールスマンの最短経路の長さを決定する漸近公式を導出した。

その後数十年間、この問題は数学、コンピュータサイエンス、化学、物理学などの多くの研究者によって研究された。しかし1960年代になると、最適解を求める代わりに、最適解の長さの倍数で証明可能な長さの解を作り出すという新しいアプローチが生み出された。この方法のひとつは、グラフの最小スパニング木を作り、そのすべての辺を2倍にすることで、最適なツアーの長さは最小スパニング木の重さの最大2倍であるという境界が得られる。

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

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

1970年代後半から1980年にかけて大きな進展があり、グレッチェル、パドベルグ、リナルディらが、切断平面と分岐と束縛を用いて、最大2,392都市のインスタンスを正確に解くことに成功した。

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