(旅行商问题.docxVIP

旅行商问题编辑旅行商问题（Traveling Saleman Problem，TSP）又译为旅行推销员问题、货郎担问题，简称为TSP问题，是最基本的路线问题，该问题是在寻求单一旅行者由起点出发，通过所有给定的需求点之后，最后再回到原点的最小路径成本。最早的旅行商问题的数学规划是由Dantzig（1959）等人提出。目录1简介2研究历史3问题解法4解法思路途程建构法途程改善法5研究进展6问题分析1简介“旅行商问题”常被称为“旅行推销员问题”，是指一名推销员要拜访多个地点时，如何找到在拜访每个地TSP问题点一次后再回到起点的最短路径。规则虽然简单，但在地点数目增多后求解却极为复杂。以42个地点为例，如果要列举所有路径后再确定最佳行程，那么总路径数量之大，几乎难以计算出来。多年来全球数学家绞尽脑汁，试图找到一个高效的算法TSP问题在物流中的描述是对应一个物流配送公司，欲将n个客户的订货沿最短路线全部送到。如何确定最短路线。TSP问题最简单的求解方法是枚举法。它的解是多维的、多局部极值的、趋于无穷大的复杂解的空间，有哪些信誉好的足球投注网站空间是n个点的所有排列的集合，大小为（n-1）。可以形象地把解空间看成是一个无穷大的丘陵地带，各山峰或山谷的高度即是问题的极值。求解TSP，则是在此不能穷尽的丘陵地带中攀登以达到山顶或谷底的过程。2研究历史旅行商问题字面上的理解是：有一个推销员，要到n个城市推销商品，他要找出一个包含所有n个城市的具有最短路程的环路。TSP的历史很久，最早的描述是1759年欧拉研究的骑士周游问题，即对于国际象棋棋盘中的64个方格，走访64个方格一次且仅一次，并且最终返回到起始点。TSP由美国RAND公司于1948年引入，该公司的声誉以及线性规划这一新方法的出现使得TSP成为一个知名且流行的问题。3问题解法旅行推销员的问题，我们称之为巡行（Tour），此种问题属于NP-Complete的问题，1、途程建构法（Tour Construction Procedures）从距离矩阵中产生一个近似最佳解的途径，有以下几种解法：2、途程改善法（Tour Improvement Procedure）先给定一个可行途程，然后进行改善，一直到不能改善为止。有以下几种解法：1）如果成本降低（距离减少），则取代之，直到无法改善为止，K通常为2或3。3、合成启发法（Composite Procedure）有以下几种解法1）起始解求解+2-Opt：起始解求解+3-Opt：蜜蜂试验4解法思路旅行推销员的问题，我们称之为巡行（Tour），此种问题属于NP完全问题（NP-Complete），所以旅行商问题大多集中在启发式解法。Bodin（1983）等人将旅行推销员问题的启发式解法分成三种：途程建构法从距离矩阵中产生一个近似最佳解的途径，有以下几种解法：如近邻点法（Nearest Neighbor Procedure）：一开始以寻找离场站最近的需求点为起始路线的第一个顾客，此后寻找离最后加入路线的顾客最近的需求点1、，直到最后。2、节省法（Clark and Wright Saving）：以服务每一个节点为起始解，根据三角不等式两边之和大于第三边之性质，其起始状况为每服务一个顾客后便回场站，而后计算路线间合并节省量，将节省量以降序排序而依次合并路线，直到最后。3、插入法（Insertion procedures）：如今插入法、最省插入法、随意插入法、最远插入法、最大角度插入法等。途程改善法先给定一个可行途程，然后进行改善，一直到不能改善为止。有以下几种解法：1、K-Opt(2/3 Opt)：把尚未加入路径的K条节线暂时取代如今路径中K条节线，并计算其成本（或距离），如果成本降低（距离减少），则取代之，直到无法改善为止，K通常为2或3。2、Or-Opt：在相同路径上相邻的需求点，将之和本身或其它路径交换且仍保持路径方向性，合成启发法先由途程建构法产生起始途程，然后再使用途程改善法去寻求最佳解，又称为两段解法（two phase method）。有以下几种解法：1、起始解求解+2-Opt：以途程建构法建立一个起始的解，再用2-Opt的方式改善途程，直到不能改善为止。2、起始解求解+3-Opt：以途程建构法建立一个起始的解，再用3-Opt的方式改善途程，直到不能改善为止。5研究进展2010年10月25日，英国一项必威体育精装版研究说，在花丛中飞来飞去的小蜜蜂显示出了轻易破解“旅行商问题”的能力，而这是一个吸引全世界数学家研究多年的大问题，如能理解蜜蜂的解决方式，将有助于人们改善交小蜜蜂解决大问题通规划和物流等领域的工作。 英国伦敦大学皇家霍洛韦学院等机构研究人员报告说，小蜜蜂显示出了轻而易举破解这个问题的能力。他们利用人工控制的假花进行了实验，结果显示，不管怎样改变花的位置，蜜蜂在稍加探