数学建模社区-数学中国

标题: TSP问题及程序 [打印本页]
作者: 森之张卫东    时间: 2015-8-10 21:16
标题: TSP问题及程序

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

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

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

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


  1. <p>MODEL:</p><p>  SETS:
  2.   CITY / 1.. 10/: U; <font style="background-color: lime;">! U( I) = sequence no. of city;</font>
  3.   LINK( CITY, CITY):
  4.        DIST, <font style="background-color: lime;"> ! The distance matrix;</font>
  5.           X; <font style="background-color: lime;"> ! X( I, J) = 1 if we use link I, J;</font>
  6. ENDSETS</p><p> DATA:   <font style="background-color: lime;">!Distance matrix, it need not be symmetric;</font>
  7.   DIST =0     8     5     9    12    14    12    16    17    22
  8.      8     0     9    15    17     8    11    18    14    22
  9.      5     9     0     7     9    11     7    12    12    17
  10.      9    15     7     0     3    17    10     7    15    18
  11.     12    17     9     3     0     8    10     6    15    15
  12.     14     8    11    17     8     0     9    14     8    16
  13.     12    11     7    10    10     9     0     8     6    11
  14.     16    18    12     7     6    14     8     0    11    11
  15.     17    14    12    15    15     8     6    11     0    10
  16.     22    22    17    18    15    16    11    11    10     0;
  17. ENDDATA</p><p><font style="background-color: lime;"> !The model:Ref. Desrochers & Laporte, OR Letters,  Feb. 91;</font>
  18.   N = @SIZE( CITY);
  19.   MIN = @SUM( LINK: DIST * X);
  20.   @FOR( CITY( K):
  21. <font style="background-color: lime;">  !  It must be entered;</font>
  22.    @SUM( CITY( I)| I #NE# K: X( I, K)) = 1;
  23. <font style="background-color: lime;"> !  It must be departed;</font>
  24.    @SUM( CITY( J)| J #NE# K: X( K, J)) = 1;
  25. <font style="background-color: lime;"> ! Weak form of the subtour breaking constraints;
  26.   ! These are not very powerful for large problems;</font>
  27.    @FOR( CITY( J)| J #GT# 1 #AND# J #NE# K:
  28.        U( J) >= U( K) + X ( K, J) -
  29.        ( N - 2) * ( 1 - X( K, J)) +
  30.        ( N - 3) * X( J, K))      );
  31. <font style="background-color: lime;">  ! Make the X's 0/1;</font>
  32.   @FOR( LINK: @BIN( X));
  33. <font style="background-color: lime;">  ! For the first and last stop we know...;</font>
  34.   @FOR( CITY( K)| K #GT# 1:
  35.    U( K) <= N - 1 - ( N - 2) * X( 1, K);
  36.    U( K) >= 1  + ( N - 2) * X( K, 1));
  37. END</p>
复制代码

Matlab可以解决TSP问题，但人们更常用的是Lingo，所以附上LIngo代码。




作者: 森之张卫东    时间: 2015-8-10 21:20
  1. MODEL:

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

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

  23. !The model:Ref. Desrochers & Laporte, OR Letters,  Feb. 91;
  24.   N = @SIZE( CITY);
  25.   MIN = @SUM( LINK: DIST * X);
  26.   @FOR( CITY( K):
  27.   !  It must be entered;
  28.    @SUM( CITY( I)| I #NE# K: X( I, K)) = 1;
  29.   !  It must be departed;
  30.    @SUM( CITY( J)| J #NE# K: X( K, J)) = 1;
  31.   ! Weak form of the subtour breaking constraints;
  32.   ! These are not very powerful for large problems;
  33.    @FOR( CITY( J)| J #GT# 1 #AND# J #NE# K:
  34.        U( J) >= U( K) + X ( K, J) -
  35.        ( N - 2) * ( 1 - X( K, J)) +
  36.        ( N - 3) * X( J, K)));
  37.   ! Make the X's 0/1;
  38.   @FOR( LINK: @BIN( X));
  39.   ! For the first and last stop we know...;
  40.   @FOR( CITY( K)| K #GT# 1:
  41.    U( K) <= N - 1 - ( N - 2) * X( 1, K);
  42.    U( K) >= 1  + ( N - 2) * X( K, 1));
  43. END
复制代码
这个代码更好看一些，实质上是一样的，只是上面那个排版时出了问题！！！
大家注意一下！
作者: wujianjack2    时间: 2015-8-11 09:17
  symmetric的其实可以不用这样，assymetric的这样也行，不过，也有更好的解决方案。
作者: wujianjack2    时间: 2015-8-11 18:36
  其实我说的是对于不同的类型选择其它更加高效的工具，而不是数据的表示方式。如果用LINGO的话，那么按照如下这种建模方式，对提高这类问题的求解效率应该会有帮助，见截图：


tspcutx.png (231.12 KB, 下载次数: 172)

tspcutx.png

作者: 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就是这么做的。





欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5