旅行商问题

组合优化中的NP难问题

旅行推销员问题（英语：Travelling salesman problem, TSP）是这样一个问题：给定一系列城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的最短回路。它是组合优化中的一个NP难问题，在运筹学和理论计算机科学中非常重要。

简介

旅行商问题(TravelingSalesmanProblem，TSP)是一个经典的组合优化问题。经典的TSP可以描述为：一个商品推销员要去若干个城市推销商品，该推销员从一个城市出发，需要经过所有城市后，回到出发地。应如何选择行进路线，以使总的行程最短。从图论的角度来看，该问题实质是在一个带权完全无向图中，找一个权值最小的Hamilton回路。由于该问题的可行解是所有顶点的全排列，随着顶点数的增加，会产生组合爆炸，它是一个NP完全问题。由于其在交通运输、电路板线路设计以及物流配送等领域内有着广泛的应用，国内外学者对其进行了大量的研究。早期的研究者使用精确算法求解该问题，常用的方法包括：分枝定界法、线性规划法、动态规划法等。但是，随着问题规模的增大，精确算法将变得无能为力，因此，在后来的研究中，国内外学者重点使用近似算法或启发式算法，主要有遗传算法、模拟退火法、蚁群算法、禁忌搜索算法、贪婪算法和神经网络等。

研究历史

最早的旅行商问题的数学规划是由Dantzig（1959）等人提出，并且是在最优化领域中进行了深入研究。许多优化方法都用它作为一个测试基准。尽管问题在计算上很困难，但已经有了大量的启发式算法和精确方法来求解数量上万的实例，并且能将误差控制在1%内。

TSP的研究历史很久，最早的描述是1759年欧拉研究的骑士环游问题，即对于国际象棋棋盘中的64个方格，走访64个方格一次且仅一次，并且最终返回到起始点。1954年，Geo~eDanzig等人用线性规划的方法取得了旅行商问题的历史性的突破——解决了美国49个城市的巡回问题。这就是割平面法，这种方法在整数规划问题上也广泛应用。后来还提出了一种方法叫做分枝限界法，所谓限界，就是求出问题解的上、下界，通过当前得到的限界值排除一些次优解，为最终获得最优解提示方向。每次搜索下界最小的分枝，可以减小计算量。

2010年10月25日，英国一项最新研究说，在花丛中飞来飞去的小蜜蜂显示出了轻易破解“旅行商问题”的能力，而这是一个吸引全世界数学家研究多年的大问题，如能理解蜜蜂的解决方式，将有助于人们改善交通规划和物流等领域的工作。英国伦敦大学皇家霍洛韦学院等机构研究人员报告说，小蜜蜂显示出了轻而易举破解这个问题的能力。他们利用人工控制的假花进行了实验，结果显示，不管怎样改变花的位置，蜜蜂在稍加探索后，很快就可以找到在不同花朵间飞行的最短路径。这是首次发现能解决这个问题的动物，研究报告即将发表在《美国博物学家》杂志上。

进行研究的奈杰尔·雷恩博士说，蜜蜂每天都要在蜂巢和花朵间飞来飞去，为了采蜜而在不同花朵间飞行是一件很耗精力的事情，因此实际上蜜蜂每天都在解决“旅行商问题”。尽管蜜蜂的大脑只有草籽那么大，也没有电脑的帮助，但它已经进化出了一套很好的解决方案，如果能理解蜜蜂怎样做到这一点，对人类的生产、生活将有很大帮助。

据介绍，“旅行商问题”的应用领域包括：如何规划最合理高效的道路交通，以减少拥堵；如何更好地规划物流，以减少运营成本；在互联网环境中如何更好地设置节点，以更好地让信息流动等。

分类

经典TSP

CTSP是在一个带权无向完全图中找一个权值最小的Hamilton回路。在各类TSP中，该类问题的研究成果最多。近几年来，研究者或者基于数学理论构造近似算法，或者使用各种仿自然的算法框架结合不同的局部搜索方法构造混合算法。同时，神经网络和自组织图方法在该问题上的应用研究也引起了研究者的关注。

不对称TSP

