簡要列出旅行商問題在歷史上的發展史，以簡短的專案符號列表形式呈現。
旅行商問題的起源不清楚。1832年一本旅行推銷員手冊提到了這個問題，幷包括了透過德國和瑞士的示例旅遊，但沒有數學處理。

愛爾蘭數學家威廉·羅恩·哈密頓和英國數學家託馬斯·柯克曼在19世紀對TSP進行了數學公式化。哈密頓的icosian遊戲是一個基於尋找哈密頓迴路的娛樂難題。TSP的一般形式似乎是在20世紀30年代由維也納和哈佛的數學家首次研究的，特別是由Karl Menger定義了這個問題，考慮了顯而易見的暴力演演算法，並觀察到最近鄰啟發式的非最優性：

我們稱之為信使問題（因為在實踐中，每個郵遞員都應該解決這個問題，也由許多旅行者解決），即為有限數量的已知其兩兩距離的點找到連線這些點的最短路徑。當然，這個問題可以透過有限次試驗來解決。不知道能否制定規則，將試驗次數降低到給定點的排列數以下。通常情況下，首先從起點到最近的點，然後到最近的點，以此類推，不一定會得到最短路徑。

它在20世紀30年代首次被Merrill M. Flood數學地考慮，他正在尋找解決學校巴士路線問題的方法。普林斯頓大學的Hassler Whitney引起了人們對這個問題的興趣，他稱之為「48個州的問題」。使用短語「旅行推銷員問題」的最早出版物是1949年Julia Robinson的RAND公司報告，「關於哈密頓遊戲（旅行推銷員問題）」。

在20世紀50年代和60年代，該問題在歐洲和美國的科學界越來越受歡迎，因為Santa Monica的RAND公司提供瞭解決該問題的獎勵。來自RAND公司的George Dantzig、Delbert Ray Fulkerson和Selmer M. Johnson表達了問題的整數線性規劃，並開發了割平面法來解決它。他們寫了一篇被認為是該主題的開創性論文，在這篇論文中，他們使用這些新方法透過構建一條旅遊路線並證明沒有其他旅遊路線可以更短來解決了一個包含49個城市的例項。但是，Dantzig、Fulkerson和Johnson推測，如果給出一個近似最優解，我們可以透過新增少量的額外不等式（割）來找到最優解或證明最優解。他們使用這個想法透過一個字串模型來解決他們的最初的49個城市問題。他們發現只需要26個割就可以得出他們的49個城市問題的解。雖然這篇論文沒有給出TSP問題的演演算法方法，但其中的思想對於後來建立TSP的精確解決方法是不可或缺的，儘管需要15年時間才能找到一種演演算法方法來建立這些割。除了割平面法外，Dantzig、Fulkerson和Johnson還首次使用了分支定界演演算法。

1959年，Jillian Beardwood、J.H. Halton和John Hammersley在劍橋哲學學會的期刊上發表了一篇名為「穿過許多點的最短路徑」的文章。Beardwood-Halton-Hammersley定理為旅行推銷員問題提供了實用的解決方案。作者推導出了一個漸近公式，以確定從家或辦公室出發並在訪問固定數量的位置後返回起點的推銷員的最短路徑長度。

在接下來的幾十年中，該問題被許多來自數學、電腦科學、化學、物理和其他科學領域的研究人員研究。然而，在20世紀60年代，創造了一種新的方法，該方法不是尋求最優解，而是產生一個長度可證明為最優長度的解，並在此過程中為問題建立下限；然後將這些下限與分支定界方法一起使用。其中一種方法是建立圖的最小產生樹，然後將其所有邊加倍，這產生了最優旅遊路線長度不超過最小產生樹權重的兩倍的界限。

1976年，Christofides和Serdyukov獨立地在這個方向上取得了重大進展：Christofides-Serdyukov演演算法產生了一個解，最壞情況下比最優解長1.5倍。由於該演演算法簡單快速，許多人希望它能夠為近似最優解方法讓路。然而，這種改進的希望並沒有立即實現，Christofides-Serdyukov仍然是最佳最壞情況的方法，直到2011年，當時為「圖形」TSP的子集開發了（非常）稍微改進的近似演演算法。在2020年，這種微小的改進被擴充套件到了完整的（度量）TSP。

Richard M. Karp在1972年表明哈密頓迴路問題是NP完全的，這意味著TSP的NP難度。這為尋找最優路線的表面計算難度提供了數學解釋。

在20世紀70年代末和80年代，Grötschel、Padberg、Rinaldi等人透過割平面和分支定界成功地解決了多達2,392個城市的例項。

在1990年代，Applegate、Bixby、Chvátal和Cook開發了Concorde程式，該程式已用於許多最近的記錄解決方案。Gerhard Reinelt在1991年釋出了TSPLIB，這是一個難度各異的基準例項集合，許多研究小組用於比較結果。在2006年，Cook等人透過微晶片佈局問題給出了一個85,900個城市例項的最優路線，目前是已解決的最大TSPLIB例項。對於許多其他具有數百萬個城市的例項，可以找到保證在最優路線的2-3％之內的解決方案。
* 19 世紀 - 由愛爾蘭數學家 William Rowan Hamilton 和英國數學家 Thomas Kirkman 首次用數學公式表述
* 1930 年代 - 首先由維也納和哈佛大學的數學家進行研究，最著名的是 Karl Menger 和 Merill M. Flood，他們正在尋求解決校車路線問題。
* 1959 - 吉莉安·比爾德伍德，J.H.霍爾頓和約翰·哈默斯利在劍橋哲學會期刊上發表了題為“The Shortest Path Through Many Points”的文章，提供了第一個實用的解決方案。
* 20 世紀 60 年代 - 建立了新方法，該方法產生的解決方案的長度可證明以最佳長度的倍數為界。
* 1972 - Richard M. Karp 證明哈密頓迴圈問題是 NP 完全的，這意味著旅行商問題的 NP 難度。
* 1976 - Christofides 和 Serdyukov 獨立發明瞭新演算法，該演算法產生的解決方案在最壞情況下最多比最優解決方案長 1.5 倍。
* 20 世紀 90 年代 - Applegate、Bixby、Chvátal 和 Cook 開發了 Concorde 程式，該程式已在許多最近的記錄解決方案中使用。
* 1991 - Gerhard Reinelt 發布了 TSPLIB，這是不同難度的基準例項集合，已被許多研究小組用來比較結果
* 2006 年 - Cook 和其他人透過微晶片佈局問題給出的 85,900 個城市例項計算出最佳遊覽，這是目前已解決的最大的 TSPLIB 例項。
* 2011 - 針對“圖形”旅行商問題的子集開發了略微改進的近似演算法。
* 2020 - 為“圖形”子集開發的略有改進的近似演算法擴充套件到涵蓋完整的旅行商問題。