基于流水算法的旅行商问题求解

,

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

1 引言

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

TSP问题的解空间是多维、多局部极值、复杂的解空间。这个解空间类似一个无穷大的丘陵地带，山峰、山谷连绵起伏，其中的山谷就代表局部极低值，最低的山谷代表最短路径，对应的方案就是最佳旅行方案。旅行商问题的求解方法大体可以分为两类：精确求解法和近似求解法。精确求解法主要是通过解析方法求得最优解，包括枚举法、分枝定界法、动态规划等。旅行商问题描述虽然非常简单，但随着需要访问城市数目的增加，会出现所谓的“组合爆炸”现象，在多项式时间内无法精确求解。所以，人们提出了以获得次优解为目标的近似启发式求解算法。受到自然界的启发，人们提出各种各样的元启发式算法(Meta-Heuristics)用于优化求解，如遗传算法[1]、模拟退火[2]、禁忌搜索算法[3]、蚁群算法[4～6]、粒子群优化算法[7]等。这些智能算法被广泛地应用于TSP问题求解，虽然不能保证获取最优解，但当问题规模较大时，保证在可行时间内找到满意的解。求解TSP问题的近似求解算法又可分为环路构造算法和环路改进算法两类[8]。前者从某个非法解开始,通过某种增广策略逐步改变该解，直到得到一个合法解为止，这类算法包括最近邻算法、贪心算法、Clarke-Wright算法和Christofides算法等。环路改进算法则在给定初始的合法解后使用某种策略来改进初始解。这些策略更多的是元启发式算法，包括遗传算法[9～12]、模拟退火[13]、禁忌搜索算法[14]、蚁群算法[15,16]、粒子群优化算法[17,18]等。旅行商问题的本质是根据旅行商问题的解空间特征，研究局部最优解、全局最优解和邻域结构之间的关系，具体包括：一种邻域结构的局部最优解和另一种邻域结构的局部最优解之间的关系；全局最优解和所有邻域结构的局部最优解之间的关系。所以，提出一种更能协调上述关系的启发式算法是组合优化领域学者长期追求的目标。

2 旅行商问题数学模型

旅行商问题是典型的组合优化问题，该问题可以表述为:给定n个城市vi(i=1,2,…,n)，形成一个完全无向带权图G=(V,E)；其中V(G)={v1,v2,…,vn}称为图G的城市集，E(G)={eij}(i,j∈(1,2,…,n),i≠j)称为图G的边集，eij表示每两个城市i和j之间的边，并且已知边eij的距离为dij。一个旅行商经过所有的城市，每个城市经过一次，且仅经过一次，求出在所有可能的旅游路线中路线长度最短的一条。旅行商问题的数学模型为

(1)

其中xij表示是否由城市i经过边eij到城市j，如果是则赋值为1，否则为0。

3 流水算法原理

现代元启发式算法成为近似求解大规模复杂的旅行商问题的研究热点。研究者从生物系统的进化和大自然中自适应性现象得到灵感,提出了一些以搜索近优解为目标的仿生元启发式算法，如遗传算法、蚁群优化算法、粒子群优化算法等。仿生优化算法是一类模拟自然生物进化或者群体社会行为的随机搜索方法的统称。借鉴自然和社会的各种现象，提出并设计优化算法成为一个重要的求解途径。本文正是在这样的背景下，基于旅行商问题的解空间类似一个无穷大的丘陵地带特点，受到自然现象“水无常形，水往低处流，水流千里归大海”的启发，设计新型的求解旅行商问题的元启发式算法—流水算法。

3.1 流水的启示

总启示：“水无常形，水往低处流，水流千里归大海”是众多流水全局寻优，求极值(地势最小)的过程。如图1所示，一个流水从初始位置A，流经B、C、D等锚点位置(局部极小)最终到达最低点E(全局最小)。流水的位置与旅行商问题可行域具体解的编码相互映射。

图1 流水的三维示意图

流水的具体启示及分析如下：

(1)流水局部搜索启示：“水无常形，水往低处流” 是一个流水根据地势状况局部搜索更低点，并向着下一个局部更低位置流动的过程，在这个过程中流水总是尽可能选择并流经最短路径到达最低点。并且，流水不可能倒着流动，具有禁忌搜索的特点。

