1 TSP经典模型
1.1 DFJ模型
引文格式：
| G.B. Dantzig, D.R. Fulkerson and S.M. Johnson, "Solution of a large scale traveling salesman problem", Oper. Res. 2, 393-410(1954). |
模型表述：
1.2 MTZ模型
引文格式：
C.E. Miller, A.W. Tucker and R.A. Zemlin, "Integer programming formulations and traveling salesman problems", J. ACM 7,
326-329 (1960).
数学表述：
引入了自由变量来消除子路径
是一个比较弱的LP松弛，其可行解并不是一个凸多边形平面
2 模型分析与经典文献赏析
DFJ模型可以较为容易的拓展到CVRP中，但拓展到DVRP中就不那么容易了更不用说要拓展到VRPTW中了
MTZ模型的子路径消除约束可与其他强约束合并
原文赏读：
3 模型拓展与Lingo源码
3.1 拓展模型表述
3.2 Lingo源代码
MODEL: SETS: CITY / 1.. 6/: U; ! U( I) = 顾客编号序列; LINK( CITY, CITY): DIST, ! 距离矩阵; X; ! 二进制变量，根据链接(i,j)是否被访问决定X( I, J) = 1或0 ; ENDSETS DATA: !距离矩阵，可以是对称矩阵也可以使非对称矩阵; DIST =0 56 35 21 51 60 56 0 21 57 78 70 35 21 0 36 68 68 21 57 36 0 51 61 51 78 68 51 0 13 60 70 68 61 13 0; ENDDATA !模型参考文献：Desrochers, M., & Laporte, G. (1991). Improvements and extensions to the Miller-Tucker-Zemlin subtour elimination constraints. Operations Research Letters, 10(1), 27–36.; !doi:10.1016/0167-6377(91)90083-2?; N = @SIZE( CITY); MIN = @SUM( LINK: DIST * X); @FOR( CITY( K): @SUM( CITY( I)| I #NE# K: X( I, K) ) = 1; ! 必须到达顾客点k; @SUM( CITY( J)| J #NE# K: X( K, J) ) = 1; ! 必须从顾客点k离开 @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( LINK: @BIN( X)); ! 二进制变量约束; @FOR( CITY( K)| K #GT# 1: U( K) <= N - 1 - ( N - 2) * X( 1, K); U( K) >= 1 + ( N - 2) * X( K, 1) ); END
