lingo怎么解决TSP问题

比如我已知A,B,C,D....之间的距离,求最小解,写出程序,谢谢
2025-02-27 13:02:16
推荐回答(1个)
回答1:

这段程序是关于13个城市的tsp问题的程序,一般解决更多城市的tsp问题,有蚁群,神经网络,和模拟退火等方法,这里给出lingo的程序,算作抛砖引玉吧。

MODEL:
SETS:
city/A1..A13/:U;!U(i)=cicy No;
links(city,city):distance,!the distance of the matrix;
X;!x(i,j)=1 if we use link i,j;
ENDSETS
DATA: !distance matrix;
!10000,the distance of impossible link;
distance= 0, 62, 92, 73,10000,10000,10000,10000,10000,10000,10000,10000,10000,
62, 0,10000,10000, 58,10000,10000,10000,10000,10000,10000,10000,10000,
92,10000, 0,10000,10000, 52, 57,10000,10000,10000,10000,10000,10000,
73,10000,10000, 0,10000,10000, 59,10000,10000,10000,10000,10000,10000,
10000, 58,10000,10000, 0,10000,10000,104,10000,10000,10000,10000,10000,
10000,10000, 52,10000,10000, 0,10000,10000, 85,104,10000, 77,10000,
10000,10000, 57, 59,10000,10000, 0,10000, 81,10000,10000,10000,10000,
10000,10000,10000,10000,104,10000,10000, 0,10000,115,166,10000,10000,
10000,10000,10000,10000,10000, 85, 81,10000, 0,10000,10000,10000, 63,
10000,10000,10000,10000,10000,104,10000,115,10000, 0,10000,10000,10000,
10000,10000,10000,10000,10000,10000,10000,166,10000,10000, 0, 87, 73,
10000,10000,10000,10000,10000, 77,10000,10000,10000,10000, 87, 0,10000,
10000,10000,10000,10000,10000,10000,10000,10000, 63,10000, 73,10000, 0;
ENDDATA
n=@SIZE(city);
!minimize total distance of the links;
MIN=@SUM(links:distance*X);
!the entrance;
@FOR(city(k):
@SUM(city(i)|i#ne#k:x(i,k))=1;
!it must be departed;
@SUM(city(j)|j#ne#k:x(k,j))=1;
@FOR(city(j)|j#gt#1 #and# j#ne#k:U(j)>=U(k)+X(k,j)-(N-2)*(1-X(k,j))+(N-3)*X(j,k)););
@FOR(links:@BIN(x)); !it makes the x's 0 or 1;
@FOR(city(k)|k#gt#1:
U(k)<=N-1-(N-2)*X(1,k);
U(k)>=1+(N-2)*X(k,1));
END