Lingo编程解决TSP问题

TSP问题即巡回旅行商问题，一个商人旅行经过所有城市一次最后回到原点，问什么走法使走的路程最短。接下来用Lingo编程实现，此方法具有普遍性，建议小本本记下。
假设有6个城市

思路

利用01矩阵表示一次巡回旅行的方案。如下面矩阵代表一种方案。
(010000001000000100000010000001100000)\\left( \\begin{matrix}{}0\\quad1\\quad0\\quad0\\quad0\\quad0 \\\\0\\quad0\\quad1\\quad0\\quad0\\quad0 \\\\0\\quad0\\quad0\\quad1\\quad0\\quad0 \\\\0\\quad0\\quad0\\quad0\\quad1\\quad0 \\\\0\\quad0\\quad0\\quad0\\quad0\\quad1 \\\\1\\quad0\\quad0\\quad0\\quad0\\quad0 \\\\\\end{matrix} \\right)⎝⎜⎜⎜⎜⎜⎜⎛010000001000000100000010000001100000⎠⎟⎟⎟⎟⎟⎟⎞
a12=1表示从城市1走到城市2。那么这个矩阵的路线为1–>2–>3–>4–>5–>6–>1。
观察这个矩阵的特点为每一行只有一个1，每一列只有一个1。但并不是这样的矩阵都是合理的，例如如下矩阵：
(010000001000100000000010000001000100)\\left( \\begin{matrix}{}0\\quad1\\quad0\\quad0\\quad0\\quad0 \\\\0\\quad0\\quad1\\quad0\\quad0\\quad0 \\\\1\\quad0\\quad0\\quad0\\quad0\\quad0 \\\\0\\quad0\\quad0\\quad0\\quad1\\quad0 \\\\0\\quad0\\quad0\\quad0\\quad0\\quad1 \\\\0\\quad0\\quad0\\quad1\\quad0\\quad0 \\\\\\end{matrix} \\right)⎝⎜⎜⎜⎜⎜⎜⎛010000001000100000000010000001000100⎠⎟⎟⎟⎟⎟⎟⎞
这个矩阵的路线为：1–>2–>3–>1，4–>5–>6–>4。说明路线矩阵不能出现子圈。
总距离=路线矩阵*距离矩阵。

建立线性规划模型

设城市之间的距离用矩阵d表示，dij表示城市i与城市j的距离。
设0–1矩阵X表示经过各城市之间的路线。xij=0表示城市i不到城市j，为1则反之。
路线矩阵每一行和为1：
∑j=1nxij=1,i=1,…,n(i≠j)\\sum\\limits_{j = 1}^n {x_{ij} = 1,i = 1,…,n} \\quad(i\\ne j)j=1∑nxij=1,i=1,…,n(i=j)
每一列和为1：
∑i=1nxij=1,j=1,…,n(j≠i)\\sum\\limits_{i = 1}^n {x_{ij} = 1,j = 1,…,n} \\quad(j\\ne i)i=1∑nxij=1,j=1,…,n(j=i)
路线矩阵不可以出现子圈（破圈），引入额外变量u：
ui−uj+nxij≤n−1,1<i≠j≤nu_i-u_j+nx_{ij}\\le n-1,\\quad1< i\\ne j\\le nui−uj+nxij≤n−1,1<i=j≤n
对于破圈公式的解释：

两个点出现子圈的情况：xij=1,xji=1。x_{ij}=1,x_{ji}=1。xij=1,xji=1。
把xij,xjix_{ij},x_{ji}xij,xji代入破圈公式得：ui−uj≤−1,uj−ui≤−1u_i-u_j\\le-1,\\quad u_j-u_i\\le-1ui−uj≤−1,uj−ui≤−1
两式相加得：0≤−20\\le-20≤−2，显然不成立，保证了两个点不可能出现子圈。
对于三个点的情况：xij=1,xjk=1,xki=1x_{ij}=1,x_{jk}=1,x_{ki}=1xij=1,xjk=1,xki=1 代入破圈公式得：
ui−uj≤−1,uj−uk≤−1,uk−ui≤−1u_i-u_j\\le-1,\\quad u_j-u_k\\le-1,\\quad u_k-u_i\\le-1ui−uj≤−1,uj−uk≤−1,uk−ui≤−1
相加得：0≤−30\\le-30≤−3，不成立，保证了三个点不出现子圈。
对于n个点以此类推。

此外:
xij=0或1，i,j=1..nx_{ij}=0或1，i,j=1..n\\quadxij=0或1，i,j=1..nui为实数，i=1..n u_i为实数，\\quad i=1..nui为实数，i=1..n
目标函数为：
minz=∑i=1ndij∑j=1nxijminz=\\sum\\limits_{i = 1}^n {d_{ij} } \\sum\\limits_{j = 1}^n {x_{ij} }minz=i=1∑ndijj=1∑nxij

Lingo编程代码如下

!TSP问题;MODEL:SETS:city/1..6/:u;link(city,city):d,x;ENDSETSDATA:d=@FILE(E:\\d.txt);!导入距离矩阵;@text()=@writefor(link(i,j)|x(i,j)#GT#0:\'x(\',i,\',\',j,\')=\',x(i,j));!指定输出格式，输出为1的x;ENDDATAmin=@sum(link:d*x);@for(city(j):@sum(city(i)|j#ne#i:x(i,j))=1);!一列只有一个1;@for(city(i):@sum(city(j)|j#ne#i:x(i,j))=1);!一行只有一个1;@for(link(i,j)|i#ne#j#and#i#gt#1:u(i)-u(j)+6*x(i,j)<=5);!破圈;@for(link:@bin(x));!x取0或1;End