TSP问题华中科技大学管理学院
•旅行商问题(Traveling Salesman Problem，TSP)，也称为货郎担问题，是爱尔兰数学家Sir William Rowan Hamilton和英国数学家Thomas Penyngton Kirkman在19世纪提出的数学问题。它是指给定n个城市并给出每两个城市之间的距离，旅行商必须以最短路径访问所有的城市一次且仅一次，并回到原出发地，现已证明它属于NP难题。由于该问题的描述简单，而其实际模型在连锁店的货物配送、网络布线等优化问题和印刷电路板的钻孔路线方案中又有着广泛的应用，故长期以来一直吸引着国内外许多研究人员进行研究，他们尝试着用各种算法来求解TSP问题。华中科技大学管理学院
•其图论描述为：给定图G =(V，A)，其中V为顶点集，A为各顶点相互连接组成的边集，设D=(dij)是由顶点i和顶点j之间的距离所组成的距离矩阵，要求确定一条长度最短的回路，即遍历所有顶点当且仅当一次的最短距离。华中科技大学管理学院
•1)对称旅行商问题=,∀i,j=1,2,3,...,n;()ddijji•2)非对称旅行商问题≠,∃i,j=1,2,3,...n.()ddijji华中科技大学管理学院
数学模型Minz=dx（1）∑∑ijijijSubjectto:x=1,i=1,...,n（2）∑ijjx=1,j=1,...,n（3）∑ijix≥1,D为部分城市集合（4）∑iji∈D,j∉Dx∈0，1，i=1,...,n，j=1,...,n（5）{}ij华中科技大学管理学院
•约束（4）表示所有的城市均由一条路径连通。24315•如要在Lingo中建立模型，约束（4）应如何表示？华中科技大学管理学院
约束（4）可表示为：u−u+Nx≤N−1(fori≠j;i=2,3,...,N;j=2,3,...,N)ijijAllu≥0j约束（4）确保：由决策变量得到一条独立的子路径，此解是不可行的；由决策变量得到一条完整的路径，此解是不可行的；华中科技大学管理学院
•对上面的图，有决策变量取值：x=x=x=x=x=11521433452•把其中子路径4－3－4的决策变量带入约束（4），得：u−u+Nx≤N−14343u−u+Nx≤N−13434•进而得：N(x+x)≤2N−24343华中科技大学管理学院
•U 可以作为决策变量，也可以赋值，如，U值取相应点的访问次序。华中科技大学管理学院
TSP问题的求解算法•1.环路构造型算法•环路构造算法从一个包含部分顶点的初始子环路开始，按照某种策略逐步将不在当前子环路中的顶点插入到子环路中，直到得到一个完整环路．一般初始子环路只是一个随机选择的顶点或几个任选的顶点构成的简单环路．选择插入顶点的策略通常是贪婪策略，即选择使子环路的长度增加最少的顶点插入．如任选一个顶点作为初始子环路，然后每次选择剩下的顶点中与上一次插入的顶点距离最近的一个。•目前最主要的4种环路构造算法是：最近邻算法、贪婪算法、Clarke—Wright节约算法和Christofides算法，解的质量则是Christofides算法最好，最近邻算法最差华中科技大学管理学院
•2.环路改进算法•环路改进算法在给定初始可行解的情况下，使用某种优化策略来改进当前的可行解．这些策略一般都以局部优化作为基础．•最常用的局部优化策略为k-交换，即：将在当前环路上的k条边与不在当前环路上的k条边交换位置，以得到新的合法环路．若选取的交换边集合使得环路的权值改进最大，则称为k-优化(k-opt)．显然k-opt的性能要优于随机k-交换．考虑到计算时间的限制，一般都选择较小的k，最常用的是2-opt和3-opt．华中科技大学管理学院
•由于构造型算法解的质量较差，迄今为止已利用智能优化算法开发了许多性能较好的改进型搜索算法，主要有：•1)模拟退火算法•2)禁忌搜索算法•3)神经网络优化算法•4)蚁群算法•5)遗传算法•6)混合优化策略华中科技大学管理学院
