简述解决TSP问题的智能优化算法

○李葶

（同济大学中德学院 上海 200092）

随着我国经济的持续快速发展，人们对交通运输的各种需求也显著增长。从1999年到2010年，我国公路总长度从130万公里上升到370万公里，增长幅度为185%，同期我国注册的车辆数量由1500万辆上升到8000万辆，增长幅度为433%，明显高于中国公路总长的增长幅度。由于车辆数量的激增，导致城市交通拥堵严重，交通事故频发，物流成本居高不下，物流时效性也无法得到保证。我国物流成本占GDP的比重持续偏高，约为20%，远高于发达国家物流成本占GDP的比重10%，以及中等发达国家的16%。而城市闲置土地资源的紧缺，导致修建和拓宽道路的成本越来越高，且修建和拓宽道路的速度远远赶不上城市车辆的增长速度，此时提高城市道路的利用率、安全性和舒适性以及降低城市物流成本就成为我们急需解决的问题。

物流配送调度系统就是针对以上问题提出的，它能提供可靠的交通信息、高效快速的应急服务，在降低物流成本方面有着显著的成效，能满足现代物流经济性、准时性和灵活性的多种需求。迄今为止，国外研究物流配送调度系统的理论和算法已经不少，并且在实际应用方面取得显著的成果，如美国IBM基于最短路径法和启发式算法研究出来的VSPX系统，日本富士通以节约法为核心研发出来的VSS系统，以及美国美孚以扫描法为核心研究出来的HPCAD系统。但是国内在这方面的研究仅停滞于初步理论阶段，在开发实用的物流配送调度系统方面还是一片空白。造成这种现象的根本原因在于大部分算法只考虑了TSP（Traveling salesman problem）问题的部分约束条件，且设置了许多假设条件，限制了他们的应用范围，在实际应用中缺乏灵活性。由于研发物流配送调度系统的核心在于解决贴合实际的TSP问题，因此研究可以妥善解决TSP问题的算法，并在此基础上开发出智能的物流配送调度系统具有现实的理论意义和实践意义。

一、TSP问题

1、TSP问题的简介

TSP问题也称旅行推销员问题、货郎担问题，是经典的组合优化问题，最早的记录来自于1759年欧拉研究的骑士周游问题，即对象棋中的64个方格，走访每个方格有且仅有一次。TSP问题的历史可以分成以下几个阶段：1800—1900年，首次描述TSP问题；1920—1930年，TSP问题得到较好的定义；1940—1950年，研究人员意识到TSP问题是个难题；1954年，42个城市的TSP问题求得最优解；1980年，Crowder和Padberg求解了318个城市的问题；1987年，Padberg和Rinaldi求解了2392个城市的问题；1992年，美国Rice大学的CRPC研究小组解决了 3038个城市的问题；1994年，Applegate、Bixby和Chvatal等人解决了7393个城市的问题；1998年，CRPC研究解决了美国13509个城市组成的TSP问题；2003年，Hisao Tamaki发现了TSPLIB中pla33810的一个次优解；2004年，Keld Helsguan发现了pla85900问题的一个次优解。

2、TSP问题的数学模型

TSP问题可以表达为，给定k个城市，i、j为城市编号，0≤i≤k，0≤j≤k。dij代表从城市 i到 j的距离，解决 TSP 问题就是寻找一条最短的闭合路径，使得每个城市刚好遍历一次。

二、求解TSP问题的各种解法

目前求解TSP问题的主要方法主要分两类：精确求解算法和近似求解算法。

精确求解算法通过搜索整个问题的全部解空间，在所有解集中求得最优解。精确求解算法包括整数规划法、动态规划法、分支定界算法等，这类算法虽然可以得到精确解，但由于过大的搜索空间范围导致计算时间过长，计算效率非常低下，很少用于实际应用。最早用于解决TSP问题的精确求解算法是穷举法，思路简单，可以直观快速地求出少量城市点数的最优解，但是求解大规模数据集时运算量太大，运算效率不高，时间上难以承受。

近似求解法又可称为启发式求解算法，部分近似求解算法又被称为智能优化算法。典型的近似算法有插入算法、r-opt算法和最近邻算法等，这类算法虽然可以较快的计算出可行解，但是其接近最优解的程度不够令人满意。智能优化算法主要包括神经网络算法、遗传算法、禁忌搜索算法、模拟退火法、粒子群算法和蚁群算法等，是近几年来非常活跃的研究领域，它是利用仿生学的原理，让算法在计算过程中不断自我调整，使之具备自适应能力。智能优化算法虽然不能在有限的时间内获得最优解，但其接近最优解的程度是非常可喜的。

求解TSP问题的算法很多，要评价和比较各种算法的优劣，必须有一个综合的性能评价标准，TSP算法的综合性能评价标准包括：算法求解的精确程度，即接近最优解的程度；求解算法的复杂度，包括时间的复杂度和空间的复杂度；求解算法的适应性，即算法在各个领域的通用程度；求解算法的严密性，即保证求解算法充分的理论基础。

综合比较，智能优化算法是一类综合性能比较强的TSP算法，也是目前最适合用于开发物流配送调度系统的算法，本文将对几种智能优化算法进行详细说明。

1、神经网络算法

