旅行商问题（TSP）是约束优化问题吗

来源：蜘蛛抓取(WebSpider) 时间：2020-03-11 04:29 标签：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

赵玲;刘三阳;;[J];兰州理工大学学报;2006年04期
李跃松;樊金生;张巧迪;;[J];石家庄铁道大学学报(自然科学版);2011年02期
张江维;司文建;;[J];电脑知识与技术;2009年07期
郏宣耀;[J];唐山师范学院学报;2005年05期
孙泽宇;邢萧飞;;[J];計算机工程与应用;2009年35期
朱命昊;厍向阳;;[J];计算机应用研究;2010年10期
孙泽宇;邢萧飞;;[J];计算机工程与设计;2011年04期
王蒙;介婧;曾建潮;董殿敏;;[J];计算机工程与设计;2009年21期
宋雪梅;李兵;;[J];河北理工学院学报;2006年01期
张宏怡;韩建松;;[J];计算机工程与应用;2006年25期
赵越;;[J];吉林建筑工程学院学报;2009年05期

我要回帖

 

随机推荐