(2)水漫溢出的启示：当流水流到一个局部最低的位置，会出现停滞(如图1中位置B)；但随着水量增加，水位上升到一定高度，流水从一个局部次优的位置溢出，并由此继续向下流动，跳出局部收敛。从优化算法的角度，流水的这种特点具有突破局部收敛的能力，即当流水若干代不变后，强行更换位置到局部次优的位置，从而继续进行局部搜索。

(3)流水凿洞的启示：流水向着下一个更低、更好位置流动时，落差越大，流水冲击惯性越大，就会对周围的泥土或岩石进行磨损，甚至可以凿洞突破当前位置的限制，向着比当前位置好的附近点流动(向着局部较优解方向搜索)，向着最低点流动(向着全局最优解方向搜索)。并且，在现实中往往可以通过人工凿洞方式，让水流到更低位置，并且路径较短。从优化算法的角度，流水的这种特点具有突破局部收敛、向着全局最优解收敛的优点。

(4)蒸发-下雨的启示：在自然界中，位置高、水量少的流水容易被蒸发掉形成水蒸气；相应水蒸气会在一定的气候影响下随机下雨，形成相对应数量的流水。从优化算法的角度，“蒸发”具有“优胜劣汰”优点；“下雨”具有多样化群体，具备随机全局寻优的优点。

(5)涓涓细流汇成江河的启示：在自然界中涓涓流水总是汇集到更低更短的路径上，集聚成江河，最后流归到大海。从流量的角度解释，只有更低、更短的路径才能吸引更多的涓涓细流，使得这些更低更短路径上的水量得到不断的增加。流水的这一特征表现为很强的流量正反馈机制，引导流水在进行路径选择时，倾向流经水量大的路径(具有位置更低、路径更短的特征)，从而使得整个流水系统向最佳路径的方向进化。

3.2 流水算法的提出

全局寻优、局部寻优和计算时间的矛盾一直是困惑旅行商问题求解的难题。本文借用大自然“水无常形，水往低处流，水流千里归大海”的规律，设计新型的求解算法“流水算法”对旅行商问题进行寻优求解。流水算法简单流程如图2所示，具体设计和相关主要操作如下。

图2 流水算法简单流程图

(1)编码

在流水算法中，一个可行解可以用编码表达，对应流水所流经的一个当前位置，具体的编码形式因具体的优化问题而异。在求解旅行商问题中，编码形式具体体现为旅行路线的所有城市排列顺序，如图3所示。

图3 交换节点位置进行局部搜索示意图

(2)初始化流水群

流水算法是群体并行协作寻优的算法机制，所以算法开始首先要初始化流水群。本文采用随机式和启发式两种方式按照特定比例产生流水群，即旅行商问题的可行解群。随机式是指没有任何规则的随机产生解群，可以保证初始解群的多样性和随机性；启发式是指依据距离短规则和流量大规则启引导产生解群(详见3.3节)，保证初始解群一定程度的良好。

(3)流水局部搜索操作

流水局部搜索操作基本思想是在搜索过程中系统地改变邻域结构集来拓展搜索范围，获得局部最优解。一个解在当前位置随机按照一定方式搜索一定步长进行局部搜索，向着下一个更好位置流动；如果没有更好位置则更新步长继续搜索。并且，解不可能倒着搜索，具有禁忌搜索特点。如图3所示，城市编码的排序对应的就是一个解，其中每个排列位置上的编码代表一个城市，如a、b。在具体的应用中，存在着许多种局部搜索方式，本文按照步长距离交换两个节点位置进行局部搜索，例如图3中，原始解中城市a与一个步长距离的城市b进行交换，形成一个新解。流水局部搜索操作的具体流程见图4。

图4 流水局部搜索及水漫溢出操作

(4)水漫溢出操作

水漫溢出操作是指一个解在当前位置搜索既定步长(设定的阈值)停滞后，强制移动到局部次优的位置，跳出局部收敛。在具体操作时候，水漫溢出操作往往结合局部搜索操作，如图4所示。在这里必须明确局部次优位置具有以下特征：来自流水当前的邻域，并且是流水先前没有经过的，同时从这个次优位置能实现局部搜索寻找到更好的位置(即流水从这个位置能继续向低处流动)。