人工神经网络（Artificial Neural Network,简称ANN），又名神经网络（Neural Network,简称NN），是一种通过模拟动物神经网络的特点进行数据分析的方法。1985年，Hopfield和Tank首次将这种算法应用于求解TSP问题。它的主要思想是用能量函数替代TSP问题中的目标函数，通过能量函数确定神经元之间的相互连接权限，随着网络状态的逐渐变化，当能量达到平衡时，就可以得到局部最优解。

由于神经网络是一种数据驱动型非线性映射模型，可以实现任何复杂的因果关系映射，能够从大量的历史数据中进行聚类和学习，进而找到某些行为变化规律，因此可以用来处理难以用数学模型描述的系统，具有很强的并行性、自适应、联想记忆、容错鲁棒以及任意逼近非线性等特性。目前神经网络技术在解决TSP问题上取得了一定的成绩，但是神经网络存在严重缺陷，很难确定算法的参数，必须通过多次反复的数据测试才能获得一个相对较好的参数，因此严重限制了神经网络的适用范围。

2、遗传算法

遗传算法是Holland于1973年首次提出的，是一种模拟生物界自然选择和遗传机制的随机搜索算法。它的基本思想是将TSP问题的求解表示成“染色体”的适者生存的过程，通过“染色体”的一代代的进化，即通过选择、交叉和变异等操作，最终得到“最适应环境”的个体，从而求得最优解或满意解。

遗传算法能准确模拟自然界生物进化过程中的染色体，整个遗传过程操作简单，在数据优化过程中不受外界条件的限制，能用简单的计算方法实现全局解空间的搜索。但是遗传算法中容易出现“早熟”现象，必须通过设置变异概率来控制“早熟”，高的变异率扩大了搜索空间，有利于诱导产生更加优秀的个体，但是交叉概率和变异概率过大会导致收敛速度过慢，迭代次数过大。因此实现收敛速度和最优解之间的平衡是遗传算法的一大难点。

3、禁忌搜索算法

禁忌搜索算法是由Fred Glovert等于1986年首次提出的，是一种全局性逐步寻优的邻域搜索算法，可以模拟人类记忆功能的寻优特征，通过局部邻域搜索机制和相应的禁忌准则来避免重复搜索，并通过藐视准则赦免一些被禁忌的优良状态，进而保证多样化的有效搜索，最终实现全局优化。

在禁忌搜索算法的搜索过程中，邻域结构、候选解、禁忌长度、禁忌对象、藐视准则、终止准则等都是影响算法性能的关键因素。且禁忌搜索算法对初始解和邻域结构有较大的依赖性，由于禁忌算法串行的搜索机制，一个不理想的初始解将直接影响到搜索质量。

4、模拟退火法

现代模拟退火算法是由Kirkpatrick S等于1983年提出，是基于Mente Carlo迭代求解策略的一种随机寻优算法。它通过模拟物理中固体物质的退火过程，结合具有概率突跳特性的Metropolis抽样策略，在解空间中随机寻找目标函数的全局最优解，在降温过程中不断重复抽样，最终实现问题的最优解。

模拟退火算法解的优越性依赖初始温度和退火时间，当初始温度过低或者退火速度过快，算法将陷入局部最优解。但是如果迭代次数较高，随着退火速度的降低将极大增加运行时间。

5、蚁群算法

蚁群算法是由意大利学者Dorigo M于1991年首次提出，是一种模拟自然界蚂蚁寻找食物的过程来计算路径的算法，通过群体间信息素的交换和相互合作寻求最优解的过程。蚂蚁独立寻找食物，在找寻食物的路程中会释放信息素，信息素会影响随后的蚂蚁对路径的选择，信息素越强的路径，越可能被蚂蚁选择。对于蚂蚁算法来说，各条路径的初始信息素相同，但是随着时间的推移，较优路径上的信息素会越来越多，最后实现寻求最优解或次优解的目的。

蚂蚁算法中，蚂蚁数量M的设置是影响算法性能的重要因素，M过小会导致未被所搜索过的路径信息素趋向于0，全局搜索能力太差，稳定性变差。M过大会导致所有路径上的信息素过于平均，随机性太强，收敛速度过慢，信息正反馈能力过弱。有研究表明，M取值范围在[0.6n,0.9n]（n代表城市规模），蚂蚁算法的收敛速度和接近全局最优解的能力最理想。

在蚂蚁算法中，总信息量Q表示循环一周蚂蚁释放的信息素的总和，Q也同样对蚂蚁算法的性能有很大的影响。Q越大信息素增长越快，正反馈效果越好，算法收敛速度越快。研究表明，Q的取值与TSP问题的规模和路径长度有关，在小规模的TSP问题中，Q一般取100。

蚂蚁算法具有正反馈、并发性、较强的鲁棒性、易于其他算法相结合等优点，但是蚂蚁算法易出现停滞现象。

[1]国家发展和改革委员会经济运行调节局、南开大学现代物流研究中心：中国现代物流发展报告（2010）[M].中国物资出版社，2010.

[2]唐纳德,J.鲍尔索科斯、戴维J.克劳斯：物流管理[M].机械工业出版社，1999.

[3]林志毅：改进的遗传算法求解TSP问题[D].武汉理工大学，2006.

[4]Helsgaun K.An effectiveimplementation oftheLin-Kernighan traveling salesman heuristic[J].European Journal of Operational Research,2000.