若在CTSP模型中，两个顶点i和j间的距离d不一定相等，则称为 ATSP。ATSP由于两点间距离的不对称性，所以求解更困难，但由于现实生活中多数实际场景都为不对称的TSP，所以对于基于实际交通网络的物流配送来说，其比CTSP更具有实际应用价值。

配送收集TSP

TSPPD是由CTSP适应物流配送领域的实际需求而产生的。这个问题涉及到两类顾客需要：一类是配送需求，要求将货物从配送中心送到需求点；另一类是收集需求，要求将货物从需求点运往配送中心。当所有的配送和收集需求都由一辆从配送中心出发、限定容量的车辆来完成时，怎样安排行驶路线才能构成一条行程最短的 Hamilton回路。

多人旅行商问题

即多个旅行商遍历多个城市，在满足每个城市被一个旅行商经过一次的前提下，求遍历全部城市的最短路径。解决 MTSP对解决 “车辆调度路径安排 ”问题具有重要意义。过去的研究大多将 MTSP转化成多个TSP，再使用求解 TSP的算法进行求解。Hong Qu等人结合胜者全取 (winner—take—all)的竞争机制设计了一个柱形竞争的神经网络模型来求解MTSP，并对网络收敛于可行解进行了分析和论证。

多目标旅行商问题

CRISP的路径上只有一个权值 (即距离)，而 MoTSP研究的是路径上有多个权值的 TSP，要求找一条通过所有顶点并最终回到起点的回路，使回路上的各个权值都尽可能小。由于在多目标情况下，严格最优解并不存在，研究 MoTSP的目的是找到Pareto最优解，这是一个解集，而不是一个单一解。现阶段算法为构造一个求解单目标的遗传局部搜索算法，然后基于此求解多目标组合优化问题算法。

问题解法

旅行推销员的问题，我们称之为巡行（Tour），此种问题属于NP完全问题，所以旅行商问题大多集中在启发式解法。Bodin（1983）等人将旅行推销员问题的启发式解法分成三种：

1、途程建构法（TourConstructionProcedures）

从距离矩阵中产生一个近似最佳解的途径，有以下几种解法：

1）最近邻点法（NearestNeighborProcedure）：一开始以寻找离场站最近的需求点为起始路线的第一个顾客，此后寻找离最后加入路线的顾客最近的需求点，直到最后。

2）节省法（ClarkandWrightSaving）：以服务每一个节点为起始解，根据三角不等式两边之和大于第三边之性质，其起始状况为每服务一个顾客后便回场站，而后计算路线间合并节省量，将节省量以降序排序而依次合并路线，直到最后。

3）插入法（Insertion procedures）：如最近插入法、最省插入法、随意插入法、最远插入法、最大角度插入法等。

2、途程改善法（TourImprovementProcedure）

先给定一个可行途程，然后进行改善，一直到不能改善为止。有以下几种解法：

1）K-Opt(2/3Opt)：把尚未加入路径的K条节线暂时取代目前路径中K条节线，并计算其成本（或距离），如果成本降低（距离减少），则取代之，直到无法改善为止，K通常为2或3。

2）Or-Opt：在相同路径上相邻的需求点，将之和本身或其它路径交换且仍保持路径方向性，并计算其成本（或距离），如果成本降低（距离减少），则取代之，直到无法改善为止。

3、合成启发法（CompositeProcedure）

先由途程建构法产生起始途程，然后再使用途程改善法去寻求最佳解，又称为两段解法（twophasemethod）。有以下几种解法：

1）起始解求解+2-Opt：以途程建构法建立一个起始的解，再用2-Opt的方式改善途程，直到不能改善为止。

2）起始解求解+3-Opt：以途程建构法建立一个起始的解，再用3-Opt的方式改善途程，直到不能改善为止。

解法思路

旅行推销员的问题，我们称之为巡行（Tour），此种问题属于NP完全问题（NP-Complete），所以旅行商问题大多集中在启发式解法。Bodin（1983）等人将旅行推销员问题的启发式解法分成三种：

途程建构法

算法的核心从距离矩阵中产生一个近似最佳解的途径，有以下几种解法：

1、近邻点法（Nearest Neighbor Procedure）：一开始以寻找离场站最近的需求点为起始路线的第一个顾客，此后寻找离最后加入路线的顾客最近的需求点，直到最后。

