文档介绍：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)对称旅行商问题
2)非对称旅行商问题
数学模型
约束(4)表示所有的城市均由一条路径连通。
如要在Lingo中建立模型,约束(4)应如何表示?
1
2
5
4
3
约束(4)可表示为:
ui,uj 可以作为决策变量,也可以赋值,如,u值取相应点的访问次序。
对上面的图,有决策变量取值:
把其中子路径4-3-4的决策变量带入约束(4),得:
进而得:
TSP问题的求解算法
环路构造算法从一个包含部分顶点的初始子环路开始,按照某种策略逐步将不在当前子环路中的顶点插入到子环路中,,,然后每次选择剩下的顶点中与上一次插入的顶点距离最近的一个。
目前最主要的4种环路构造算法是:最近邻算法、贪婪算法、Clarke—Wright节约算法和Christofides算法,解的质量则是Christofides算法最好,最近邻算法最差