TSP问题数学模型的问题分析

旅行商问题要从图G的所有周游路线中求取最小成本的周游路线，而从初始点出发的周游路线一共有(n-1)!条，即等于除初始结点外的n-1个结点的排列数，因此旅行商问题是一个排列问题。排列问题比子集合的选择问题通常要难于求解得多，这是因为n个物体有n!种排列，只有 个子集合(n!>O( ))。通过枚举(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 space tree）。

对于旅行商问题，一旦设想出一种状态空间树，那么就可以先系统地生成问题状态，接着确定这些问题状态中的哪些状态是解状态，最后确定哪些解状态是答案状态，从而将问题解出。为了生成问题状态，采用两种根本不同的方法。如果已生成一个结点而它的所有儿子结点还没有全部生成，则这个结点叫做活结点。当前正在生成其儿子结点的活结点叫E-结点。不再进一步扩展或者其儿子结点已全部生成的生成结点就是死结点。在生成问题状态的两种方法中，都要用一张活结点表。在第一种方法中，当前的E-结点R一旦生成一个新的儿子C，这个儿子结点就变成一个新的E-结点，当完全检测了子树C之后，R结点就再次成为E-结点。这相当与问题状态的深度优先生成。在第二种状态生成方法中，一个E-结点一直保持到死结点为止。这两种方法中，将用限界函数去杀死还没有全部生成其儿子结点的那些活结点。如果旅行商问题要求找出全部解，则要生成所有的答案结点。使用限界函数的深度优先结点生成方法称为回溯法。E-结点一直保持到死为止的状态生成方法称为分支限界法。 为了应用回溯法，所要求的解必须能表示成一个n- 元组(x1,…,Xn)，其中x1是取自某个有穷集Si。通常，所求解的问题需要求取一个使某一规范函数P(x1,…,Xn)取极大值（或取极小值或满足该规范函数条件）的向量。

假定集合Si的大小是mi，于是就有m=m1m2…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个输入城市排序，并按序一次输入一个城市。如果这个输入和当前已构成在这种量度意义下的部分最优解加在一起不能产生一个可行解，则不把这个城市加入到这部分解中。这种能够得到某种量度意义下的最优解的分级处理方法成为贪心方法。

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

问题描述不展开了，感兴趣可以自己搜一下。csdn上这篇文章介绍的很详细，可以看一下 ， >

、旅行商问题（Traveling Salesman Problem, TSP）

这个问题字面上的理解是：有一个推销员，要到n个城市推销商品，他要找出一个包含所有n个城市的具有最短路程的环路。

TSP的历史很久，最早的描述是1759年欧拉研究的骑士周游问题，即对于国际象棋棋盘中的64个方格，走访64个方格一次且仅一次，并且最终返回到起始点。

TSP由美国RAND公司于1948年引入，该公司的声誉以及线性规划这一新方法的出现使得TSP成为一个知名且流行的问题。

2、中国邮递员问题（Chinese Postman Problem CPP）

同样的问题，在中国还有另一个描述方法：一个邮递员从邮局出发，到所辖街道投递邮件，最后返回邮局，如果他必须走遍所辖的每条街道至少一次，那么他应如何选择投递路线，使所走的路程最短？这个描述之所以称为中国邮递员问题， 因为是我国学者管梅古谷教授于1962年提出的这个问题并且给出了一个解法。

3、“一笔画”问题（Drawing by one line）

还有一个用图论语言的描述方式：平面上有n个点，用最短的线将全部的点连起来。称为“一笔画”问题。

4、配送路线问题（Route of Distribution）

TSP问题在物流中的描述是对应一个物流配送公司，欲将n个客户的订货沿最短路线全部送到。如何确定最短路线。

TSP问题最简单的求解方法是枚举法。它的解是多维的、多局部极值的、趋于无穷大的复杂解的空间，搜索空间是n个点的所有排列的集合，大小为（n-1）！。可以形象地把解空间看成是一个无穷大的丘陵地带，各山峰或山谷的高度即是问题的极值。求解TSP，则是在此不能穷尽的丘陵地带中攀登以达到山顶或谷底的过程。

5、多回路运输问题（Vehicle Routing Problem, VRP）

多回路运输问题在物流中的解释是对一系列客户的需求点设计适当的路线，使车辆有序地通过它们，在满足一定的约束条件下，如货物需求量、发送量、交发货时间、车辆载重量限制、行驶里程限制、时间限制等等，达到一定的优化目标，如里程最短、费用最少、时间最短，车队规模最少、车辆利用率高。

VRP问题和TSP问题的区别在于：客户群体的数量大，只有一辆车或一条路径满足不了客户的需求，必须是多辆交通工具以及运输工具的行车顺序两个问题的求解。相对于TSP问题，VRP问题更复杂，求解更困难，但也更接近实际情况。

6、多个旅行商问题（Multiple TSP）

由于限制条件的增加，TSP问题可以衍生出多个旅行商问题（MTSP），就是一个出发点，m个旅行商的TSP，即所访问的客户没有需求，车辆没有装载的限制，优化目标就是要遍历所有的客户，达到总里程最短。

VRP问题是MTSP问题的普遍化，当客户的需求不仅仅是被访问，而是有一定容积和重量的商品的装载和卸载，涉及到不同种类和型号或不同载重量车辆的调度策略时，MTSP问题转换为VRP问题。

7、最近邻点法（Nearest Neighbor）

这是一种用于解决TSP问题的启发式算法。方法简单，但得到的解并不十分理想，可以作为进一步优化的初始解。求解的过程一共四步：首先从零点开始，作为整个回路的起点，然后找到离刚刚加入到回路的上一节点最近的一个节点，并将其加入到回路中。重复上一步，直到所有的节点都加入到回路中，最后，将最后一个加入的节点和起点连接起来，构成了一个TSP问题的解。

8、最近插入法（Nearest Insertion）

最近插入法是另一个TSP问题的求解方法。它的求解过程也是4步：首先从一个节点出发，找到一个最近的节点，形成一个往返式子回路；在剩下的节点中，寻找一个离子回路中某一节点最近的节点，再在子回路中找到一个弧，使弧的两端节点到刚寻找到的最近节点的距离之和减去弧长的值最小，实际上就是把新找到的节点加入子回路以后使得增加的路程最短，就把这个节点增加到子回路中。重复以上过程，直到所有的节点都加入到子回路中。最近插入法比最近邻点法复杂，但可以得到相对比较满意的解。

9、节约里程法（Saving Algorithm）

节约算法是用来解决运输车辆数目不确定的VRP问题的最有名的启发式算法。它的核心思想是依次将运输问题中的两个回路合并为一个回路，每次使合并后的总运输距离减小得幅度最大，直到达到一辆车的装载限制时，再进行下一辆车的优化。优化过程分为并行方式和串行方式两种。

10、扫描算法（Sweep Algorithm）

它也是求解车辆数目不限制的VRP问题的启发式算法。求解过程同样是4步：以起始点为原点建立极坐标系，然后从最小角度的两个客户开始建立一个组，按逆时针方向将客户逐个加入到组中，直到客户的需求总量超出了车辆的载重定额。然后建立一个新的组，继续该过程，直到将全部客户都加入到组中

1 ounce (oz) ≈ 29ml——1盎司约等于29毫升

1 tsp (bsp) =1/8 oz——1茶匙（吧匙）等于1/8盎司

1 tbsp = 3/8 oz——1餐匙等于3/8盎司

1 jigger= 3/2 oz——1吉格等于3/2盎司

1 split =6 oz——1司普力等于6盎司

1 miniature =2 oz ——1明尼托等于2盎司

1 pint =16 oz ——1品脱等于16盎司

1 quart = 32 oz——1夸脱等于32盎司

1 gallon = 128 oz——1加仑等于128盎司

1、方法简介

好久没更新啦，最近在专注看看分支定界，列生成，分支定价算法，并动手实现去求解一些简单的问题。分支定界我理解就是一种有规律的枚举，所以它是可以求出精确的解。分支定界几个关键点就是设定界限函数，随着搜索的过程中逐渐更新界限，直至上界和下界重合；构建节点表，在每个分支的过程中需要将信息记录下来，按照某一个标准在节点表里储存，后续取点删点。

2、方法应用

下边以bb在求解tsp中的应用来说明，不同问题思路相近，大同小异。求解步骤如下：

（1）规约费用矩阵。即使费用矩阵中每一行每一列都包含0元素，此时规约系数就是该问题的一个下界。

3、算法实现

以28个点的tsp为例，测试结果如下：

以上就是关于TSP问题数学模型的问题分析全部的内容，包括:TSP问题数学模型的问题分析、关于旅行家TSP问题的几种算法 python、想问一下什么是vrp问题，什么是tsp问题等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！