2、节省法（ClarkandWright Saving）：以服务每一个节点为起始解，根据三角不等式两边之和大于第三边之性质，其起始状况为每服务一个顾客后便回场站，而后计算路线间合并节省量，将节省量以降序排序而依次合并路线，直到最后。

3、插入法（Insertion procedures）：如插入法、最省插入法、随意插入法、最远插入法、最大角度插入法等。

途程改善法

先给定一个可行途程，然后进行改善，一直到不能改善为止。有以下几种解法：

1、K-Opt(2/3Opt)：把尚未加入路径的K条节线暂时取代如今路径中K条节线，并计算其成本（或距离），如果成本降低（距离减少），则取代之，直到无法改善为止，K通常为2或3。

2、Or-Opt：在相同路径上相邻的需求点，将之和本身或其它路径交换且仍保持路径方向性，合成启发法

先由途程建构法产生起始途程，然后再使用途程改善法去寻求最佳解，又称为两段解法（twophasemethod）。有以下几种解法：

1、起始解求解+2-Opt：以途程建构法建立一个起始的解，再用2-Opt的方式改善途程，直到不能改善为止。

2、起始解求解+3-Opt：以途程建构法建立一个起始的解，再用3-Opt的方式改善途程，直到不能改善为止。

问题分析

旅行商问题要从所有周游路线中求取最小成本的周游路线，而从初始点出发的周游路线一共有(n-1)!条，即等于除初始结点外的n-1个结点的排列数，因此旅行商问题是一个排列问题。通过枚举(n-1)!条周游路线，从中找出一条具有最小成本的周游路线的算法，其计算时间显然为O(n!)。

枚举法

程序中采用深度优先策略。（采用隐式和显式两种形式）

枚举算法的特点是算法简单，但运算量大，当问题的规模变大，循环的阶数越大，执行的速度越慢。如果枚举范围太大（一般以不超过两百万次为限），在时间上就难以承受。在解决旅行商问题时，以顶点1为起点和终点，然后求{2…N}的一个全排列，使路程1→{2…N}的一个全排列→1上所有边的权（代价）之和最小。所有可能解由（2，3，4，…，N）的不同排列决定。

为便于讨论，介绍一些关于解空间树结构的术语。在下面分析回溯法和分支限界法时都直接或间接用到解空间树。在解空间树中的每一个结点确定所求问题的一个问题状态（problem state）。由根结点到其它结点的所有路径则确定了这个问题的状态空间（state space）。解状态（solution states）表示一些问题状态S，对于这些问题状态，由根到S的那条路径确定了这解空间中的一个元组。答案状态（answer states）表示一些解状态S，对于这些解状态而言，由根到S的这条路径确定了这问题的一个解（即，它满足隐式约束条件）。解空间的树结构称为状态空间树（state pace tree）。

对于旅行商问题，一旦设想出一种状态空间树，那么就可以先系统地生成问题状态，接着确定这些问题状态中的哪些状态是解状态，最后确定哪些解状态是答案状态，从而将问题解出。为了生成问题状态，采用两种根本不同的方法。如果已生成一个结点而它的所有儿子结点还没有全部生成，则这个结点叫做活结点。当前正在生成其儿子结点的活结点叫E-结点。不再进一步扩展或者其儿子结点已全部生成的生成结点就是死结点。在生成问题状态的两种方法中，都要用一张活结点表。在第一种方法中，当前的E-结点R一旦生成一个新的儿子C，这个儿子结点就变成一个新的E-结点，当完全检测了子树C之后，R结点就再次成为E-结点。这相当与问题状态的深度优先生成。在第二种状态生成方法中，一个E-结点一直保持到死结点为止。这两种方法中，将用限界函数去杀死还没有全部生成其儿子结点的那些活结点。如果旅行商问题要求找出全部解，则要生成所有的答案结点。使用限界函数的深度优先结点生成方法称为回溯法。E-结点一直保持到死为止的状态生成方法称为分支限界法。

回溯法

