1、TSP问题描述
TSP问题为travelling salesman Problem的缩写，问题描述为：一名旅行商需要从他的住址(home)出发，游历n个城市，之后再返回home。已知所有城市间的旅行成本，问题目标为：这位旅行商应该选择怎样的线路旅游，才能花最少的钱游历一遍所有的城市？
2、TSP问题建模
2.1 参数定义
定义城市的总个数为： n n n，从城市 i i i到城市 j j j的旅行成本为： C i j ， i ∈ n ， j ∈ n C_{ij}，i\in n，j\in n Cij，i∈n，j∈n。
2.2 变量定义
定义0-1变量
2.3 模型建模
2.3.1 目标函数
目标函数表示最小化旅行总费用。
2.3.2 约束条件
约束条件(1)表示每一个城市 i需要离开一次。
约束条件(2)表示每一个城市 i i i需要进入一次。
若仅仅考虑上述问题情景中的描述要去，则约束(1)和(2)已经满足所有条件，但是会出现子路径的情况
如上图所示，旅行商从红色城市出发，上述的路径满足所有的约束条件，但是明显不符合实际情况，所以需要添加额外的子路径消除约束来避免上述情况的发生。
3、 子路径消除约束
3.1 子路径消除不等式一
解释： 对于每一个非空集合 S S S， S S S中城市的个数最多为 n − 1 n-1 n−1个，从 S S S中流出的弧的个数必定大于或者等于一条。将上述图中的子路径的情况套用到这个不等式上，很明显会违反不等式一，所以将这条不等式加入到模型中能够有效消除子路径问题。同时，不等式一会添加的约束个数为：
条约束。
3.2 子路径消除不等式二
解释： 对于每一个集合 S S S， S S S相互链接的弧的个数最多为 ∣ S ∣ − 1 |S|-1 ∣S∣−1条，即只有当 S S S中的城市的个数为 n n n个时，才允许构成环路，这样不等式二也可以避免上述图中的情况发生。同时，不等式二会添加的约束个数为：
条约束。