(5)流水凿洞操作

经过不断搜索，流水群中优秀解往往可能处于局部优位置，这个位置很有可能非常接近全局最优解，这些优秀的流水在自己的位置停滞的时间很久，并且，水漫溢出操作很难实现跳出局部收敛。这时候，本算法采用流水凿洞方式使得当前位置向着当前种群最优解方向搜索，表现为向着全局寻优，具体方式有很多种。本文采取流水凿洞操作的措施是：优秀的流水在当前局部优位置向着当前种群最优解定向搜索若干步长，进行局部搜索。理论上，按照这种定向搜索，优秀的流水一定会搜索到比当前位置更好的解。流水凿洞操作具有跳出局部停滞，向着全局最优解收敛的优点。

具体来说，对比原始解和全局最优解，寻找二者编码有差异的位置，原始解通过自身交换方式，换成与全局最优解中同样位置所对应的编码，直至找到一个更优解(理论上一定可以寻找到)。如图5所示，原始解中某位置城市编号是b，全局最优解中对应位置城市编号是c，通过自身交换让原始解中对应位置城市编号是c，形成新的更换解。

图5 交换节点位置进行凿洞操作示意图

(6)蒸发-下雨操作

蒸发-下雨操作具体包括两个子操作，其中“蒸发”操作是按照一定比率蒸发(消除)解群中不好的解，具有“优胜劣汰”的优点；“下雨”操作随机生成先前被蒸发数量的新的解，保证群体多样化，具有随机全局寻优的优点。下雨操作具体根据“涓涓细流汇成江河”流量正反馈机制进行路径选择(具体见3.3节)，引导整个解群系统向最佳路径(最优解)的方向进化。

3.3 路径选择

每一个新的流水(无论是初始化阶段的流水群，还是迭代过程中随机下雨阶段的流水)都使用逐步决策方法进行路径选择，建立问题的解；具体就是随机选择初始城市，然后按照概率依次选择所要旅游的城市。假如在第t次迭代时，一个新的流水k处于城市i，选择城市j作为下一站要旅游的城市的概率

(2)

3.4 水流量更新规则

模仿现实中流水的汇集和挥发原理，每次迭代完后，算法要对路径上水流量实施更新。在第t次迭代过程中，流水k在进行一次巡游后，根据(3)式进行所经过路径上水流量更新

(3)

(4)

其中Lk(t)是流水k在第t次迭代时巡游路线长度。

4 数值试验

本文运用标准TSP测试算例Eil51(该算例需要旅游51个城市，目前最优结果为426)对算法性能进行评估。相关参数如下：水源群数量m=100；迭代总数NC_max=100；蒸发下雨比例rain=0.7；凿洞概率系数cave=0.2；水流量权重系数α=4；能见度权重系数β=1；水流量挥发系数ρ=0.1。在MATLAB平台进行20次仿真实验，最优结果val_best=428.9816471722069，非常接近426，其对应的旅行方案为R=(44,17,37,15,45,33,39,10,49,5,38,11,32,1,22,2,16,50,9,30,34,21,29,20,35,36,3,28,31,8,26,7,43,24,23,48,6,27,51,46,12,47,4,18,14,25,13,41,40,19,42)。上述最优结果所对应的整个旅行路线简约、紧凑、高效，不存在交叉、过多折返现象，旅行方案非常好。并且，流水算法在求解算例Eil51时候呈现出非常好的收敛性，其每一代的最佳解的值和解群的平均值都能快速地递减收敛，收敛的代数很小。

与文献[18]中的蚁群算法、遗传算法、模拟退火方法、禁忌搜索方法、粒子群算法等经典元启发式算法相同条件的运算结果进行比较，如表1所示。很明显本文提出的流水算法远优于经典的蚁群算法、遗传算法、模拟退火方法、禁忌搜索方法，所求最优解非常接近实例Eil51目前已知的最优解，求解精度高，迭代收敛的代数要明显少于上述算法，并且具有很好的收敛性。

5 结论

