(资料图)

原发布者:tancydc

TSP问题的求解摘要旅行商问题（TravelingSalesmanProblem，TSP）代表一类组合优化问题，在计算机网络、公路交通分布等多种实际问题中都有重要意义。“旅行商问题”也常被称为“旅行推销员问题”，其实质为是指一名推销员要拜访多个地点时，如何找到在拜访每个地点一次后再回到起点的最短路径。针对该题求解经过30个城市旅行的最短路径问题，我们采用三种方法解决：法一：（模拟退火算法）借助Matlab程序采用模拟退火算法进行分析解决。即首先在固定温提条件下求出当前温度下的最短路径（局部最优解），然后改变温度后再次求局部最优后得到最终的最短路径（全局最优）法二：（遗传算法）借助Matlab程序采用遗传算法进行分析解决。即法三：（线性规划）找出该线性目标规划的目标函数及约束条件，借助Lingo软件求得该TSP问题的最短路径关键词：TSP问题模拟退火算法线性规划遗传算法一、问题重述1.1引言TSP是典型的组合优化问题,并且是一个NP-hard问题，TSP简单描述为:一名商人欲到n个不同的城市去推销商品,每2个城市i和j之间的距离为dij,如何选择一条路径使得商人每个城市走一遍后回到起点,所走的路径最短。用数学符号表示为:设n维向量s=(c1,c2,…,cn)表示一条路经,目标函数为:minn1C(c1,c2,…,cn)=d(ci,ci1)d(c1,cn)。i11.2问题提出题目给出30个城市的分布图象及具体坐标，要求出经过30

本文到此讲解完毕了，希望对大家有帮助。