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代码。

森之张卫东

1. MODEL:
   
2. 
   
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
   
9. 
   
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
    
22. 
    
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

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

wujianjack2

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

wujianjack2

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

wujianjack2

  我试了下，如果用普通的建模方式，在我的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就是这么做的。