TSP问题算法-TSP问题求解方法工具 v5.0

软件介绍

TSP问题，，即Traveling Salesman Problem，也就是旅行商问题，是款功能比较不错的算法小工具；利用软件来帮助我们计算这些最线路问题，简称为TSP问题，并且支持对各种参数输入，计算的速度快，结果也正确，直观的用户操作界面，通过所有给定的需求点之后，最后再回到原点的最小路径成本。TSP问题算法小软件就能帮上你的忙，有需要的快来下载吧。

TSP问题算法

TSP问题算法功能介绍

TSP问题在物流中的描述是对应一个物流配送公司，欲将n个客户的订货沿最短路线全部送到。如何确定最短路线。
TSP问题最简单的求解方法是枚举法。它的解是多维的、多局部极值的、趋于无穷大的复杂解的空间，搜索空间是n个点的所有排列的集合，大小为(n-1)。可以形象地把解空间看成是一个无穷大的丘陵地带，各山峰或山谷的高度即是问题的极值。求解TSP，则是在此不能穷尽的丘陵地带中攀登以达到山顶或谷底的过程。
旅行商问题字面上的理解是：有一个推销员，要到n个城市推销商品，他要找出一个包含所有n个城市的具有最短路程的环路。 TSP的历史很久，最早的描述是1759年欧拉研究的骑士周游问题，即对于国际象棋棋盘中的64个方格，走访64个方格一次且仅一次，并且最终返回到起始点。 TSP由美国RAND公司于1948年引入，该公司的声誉以及线性规划这一新方法的出现使得TSP成为一个知名且流行的问题。
旅行推销员的问题，我们称之为巡行(Tour)，此种问题属于NP-Complete的问题，所以旅行商问题大多集中在启发式解法。

TSP问题算法软件优势

　　只对分支界限的算法路径进行显示，是黄色的颜色
　　显示动态规划算法的路径，是绿色的颜色
　　这次对益群里面的蚁数进行输入
　　信息素重要程度、启发式因子重要程度
　　信息素的挥发、信息素的初始值
　　每次金华的代数设置、交叉算子的信息

TSP问题算法软件特色

　　分支限界的算法信息查看
　　1。在顶点数为 12 时，测得分支限界算法约半分钟。
　　2。在顶点数为 13 时，测得分支限界算法约一分钟。
　　3。在顶点数为 14 时，测得分支限界算法约两分半钟。
　　4。顶点数大于 14 时，没有测试过。

TSP问题算法下载安装步骤

　1、途程建构法（Tour Construction Procedures）

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

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

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

　　2、途程改善法（Tour Improvement Procedure）

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

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

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

　　蜜蜂实验

　　3、合成启发法（Composite Procedure）

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

TSP问题求解方法工具 v5.0

TSP问题算法常见问题

注意事项
　　1.质点坐标是屏幕像素坐标，left,top,纵坐标向下不是向上，与数学上的纵坐标方向相反。
　　2.坐标为屏幕像素坐标，所以只能整数。
　　3.点坐标可以用鼠标拖动，拖动时可以超出屏幕范围自动产生滚动条，但点坐标不可以为负数。