基于流水算法的旅行商問題求解

,

(1.天津商業大學 商學院，天津 300134； 2.天津商業大學 管理創新與評價研究中心，天津 300134)

1 引言

旅行商問題(Traveling Salesman Problem，簡稱TSP)又稱為旅行推銷員問題、貨郎擔問題，最早于1859年由威廉·漢密爾頓首次提出，屬于運籌學中經典的組合優化難題。該問題是單一旅行者由起點出發，不重復地走完其余地點并回到原出發點，在所有可能的路徑中求出路徑長度最短的一條。旅行商問題屬于組合優化范疇，是NP-hard問題，具有組合優化問題的典型特征，并且問題描述簡單，因此很多學者將旅行商問題算例作為算法研究的公共實例。同時，旅行商問題有著廣泛的實際應用背景，如物流配送、調度排班、道路交通、計算機網絡節點配置、生產調度、組合優化求極值等問題。所以，旅行商問題成為優化領域里的研究熱點，吸引了管理優化、運籌學、數學、物理、生物和人工智能等領域的研究者的關注。

TSP問題的解空間是多維、多局部極值、復雜的解空間。這個解空間類似一個無窮大的丘陵地帶，山峰、山谷連綿起伏，其中的山谷就代表局部極低值，最低的山谷代表最短路徑，對應的方案就是最佳旅行方案。旅行商問題的求解方法大體可以分為兩類：精確求解法和近似求解法。精確求解法主要是通過解析方法求得最優解，包括枚舉法、分枝定界法、動態規劃等。旅行商問題描述雖然非常簡單，但隨著需要訪問城市數目的增加，會出現所謂的“組合爆炸”現象，在多項式時間內無法精確求解。所以，人們提出了以獲得次優解為目標的近似啟發式求解算法。……