为了应用回溯法，所要求的解必须能表示成一个n-元组(x1,…,Xn)，其中x1是取自某个有穷集Si。通常，所求解的问题需要求取一个使某一规范函数P(x1,…,Xn)取极大值（或取极小值或满足该规范函数条件）的向量。

假定集合Si的大小是mi，于是就有m=m1 m2…mn个n元组可能满足函数P。所谓硬性处理是构造这m个n元组并逐一测试它们是否满足P，从而找出该问题的所有最优解。而回溯法的基本思想是，不断地用修改过的函数Pi(x1,…Xi)（即限界函数）去测试正在构造中的n-元组的部分向量(x1,…,Xi)，看其是否可能导致最优解。如果判定(x1,…,Xi)不可能导致最优解，那么就可能要测试的后n-i个元素组成的向量一概略去。因此回溯法作的次数比硬性处理作的测试次数（m次）要少得多。用回溯法求解的旅行商问题，即在枚举法的基础上多了一个约束条件，约束条件可以分为两种类型：显式约束和隐式约束。

分支限界法

采用FIFO分支限界法，分支限界法是在生成当前E-结点全部儿子之后再生成其它活结点的儿子，且用限界函数帮助避免生成不包含答案结点子树的状态空间的检索方法。在总的原则下，根据对状态空间树中结点检索的次序的不同又将分支限界设计策路分为数种不同的检索方法。在求解旅行商问题时，程序中采用FIFO检索（First In First Out），它的活结点表采用一张先进先出表（即队列）。可以看出，分支限界法在两个方面加速了算法的搜索速度，一是选择要扩展的节点时，总是选择选择一个最小成本的结点，尽可能早的进入最有可能成为最优解的分支；二是扩展节点的过程中，舍弃导致不可行解或导致非最优解的子结点。

贪心法

贪心法是一种改进了的分级处理方法。它首先旅行商问题描述，选取一种度量标准。然后按这种度量标准对n个输入城市排序，并按序一次输入一个城市。如果这个输入和当前已构成在这种量度意义下的部分最优解加在一起不能产生一个可行解，则不把这个城市加入到这部分解中。这种能够得到某种量度意义下的最优解的分级处理方法成为贪心方法。

获得最优路径的贪心法应一条边一条边地构造这棵树。根据某种量度来选择将要计入的下一条边。最简单的量度标准是选择使得迄今为止计入的那些边的成本的和有最小增量的那条边。

应用

旅行商问题具有重要的实际意义和工程背景。它一开始是为交通运输而提出的，比如飞机航线安排、送邮件、快递服务、设计校车行进路线等等。实际上其应用范围扩展到了许多其他领域．下面举几个实例。

印制电路板转孔是TSP应用的经典例子，在一块电路板上打成百上千个孔，转头在这些孔之间移动，相当于对所有的孔进行一次巡游。把这个问题转化为TSP，孔相当于城市．孔到孔之问的移动时间就是距离。

为了避免大气干扰，使光学系统达到其衍射极限分辨率．欧美发达国家提出发展空间光干涉仪和综合孔径望远镜的计划。美国航空航天局有一个卫星群组成空间天文台(Space—basedObservatories)的计划，用来探测宇宙起源和外星智慧生命。欧洲空间局也有类似的Darwin计划。对天体成像的时候，需要对两颗卫星的位置进行调整，如何控制卫星，使消耗的燃料最少，可以用TSP来求解。这里把天体看作城市，距离就是卫星移动消耗的燃料。

美国国家卫生协会在人类基因排序工作中用TSP方法绘制放射性杂交图。把DNA片段作为城市．它们之间的相似程度作为城市间的距离。法国科学家已经用这种办法作出了老鼠的放射性杂交图。

此外，旅行商问题还有电缆和光缆布线、晶体结构分析、数据串聚类等多种用途。更重要的是．它提供了一个研究组合优化问题的理想平台。很多组合优化问题，比如背包问题、分配问题、车间调度问题都和TSP同属NP完全问题，它们都是同等难度的．如果其中一个能用多项式确定性算法解决，那么其他所有的NP完全问题也能用多项式算法解决。很多方法本来是从TSP发展起来的．后来推广到其他NP完全问题上去。

全国各地天气预报查询

上海市

云南省

云南省

云南省

云南省

云南省