TSP问题及程序

森之张卫东 发表于 2015-8-10 21:16

旅行商问题，即TSP问题（Travelling Salesman Problem）又译为旅行推销员问题、货郎担问题，

是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径

的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径

路程为所有路径之中的最小值。

MODEL: SETS:
 CITY / 1.. 10/: U; ! U( I) = sequence no. of city;
 LINK( CITY, CITY):
 DIST, ! The distance matrix;
 X; ! X( I, J) = 1 if we use link I, J;
ENDSETS DATA: !Distance matrix, it need not be symmetric;
 DIST =0 8 5 9 12 14 12 16 17 22
 8 0 9 15 17 8 11 18 14 22
 5 9 0 7 9 11 7 12 12 17
 9 15 7 0 3 17 10 7 15 18
12 17 9 3 0 8 10 6 15 15
14 8 11 17 8 0 9 14 8 16
12 11 7 10 10 9 0 8 6 11
16 18 12 7 6 14 8 0 11 11
17 14 12 15 15 8 6 11 0 10
22 22 17 18 15 16 11 11 10 0;
ENDDATA !The model:Ref. Desrochers & Laporte, OR Letters, Feb. 91;
 N = @SIZE( CITY);
 MIN = @SUM( LINK: DIST * X);
 @FOR( CITY( K):
 ! It must be entered;
@SUM( CITY( I)| I #NE# K: X( I, K)) = 1;
 ! It must be departed;
@SUM( CITY( J)| J #NE# K: X( K, J)) = 1;
 ! Weak form of the subtour breaking constraints;
 ! These are not very powerful for large problems;
@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)) );
 ! Make the X's 0/1;
 @FOR( LINK: @BIN( X));
 ! For the first and last stop we know...;
 @FOR( CITY( K)| K #GT# 1:
U( K) <= N - 1 - ( N - 2) * X( 1, K);
U( K) >= 1 + ( N - 2) * X( K, 1));
END
Matlab可以解决TSP问题，但人们更常用的是Lingo，所以附上LIngo代码。

森之张卫东 发表于 2015-8-10 21:20

MODEL:

 SETS:
 CITY / 1.. 10/: U; ! U( I) = sequence no. of city;
 LINK( CITY, CITY):
 DIST, ! The distance matrix;
 X; ! X( I, J) = 1 if we use link I, J;
ENDSETS

DATA: !Distance matrix, it need not be symmetric;
 DIST =0 8 5 9 12 14 12 16 17 22
 8 0 9 15 17 8 11 18 14 22
 5 9 0 7 9 11 7 12 12 17
 9 15 7 0 3 17 10 7 15 18
12 17 9 3 0 8 10 6 15 15
14 8 11 17 8 0 9 14 8 16
12 11 7 10 10 9 0 8 6 11
16 18 12 7 6 14 8 0 11 11
17 14 12 15 15 8 6 11 0 10
22 22 17 18 15 16 11 11 10 0;
ENDDATA

!The model:Ref. Desrochers & Laporte, OR Letters, Feb. 91;
 N = @SIZE( CITY);
 MIN = @SUM( LINK: DIST * X);
 @FOR( CITY( K):
 ! It must be entered;
@SUM( CITY( I)| I #NE# K: X( I, K)) = 1;
 ! It must be departed;
@SUM( CITY( J)| J #NE# K: X( K, J)) = 1;
 ! Weak form of the subtour breaking constraints;
 ! These are not very powerful for large problems;
@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)));
 ! Make the X's 0/1;
 @FOR( LINK: @BIN( X));
 ! For the first and last stop we know...;
 @FOR( CITY( K)| K #GT# 1:
U( K) <= N - 1 - ( N - 2) * X( 1, K);
U( K) >= 1 + ( N - 2) * X( K, 1));
END
这个代码更好看一些，实质上是一样的，只是上面那个排版时出了问题！！！
大家注意一下！

wujianjack2 发表于 2015-8-11 09:17

symmetric的其实可以不用这样，assymetric的这样也行，不过，也有更好的解决方案。

wujianjack2 发表于 2015-8-11 18:36

其实我说的是对于不同的类型选择其它更加高效的工具，而不是数据的表示方式。如果用LINGO的话，那么按照如下这种建模方式，对提高这类问题的求解效率应该会有帮助，见截图：

wujianjack2 发表于 2015-8-11 18:38

主要是通过subtour elimination的方式，采用branch and cut的思想。

wujianjack2 发表于 2015-8-11 21:20

  我试了下，如果用普通的建模方式，在我的LINGO上求解花费大致如下：
  Global optimal solution found.
  Objective value:                      7577.00000000
  Objective bound:                      7577.00000000
  Infeasibilities:                            0.00000000000
  Extended solver steps:                         108
  Total solver iterations:                         8505
  Elapsed runtime seconds:                   1.41

  如果用图片中的方式，大概只需要37步迭代，0.05s左右吧。

  如果采用更加复杂的subtour elimination规则，则还可以将求解效率提高至少一个数量级，state of the art implementation就是这么做的。

页: [1]

数学建模社区-数学中国's Archiver

TSP问题及程序