旅行商问题的综述教学研究

2022-09-11

旅行商问题[1] (Traveling Salesman Problem, 简称TSP) 是一个著名的组合优化问题, 是一个经典的N P完全问题, 该问题具有很强的应用背景, 如数控机床上的最优钻孔路线[1]的选取, 电路版的焊接、物流的调度等都都属于旅行商问题;而且对旅行商问题的不断研究, 也带动了相关学科的发展。正因如此, 旅行商问题受到广大科研工作者的广泛重视。但对旅行商问题的综述教学研究却还未有人注意到, 这给初学者或广大的学生了解并进入该领域, 从而对该领域产生兴趣造成了一定的障碍。因此, 对该问题的综述教学研究是非常有意义的。本文从旅行商问题的定义、旅行商问题的推广形式、旅行商问题的应用、旅行商问题的求解方法、旅行商问题求解算法的发展前景等几个方面对该问题作分析与论述, 为该问题的教学研究提供了借鉴, 增强了初学者对该问题的全面了解并增强其对该领域的兴趣。

1 旅行商问题的定义

旅行商问题最初描述为:一个商品推销员要去若干个城市推销商品, 该推销员从一个城市出发, 需要经过所有城市后, 回到出发地。应如何选择行进路线, 以使总的行程最短。由于该问题的可行解是所有顶点的全排列, 随着顶点数的增加, 它的可行解会急速增加, 这就是所谓的组合爆炸, 是一个N P完全问题。

从图论的角度来看, 旅行商问题实质是在一个带权完全无向图中, 找一个权值最小的Hamiton回路。设G= (V, E) 为一个带权图, V={1, 2, …, n}为顶点集, E={eij= (i, j) |}为边集合。为顶点i但顶点j的距离, 其中dij>0且dij≠∞, 同时dij=dji (i, j∈V) , 则经典TSP的数学模型为:

其中|S|为图S的顶点数。⑴为TSP的目标函数, 求经过所有顶点的回路的最小距离。⑵-⑷限定回路上每个顶点仅有一条入边和一条出边。⑸限定在回路中不出现子回路。模型实质上是在一个带权图中求一条Hamilton回路。

2 旅行商问题的推广形式

随着科技的发展与现实工程中的需要, 旅行商问题也发展出了各种推广的形式, 以适应工程上的需求。

2.1 K-TSP问题

K-TSP问题[2]是k个人从城市1出发分头去访问n-1个城市, 每个城市有且仅有一个人到达, 最后都回到城市1。问怎样安排使得k个人的总访问路线最短?显然当k=1时, 就是经典的T S P问题。

2.2 非对称距离的旅行商问题

现实中碰到的问题, 大多是顶点i、j的距离dij与顶点j、i的距离dji是相等的, 即dij=dji, 但在工程上确实也存在dij≠dji的问题, 对于, 未必都有dij=dji的旅行商问题, 就称为非对称旅行商问题[3]。

2.3 点群旅行商问题

在经典旅行商问题中, 若将顶点集V变为P个点群 (cluster) 的并集, , 要找到一条能够遍历P个点群的费用最小的Hamilton回路。如下图1:

这就叫点群旅行商问题[4]。该问题在实际中也有广泛的应用, 如:循环物流系统设计, 一个厂区被分砌个多边形区域, 如图2, 每个区域都规范为只含有或的角问题要求设计一条沿着这些区域边缘的最短路线, 以遍历每一个区域;要求设计的路线至少经过每个区域的一个顶点, 这就是点群旅行商问题一个实例。

2.4 多目标旅行商问题

多目标T S P是由经典的T S P延伸而来, 对给定的赋权图G, 经典的T S P只有一个权重, 而对于对于多目标T S P, 它的每条边上同时具有m (m≥2) 个权重 (如、距离, 费用) , 要求寻找一条回路, 使得该图的每个顶点都恰好访问一次, 且回路的m个总权重都尽可能最小;这就是多目标TSP[5]。显然当m=1时, 它就是经典的TSP问题。因此, 它是经典T S P的推广。

2.5 黑白旅行商问题

黑白旅行商问题[6]是基于SONET技术的光纤网络设计、航线调度等实际应用背景提出的一种经典旅行商问题的推广形式。它的顶点被分成两类, 一类是白的, 一类是黑的, 它也是要寻找一条不重复地访问所有顶点的Hamilton环路, 但这条环路必须满足:1) 基数约束:环路上连续的两个黑色顶点间的白色顶点数目不超过正整数Q, 其中Q被称为基数阈值;2) 权值约束:环路上连续的两个黑色顶点间路径的权值不超过正数L, 其中L被称为权值阈值。若没有基数与权值的约束, 那它也就是经典的旅行商问题。因此, 它也是经典旅行商问题的推广。

2.6 瓶颈旅行商问题

瓶颈旅行商问题[7]是从经典旅行商问题延伸出来的一种扩展形式, 其含义与经典的T S P类似, 仅是目标不同, 要求巡回路线中经过的最长距离最短。

3 旅行商问题的应用

