天天看點

旅行商問題(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的技巧,等我嘗試後再更新。

繼續閱讀