旅行推銷員問題問的是：有沒有一條最短的封閉路線，能剛好造訪每一個輸入點一次，再回到起點——而它在實務上能給出的最佳解，是一種確定性的、經過局部改善的啟發式解法，而不是一個全域最佳解。Traveling Salesman Solver 建構出來的正是這種答案：它接受 3 到 50 個具名的 (x, y) 座標，先跑一次最近鄰演算法，產生一條初始路線，接著反覆套用 2-opt 邊交換，直到再也無法改善為止。輸出面板會把最初的最近鄰距離，跟改善後的距離並排顯示出來，並計算套用了幾次 2-opt 迭代，因此區域搜尋帶來的收益是看得見的，而不是被隱藏起來。因為路由問題是 NP-困難的，目前沒有已知的多項式時間演算法，能對任意輸入回傳保證最短的路線，任何宣稱做得到這一點的工具，都是誇大了它實際的能力。這個頁面刻意把這套啟發式演算法限制在可控且可檢視的範圍內，固定用第一筆輸入資料當作起點，因此用同一份資料重複執行，會得到同樣的答案。
「最佳解」對旅行推銷員問題來說代表什麼
旅行推銷員問題是一個經典問題：給定一組點以及它們之間的距離，找出一條最短的封閉巡迴路線，恰好造訪每一個點一次，再回到起點。對於非常小的輸入，你可以把每一種排列都列舉出來，選出最小值，但對於實務上的輸入來說，這種暴力法會完全撐不住，因為可能的巡迴路線數量，會隨著點的數量呈階乘成長。TSP 同時也是 NP-困難的，這代表沒有任何已知的演算法，能保證在多項式時間內，把每一個實例都解到最佳。Google OR-Tools describes the same routing objective 在它的路由文件中描述了同樣的路由目標，並指出實務上的求解器，在困難的輸入上可能會回傳非最佳的結果。因此，正式環境中的路由系統，會使用專門的求解器、分支界限法、整數規劃，或是針對特定問題形態調校過的限制式方法。一個以教學與檢視為目標的網頁工具，做的是不一樣的事：它給你的是一套清楚、確定性的啟發式方法，而不是一個黑盒子式的最佳解宣稱。了解這個區別，能讓你為正確的任務挑選正確的工具。
求解器接受哪些輸入，又拒絕哪些輸入
Traveling Salesman Solver 接受一份 3 到 50 組具名座標對的清單，每行一組，格式是 name, x, y。第一行會被當成固定的起始位置，這條巡迴路線最後也一定會回到這裡。名稱不能包含逗號，因為逗號是欄位分隔符號，而座標必須是落在求解器可接受範圍內的有限數值。重複的座標會被拒絕：兩個不同的名稱如果放在完全相同的位置上，會讓路線變得含糊不清，因為這個工具無法判斷你原本想要的排序是哪一種。50 個點的上限，是一個實務上的安全防線，用來讓區域搜尋維持反應靈敏，因為 2-opt 每一輪的計算量，會隨點數呈平方成長。任何不符合這些規則的輸入，都會在求解器執行之前就被拒絕，因此你得到的會是一則清楚的驗證訊息，而不是一條有誤導性的路線。
| 輸入元素 | 要求 |
|---|---|
| 點的數量 | 3 到 50（含頭尾） |
| 每行欄位 | name, x, y（以逗號分隔） |
| 名稱字元 | 不允許包含逗號 |
| 座標 | 有限、有界的平面數值 |
| 起點 | 永遠是第一行 |
| 重複的座標 | 拒絕 |
| 緯度與經度 | 目前不支援直接使用 |
三個步驟，跑出一條封閉巡迴路線
- 把每一個地點各自一行，寫成 name, x, y。把你希望路線起點與終點所在的那個地點，放在第一行。請使用兩軸單位一致的座標系統：不論是本地繪圖用的公尺、版面配置用的像素，或是課堂上不帶單位的數值，都可以。
- 執行求解器，建構出這條巡迴路線。結果面板會列出一條恰好造訪每個點一次、再回到起點的封閉名稱序列，最初的最近鄰距離、經過 2-opt 改善後的距離，以及套用了多少次 2-opt 迭代。
- 比較這兩個距離，看看區域搜尋把路線縮短了多少，檢查名稱的順序，如果直線歐幾里得距離符合你的任務需求，就複製這條封閉序列。
最近鄰與 2-opt 如何算出這個數字
這個求解器建立在兩種廣為理解的 TSP 啟發式方法之上，它們都是教科書中的標準做法，也是 Croes 1958 年那篇關於 2-opt 的論文中所使用的方法。建構過程從第一個輸入點開始。在每一步，最近鄰演算法會挑選出到目前巡迴路線末端歐幾里得距離最小的未造訪點，其中距離用直線公式 sqrt((x2 − x1)² + (y2 − y1)²) 計算。如果有兩個候選點距離完全相等，就以它在你輸入順序中較早出現的那個獲勝，這樣才能維持結果的確定性。一旦完整的巡迴路線建立起來，2-opt 就會掃描每一對邊。針對每一對邊，它會考慮把它們之間的那一段路線反轉，重新連接起來。如果反轉之後，總距離確實縮短了，這次交換就會被套用，並從第一條邊重新開始掃描。這個過程會持續，直到一次完整掃描找不到任何能改善結果的交換為止，或是達到一個防呆用的迭代上限。回傳的巡迴路線，在雙邊交換的意義下是區域最佳解，這相較於原始的最近鄰結果是有意義的改善，但並不保證是全域最佳解。
以四個點來看一個實際範例：A (0, 0)、B (4, 0)、C (4, 3)、D (0, 3)，以 A 作為起點。從 A 出發，最近的未造訪點是 D，距離是 sqrt((0 − 0)² + (3 − 0)²) = sqrt(9) = 3。從 D 出發，最近的未造訪點是 C，距離是 sqrt((4 − 0)² + (3 − 3)²) = sqrt(16) = 4。從 C 出發，最近的未造訪點是 B，距離是 sqrt((4 − 4)² + (0 − 3)²) = sqrt(9) = 3。從 B 回到 A 的距離是 sqrt((0 − 4)² + (0 − 0)²) = sqrt(16) = 4。最近鄰的總距離是 3 + 4 + 3 + 4 = 14。對這個特定的矩形來說，最近鄰演算法碰巧還原出了真正的周長（2 × (4 + 3) = 14），因此經過 2-opt 改善後的距離，會等於最初的距離，沒有任何有用的交換可以進行。在有交叉的較複雜幾何形狀上，2-opt 通常會進一步縮短路線。
| 幾何形狀 | 典型的 2-opt 表現 |
|---|---|
| 三角形（3 個點） | 沒有任何交換能縮短周長；改善後的結果等於最初的結果。 |
| 正方形或矩形 | 如果最近鄰演算法已經沿著周長走了一圈，通常就不需要任何交換。 |
| 共線的點 | 消除交叉，還原出一條乾淨的線性掃描路徑，並移除繞路。 |
| 中心點加上一圈環繞點 | 反轉來回的路徑，通常能省下最初距離中相當可觀的一部分。 |
解讀初始距離、改善後距離，以及 2-opt 迭代次數
這個輸出面板的結構，讓這套啟發式方法變得可稽核，而不是一個黑盒子。有三個數字，承載了大部分的意義。初始距離，是最近鄰演算法在沒有經過任何區域搜尋處理之前，單靠自己算出來的結果。改善後距離，是 2-opt 最終得到的結果，依照建構方式，它永遠會小於或等於初始距離，因為每一次被接受的交換，都必須確實縮短總距離。迭代次數，告訴你這個迴圈在跑出一次沒有任何可改善交換的完整掃描之前，總共需要多少次完整掃描。在一個小輸入上出現很高的迭代次數，通常代表這份輸入原本有交叉，需要好幾輪掃描才能理清；而較低的迭代次數，則通常代表最近鄰算出來的巡迴路線，本來就已經很接近一個區域最小值。如果這兩個距離相等，代表 2-opt 在你的資料上沒有做出任何有用的交換，這在非常小的實例上，或是最近鄰演算法本來就排得不錯的輸入上，是很常見的情況。用同一份輸入再跑一次，會得到完全相同的結果，因為第一行被固定為起點，而完全相等的情況，也會保留它們原本的順序。
為什麼你不該在這裡貼上緯度與經度
這個求解器把座標當成平坦的平面數值來處理，而不是球面上的度數。這一點很重要，因為以十進位度數表示的兩個點之間的歐幾里得距離，只是真實地球距離的粗略近似值，而且離兩極越近，或是你涵蓋的區域越大，這個近似值就會越不準確。跨越大陸或大洋的範圍時，這種扭曲會非常嚴重，而跨越國際換日線時，方向甚至可能完全反過來。如果你需要一條在地球表面上、真實世界的旅行推銷員路線，請先把你的點投影到一個本地座標系統上（舉例來說，一個 UTM 分區），或是改用一個能處理大地測量距離，以及實際道路或交通網路的路由服務。把像素、毫米，或課堂上不帶單位的數值，當成公尺來處理，同樣也會出錯，但至少這種誤差是均勻的，你可以在兩軸上選定一個一致的比例。不論哪一種情況，根本的限制都是一樣的：這個工具假設的是一個平坦的二維平面，x 與 y 使用同樣的單位，因此點與點之間的直線線段，只是幾何上的線段，並不是關於道路或行車時間的主張。
這個工具適合的任務，以及不適合的任務
當你想學習最近鄰與 2-opt 在一個你自己畫得出來的小輸入上如何運作、想在一份本地繪圖上草擬一條候選的巡檢順序、想為你正在寫的路由演算法產生可重現的測試夾具，或是想實驗一下起點的選擇會如何改變一條區域最佳的巡迴路線時，Traveling Salesman Solver 都很適合。對於在具名點上進行的相關組合最佳化工作，minimum spanning tree guide 涵蓋的是同一種輸入形式下、連接成本版本的問題。當你需要保證最佳、能用於成本承諾或派工的路由，當你需要遵守像單行道、時間窗口、車輛容量、多位駕駛、交通狀況，或障礙物這類真實世界的限制條件，或是當底層的距離應該是道路網路上的行車時間、而不是直線歐幾里得距離時，這個求解器就不適合。這個求解器不會呼叫任何外部地圖 API，因此不會有付費請求，也不會有任何位置資料離開你的瀏覽器，但這也代表它不可能知道兩個座標之間實際有沒有道路。對於那類工作，請改用一個經過驗證、使用真實路網距離或時間矩陣的求解器，並獨立驗證這條路線，而不要把一個本地端的近似值，當成具備營運上的權威性。
如果想更深入了解，可以參考 Assignment Problem Solver Online: Hungarian Algorithm。