本文受自然现象“水无常形，水往低处流，水流千里归大海”的启发，设计新型的旅行商问题的元启发式算法，即流水算法。新算法主要包括流水局部搜索、水漫溢出、流水凿洞、蒸发-下雨4个算子，具有很强的全局搜索和局部搜索能力，同时具有禁忌搜索、正反馈机制、优胜劣汰、群体并行寻优等特点，并且兼有跳出局部收敛加速全局收敛的能力。通过求解经典的标准TSP测试算例Eil51，对比于其他元启发式算法，该算法具有明显的优势，求解精度高、迭代次数少、收敛速度快，为高效率解决大规模组合优化问题提供了新的思路。本文提出的流水算法研究处于初期，还有许多问题值得研究，如算法的时间复杂度、空间复杂度、稳定度、收敛性、参数变化对寻优的影响及敏感性规律等。从以往经典元启发式算法的研究和应用经验可以推断，这种模仿自然现象的流水算法具有广阔的实际应用前景，如物流配送、旅游路线、道路交通、员工调度排班、生产调度、组合优化求极值等领域。所以，从应用的角度看，更多深入细致的工作还有待于进一步展开。并且，流水算法丰富了中国本土学者原创性元启发式算法的研究，已经被相关领域的专家所关注。

[1] Holland J H. Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence[M]. Ann Arbor, MI: University of Michigan Press, 1975.

[2] Kirkpatrick S, Gelatt C D, Vecchi M P. Optimization by simulated annealing[J]. Science, 1983, 220(4598): 671-680.

[3] Glover F. Future paths for integer programming and links to artificial intelligence[J]. Coputers and Operations Research, 1986, 13: 533-549.

[4] Colorni A, Dorigo M, Maniezzo V. Distributed optimization by ant colonies[A]. Processings of the First European Conference on Artificial Life[C]. Amsterdam: Elsevier, 1992. 134-142.

[5] Colorni A, Dorigo M, Maniezzo V. An investigation of some properties of an ant algorithm[A]. Processings of the Parallel Problem Solving from Nature Conference[C]. Amsterdam: Elsevier, 1992. 509-520.

[6] Dorigo M, Maniezzo V, Colorni A. Ant system: optimization by a colony of cooperating agents[J]. IEEE Transactions on System, Man, and Cybernetics Part-B: Cybernetics, 1996, 26(1): 29-41.

[7] Kennedy J, Eberhart R C. Particle swarm optimization[A]. Proceedings of the 1995 IEEE International Conference on Neural Networks[C]. Piscataway, New Jersey, 1995. 1942-1948.

[8] 戚玉涛,焦李成,刘芳.基于并行人工免疫算法的大规模TSP问题求解[J].电子学报，2008,36(8):1552-1558.

[9] 唐立新.旅行商问题的改进遗传算法[J].东北大学学报，1999，20(1):40-42.

[10] Chang P C, Huang W S, Ting C J. Dynamic diversity control in genetic algorithm for mining unsearched solution space in TSP problems[J]. Expert Systems with Applications, 2010, 37(3): 1863-1878.

[11] Albayrak M, Allahverdi N. Development a new mutation operator to solve the traveling salesman problem by aid of genetic algorithms[J]. Expert Systems with Applications, 2011, 38: 1313-1320.

[12] Nagata Y, Soler D. A new genetic algorithm for the asymmetric traveling salesman problem[J]. Expert Systems with Applications, 2012, 39: 8947-8953.

[13] Geng X, Chen Z, Yang W. et al.. Solving the traveling salesman problem based on an adaptive simulated annealing algorithm with greedy search[J]. Applied Soft Computing, 2011, 11: 3680-3689.

[14] 刘于江，喻泽峰.一种求解旅行商问题的禁忌搜索算法[J].江西理工大学学报,2006,27(4):38-40.

[15] Manfrin M, Birattari M, Stützle T, et al.. Parallel ant colony optimization for the traveling salesman problem[J]. Lecture Notes in Computer Science, 2006, 4150: 224-234.

[16] 蔡荣英，王李进，吴超，等.一种求解旅行商问题的迭代改进蚁群优化算法[J].山东大学学报(工学版),2012,42(1):6-11.

[17] 郭崇慧,谷超，江贺.求解旅行商问题的一种改进粒子群算法[J].运筹与管理,2010,19(5):20-26.

[18] 沈继红,王侃.求解旅行商问题的混合粒子群优化算法[J].智能系统学报,2012,7(2):174-182.