旅行商问题在工程上具有很强的适用背景, 如印刷电路版 (P C B) 的走刀问题[1]。P C B上通常有多种不同直径的孔, 对某一孔径所构成的孔系, P C B数控钻问题可描述为:从换刀点处出发, 不重复又不遗漏地加工完所有孔, 再回到换刀点, 进行下一种孔径换刀和加工。这对数控编程而言, 就存在如何安排孔的加工顺序 (路线) , 使空程移动时间最短, 这一问题就是旅行商问题。把这个问题的最优解或近似最优解求出来, 以设计最优走刀路线, 这对像杭州三联公司整机定型产品年产几千块到几十万块PCB这样大批量生产规模的专用生产厂家来说其影响相当可观。除了以上这些应用, 求解T S P问题还可应用于:V L S I芯片设计、机器人控制、车辆选路、调度问题及物流配送等领域。

4 旅行商问题的求解算法

求解旅行商问题的方法可以分为两大类, 一类是精确算法, 目的是要找到理论最优解;另一类是近似算法, 不强求最优解, 只要找到“足够好”的满意解就可以了。

4.1 精确算法

穷举法是一种精确算法, 它将所有的可能路线全部求出, 通过比较找到全局最优解, 但计算量在顶点数稍微多一点情况下, 这时由于可行解太多, 而使算法不可行。因为对于n个城市的经典T S P, 剔除方向性和周期性, 存在 (n-1) !/2条不同的路径;如n=20, 则存在1.2×1018条回路, 即使每秒列举一亿条回路的计算也需3 5 0年, 且随城市数增加计算量将超指数增长。

目前精确算法还有两种常用方法:割平面法与分枝定界法。它们与穷举法比较, 虽然减小了计算, 但计算量仍然很大;所以有必要寻求近似算法。

4.2 近似算法

和精确算法相比, 近似算法比较简单, 计算量小很多, 大致可分为三类: (1) 巡回路径构造算法;这类算法按照一定的规则把城市一个一个地加入到路径中去, 全部加进去以后就得到了一条巡回路径。不同的规则就得到不同的算法, 例如贪婪算法就是其中的一种; (2) 巡回路径优化算法, 该类方法先产生一条初始巡回路径, 再改变其中某些城市的顺序, 使路径优化, 逐渐接近最优解; (3) 智能算法。所谓智能算法, 是指2 0世纪以来借助自然界的规律, 根据其原理设计的算法, 如模拟退火、遗传算法、神经网络、蚁群算法、粒子群优化算法等;这类方法的共同特点就是先随机生成一些可行解, 再通过一定的替代规则, 由这些初始可行解生成新的可行解, 这样反复地进行, 直到满足事先规定的停止标准, 以最后得到的可行解作为问题的最优解的近似解。

5 旅行商问题求解算法的发展前景

近几年, 研究人员试图运用各种方法对T S P进行求解, 但是, 随着对T S P特性的认识的加深, 试图使用精确算法求解T S P的研究基本销声匿迹, 取而代之的是各种近似方法;试图使用单一方法求解T S P问题的研究也在减少, 而使用多种方法结合的研究逐渐占据了研究的主流。纵观近几年的研究成果, 研究者主要使用了以下几种方法对T S P进行了研究: (1) 使用各种纯数学的方法构造时间复杂度为多项式的近似算法。 (2) 使用常规的启发式算法:通常首先构造一个所有顶点回路, 然后使用一些局部优化方法对回路进行改进。 (3) 使用遗传算法、蚁群算法、模拟退火算法、粒子群算法和神经网络等仿自然算法。由于遗传算法、蚁群算法和粒子群算法具有较强的群体搜索能力, 但同时又存在可能陷入局部最优的问题, 因而研究者通常将其它搜索算法和这些算法相结合以构造更高效的混合算法。神经网络和自组织图由于具有自学习、联想存储功能和高速寻找优化解的能力, 使用它们和其它方法相结合的研究T S P问题的求解也得到了研究者的重视。

由于T S P的广泛的实际应用背景, 相信未来相当长时间内, T S P仍将是算法研究领域的一个热点问题。除非有新的解决组合优化问题的算法框架出现, 否则各种仿自然的算法结合局部优化的算法思想仍将是研究的重点;结合实际问题设计适当的操作算子和局部优化策略以构造混合算法仍将是解决TSP的重要途径。在现行的利用仿自然算法对TSP进行的研究中, 解的表示方法似乎已经成为限制突破的一个瓶颈, 如果能够设计出新型的更易产生更优解的解的表示方法, 并据此设计出求解方法, 将是T S P算法研究的突破。

6 结语

旅行商问题是组合优化中的一个经典N P问题, 由于其在工程上具有广泛的实际应用背景, 因此一直以来受到广大科研工作者的关注;但关于旅行商问题的教学研究方面做得还不够, 使得初学者很难快速进入该领域的研究。本文对旅行商问题从几个方面进行了分析与阐述, 使初学者能对该问题有一个全面的认识, 了解该问题的实际应用性、把握该问题现今求解算法的发展趋势;从而对它感性趣, 迅速加入该领域的研究。

摘要：旅行商问题是数学上的组合优化问题, 是一个经典的NP完全问题。该问题在工程上有很强的实用背景;对该问题的研究一直受到众多学者的重视, 对其的求解亦提出了各种不同算法;同时就该问题还提出了各种推广形式, 但就该问题的教学研究却很少有人涉及。针对这些情况, 本文就该问题的综述与教学做几方面的研究, 以提高对该问题的教学质量、增强学生的学习积极性。

关键词：旅行商问题,NP完全问题,多旅行商问题,K旅行商问题,黑白旅行商问题,非对称旅行商问题,多目标旅行商问题,教学研究