旅行商問題（TSP）的兩種模型

TSP簡介

一個商人從一點出發，經過所有點後傳回原點。它需要滿足：除起點和終點外，所有點當且僅當經過一次；起點與終點重合；所有點構成一個連通圖。要求：得到這個商人經過所有點的最短路程。

TSP模型表示

設x[i][j]是一個0-1變量，其中1表示點i與點j之間有連邊，0表示這兩點之間無連邊，值得注意的是：x[i][j]不一定等于x[j][i]。

設c[i][j]表示點i到點j的距離，同理，c[i][j]不一定等于c[j][i]。

目标函數：

min sum(x[i][j]*c[i][j]) i，j分别周遊（部落格中插入公式不會，暫且這麼表示，該公式是一個二維for循環，分别周遊i和j）

限制條件：

根據題目描述：所有點經過且隻經過一次，并且構成一個環，是以任意一點的出度等于入度等于1，即需要滿足如下兩個限制：

1.sum(x[i][j])=1,周遊i （該公式表示點j的入度等于1）

2.sum(x[i][j])=1,周遊j （該公式表示點i的出度等于1）

若隻有以上兩個限制條件，則形成的解中可能會産生若幹個獨立的環，即所有點不能構成一個連通塊。為打破子環的存在，還需加入一個限制條件。基于不同的角度，有兩種不同的限制方式，進而産生兩種不同的TSP數學模型，鑒于網上對兩種模型的比較較少，且介紹較為簡單，同時由于前面幾個目标函數和限制1 2 的意義明确，是以本博文主要想介紹這兩種不同的限制的理由及各自優缺點。

A：sum(x[i][j])<=|S|-1;其中S表示任意一個點的子集（S集合中點的個數大于等于2個，小于CityNum個），例如：TSP中有3個點 a b c,則S表示{a,b},{a,c},{b,c}中的任意一個。上式中i和j在S集合中周遊。解釋：若不滿足該限制，則存在一個TSP的點的子集，使得sum(x[i][j])>=|S|，我們可以很快知道sum(x[i][j]),周遊i和j表示對應子圖中連邊數量（因為x[i][j]=1表示從i到j有連邊），那麼當該子圖構成一個環時，邊的個數等于點的個數。是以，添加該限制能夠保證任意子圖不存在子環，進而保證所有點形成一個連通塊。具體cplex的代碼可以參考我的另一篇博文：https://blog.csdn.net/u011561033/article/details/93380842

B：u[i]-u[j]+(CityNum-1)*x[i][j]<=CityNum-2; i,j 從2個點開始周遊。該公式新定義了一個變量，不用任何初始化操作。需要注意的是這邊的i和j是從2個點開始周遊的，即需要把起點去掉。該公式也能滿足不存在環。因為若x[i][j]=1，表示i到j有連邊，那麼原限制就變成：u[i]-u[j]<=-1 即 u[j]>=u[i]+1它保證u[t]從起點開始随着商人的行走一直遞增，若存在子環，例如a-b-c-a,則會出現u[a]<u[b]<u[c]<u[a]，進而導緻不等式遞推不成立，是以，若滿足公式：u[i]-u[j]+(CityNum-1)*x[i][j]<=CityNum-2;就能保證不存在環。是以，不把起點也包括在内是非常重要的。我就因為一開始把起點包括在内，導緻出現了很多錯誤。

綜上所述，兩種TSP模型各有優缺點，其中A模型易于了解，但随着資料規模增大會導緻S的規模呈指數級上升。B模型了解稍微要難于A模型，但其限制表示友善，便于計算。綜合分析上述兩個模型，我認為還是B模型更好，更能在程式中進行表示。具體cplex的代碼可以參考我的另一篇博文：https://blog.csdn.net/u011561033/article/details/93408062

據說當點的規模超過100時，上述cplex代碼中的兩種方法都将不再适用，需要加入column generate的技巧，等我嘗試後再更新。