,

(1.天津商业大学 商学院，天津 300134； 2.天津商业大学 管理创新与评价研究中心，天津 300134)

1 引言

旅行商问题(Traveling Salesman Problem，简称TSP)又称为旅行推销员问题、货郎担问题，最早于1859年由威廉·汉密尔顿首次提出，属于运筹学中经典的组合优化难题。该问题是单一旅行者由起点出发，不重复地走完其余地点并回到原出发点，在所有可能的路径中求出路径长度最短的一条。旅行商问题属于组合优化范畴，是NP-hard问题，具有组合优化问题的典型特征，并且问题描述简单，因此很多学者将旅行商问题算例作为算法研究的公共实例。同时，旅行商问题有着广泛的实际应用背景，如物流配送、调度排班、道路交通、计算机网络节点配置、生产调度、组合优化求极值等问题。所以，旅行商问题成为优化领域里的研究热点，吸引了管理优化、运筹学、数学、物理、生物和人工智能等领域的研究者的关注。

TSP问题的解空间是多维、多局部极值、复杂的解空间。这个解空间类似一个无穷大的丘陵地带，山峰、山谷连绵起伏，其中的山谷就代表局部极低值，最低的山谷代表最短路径，对应的方案就是最佳旅行方案。旅行商问题的求解方法大体可以分为两类：精确求解法和近似求解法。精确求解法主要是通过解析方法求得最优解，包括枚举法、分枝定界法、动态规划等。旅行商问题描述虽然非常简单，但随着需要访问城市数目的增加，会出现所谓的“组合爆炸”现象，在多项式时间内无法精确求解。所以，人们提出了以获得次优解为目标的近似启发式求解算法。……