一個求解旅行商問題的松弛算法

董傳波

(中國航空油料集團有限公司，北京 100088)

旅行商問題(TSP)是運籌學領域典型的組合優化問題，其目的是在一個完全圖G=(N,A)中找到費用最小的哈密頓回路。其中,N={1,…,n}表示城市構成的集合，A={(i,j)|i∈N,j∈N,i≠j}表示邊構成的集合。TSP在實際中具有非常廣泛的應用，例如，機組調度[1]、熱軋調度[2]、采訪日程安排[3]、自主移動機器人任務規劃[4]、印刷機調度[5]等。由于TSP是一類具有二元決策變量的NP-hard問題[6]，啟發式算法常被用于解決這類問題，包括蟻群算法、遺傳算法、局部搜索、神經網絡、模擬退火、禁忌搜索等[7-12]。然而，這類算法存在解的最優性無法保證、實際應用中的解釋性不好等缺陷。因此，有必要設計TSP的全局最優求解算法[13-19]。

Dantzig等[13]首次提出了TSP問題的數學規劃模型，即Dantzig-Fulkerson-Johnson(DFJ)模型。該模型除了包括決策變量的二元約束以外，還包括分配約束和子回路消除約束。然而，由于該數學模型的約束條件數量是城市數量的指數級，導致利用該模型在求解大規模TSP時變得不可行。因此，有必要構建只有多項式數量約束條件的TSP數學模型以提高求解效率。Miller等[14]提出了一個具有多項式約束數的混合整數規劃模型來描述TSP。隨后，Desrochers等[15-16]改進了該模型。混合整數規劃問題通常可以采用分支定界法來精確求解。然而，由于受變量數和約束條件數量的限制，TSP可求解的問題規模仍然有限。

Sarin等[17]的數值結果表明，約束條件個數對求解TSP最優解起著至關重要的作用。雖然TSP具有指數級數量的子回路消除約束，但是大多數約束都是不起作用約束。研究有效的方法來給出起作用的子回路消除約束，可以潛在地加快TSP的求解速度。本文提出了一個求解TSP的松弛方法，通過求解一系列線性整數規劃問題(LIP)來得到起作用的子回路消除約束，不斷地把新找到的起作用子回路約束添加到松弛問題中，逐步實現TSP的精確求解。

1 數學模型

TSP的數學模型可以表述如下：

(1)

(2)

(3)

xij∈{0,1},?i∈N,j∈N，

(4)

{(i,j):i∈N,j∈N;xij=1}不構成子回路，

(5)

其中，xij為0-1變量，表示路段(i,j)是否在最優的旅行路徑中，即推銷員是否通過該路段。cij表示從城市i到城市j所需要的花費。

目標函數(1)表示總的旅行費用最小；約束條件(2)～(4)為TSP的分配松弛約束，約束條件(2)和(3)意味著最優路徑上任意一個城市都只有一條邊進入和一條邊離開，約束條件(2)保證推銷員只能經過一個城市i到達城市j，約束條件(3)保證推銷員只能經過一個城市j到達城市i；約束條件(4)表示變量xij是0-1變量；約束條件(5)用于避免子回路。該約束條件有不同的數學表述形式[13-16]。

在DFJ模型中，子回路消除約束可以表述如下[13]:

(6)

約束條件(6)具有城市數量指數級的子回路消除約束，但可以完全排除任何可能的子回路。我們提出的松弛策略生成的子回路消除約束是約束條件(6)的子集。

Desrochers等[15]提出了如下約束條件來代替子回路消除約束：

SDL={x:? {u1,…,un},u1≡0,使得

uj≥(ui+1)-(n-1)(1-xij)+(n-3)xji,?i,j≥2,i≠j，

(7)

1+(1-x1j)+(n-3)xj1≤uj≤(n-1)-(n-3)x1j-(1-xj1),?j≥2}，

(8)

當約束條件(8)是起作用約束時，約束條件(7)是最大平面定義[18]。

2 求解TSP的松弛算法

如下命題是本文提出的方法的理論基礎：

命題1：對于滿足分配約束條件(2)～(4)的任意可行解x=[xij,i∈N,j∈N]，可以把x分解為一組回路，且分解得到的回路數量不小于1。

證明：根據約束條件(3)，對于給定的任意一個節點i∈N，我們可以找到有且僅有的一個節點i1∈N滿足xii1=1。這意味著推銷員從城市i到達城市i1。同理存在一個節點i2使得xi1i2=1。以此類推我們可以得到一個城市序列Si=(i,i1,i2,…,im)，這個序列滿足：xikik+1=1,?k=1,…,m-1；i≠i1≠i2≠…≠im-1，其中，im∈{i,i1,i2,…,im-1}。當im=i就意味著Si是一個回路。該城市序列的生成保證了序列的存在性。如果m=|N|那么就只有一個回路，否則對于可行解x來說至少包含一個回路。特別地當m=1時節點i自身形成一個回路。證畢。

如果我們把約束條件(5)從TSP的模型中去掉，則TSP被松弛為了一個指派問題(AP)。我們可以采用匈牙利算法快速求解得到AP的最優解。如果得到的最優解只有一個回路，則該解也是TSP的最優解。如果AP的最優解包含多個回路，則需要在AP問題的基礎上添加起作用的子回路消除約束。為了簡化表示，我們令T表示已經生成的子回路集合，At表示子回路t上的路段集合，mt表示該回路上路段的數量。起作用的子回路消除約束表述如下：

(9)

把約束條件(9)加入到AP中，我們可以得到松弛的TSP。由于該松弛問題是線性整數規劃問題，我們可以采用分支定界算法來進行求解。通過求解松弛問題，我們可以得到松弛問題的最優解。該解也可以分解成為一組子回路。如果得到的新的最優解中只有一個回路，則該解就是TSP的最優解。否則，將新生成的一組子回路加入到已經生成的子回路集合中。然后根據新的已經生成的子回路集合生成子回路消除約束(9)，形成新的松弛TSP，然后通過分支定界算法求解，重復上步驟，直到松弛的TSP的最優解只有一個回路，即得到TSP的最優解。

求解TSP的松弛方法的詳細步驟總結如下：

Step 1 初始化。設已經生成的子回路集合C0=?，將迭代次數設為k=0。

Step 3 求解松弛的TSP。求解得到松弛的TSP的最優解xk。

Step 4 生成子回路。把xk分解成一組回路，生成新的回路集合Tk。

Step 5 檢驗。如果新生成的回路個數|Tk|=1，則xk為TSP的最優解，停止迭代；否則，更新已經生成的子回路集合Ck+1=Ck∪Tk，設k=k+1，轉到Step 2。

由于TSP的子回路消除約束的數量有限，本文提出的松弛算法具有全局收斂性。在我們的方法中，生成的子回路消除約束的個數隨著迭代次數的增加而增加，最壞的情形是生成所有子回路消除約束。

3 算例分析

3.1 9個城市的TSP

考慮如圖1所示的9個城市的對稱TSP,我們通過城市的坐標來獲取任意兩個城市間的出行費用。通過求解AP，我們可以得到4個子回路：1→2→1、3→4→3、5→6→7→5和8→9→8。AP的目標函數值35.685。這4個子回路可以生成4個子回路消除約束：

x12+x21≤1，

(10)

x34+x43≤1，

(11)

x56+x67+x75≤2，

(12)

x89+x98≤1。

(13)

圖1 9個城市的TSP問題Fig.1 A TSP problem involving nine cities

把生成子回路消除約束(10)～(13)添加到AP中，構造松弛的TSP。該松弛TSP的可行解可以避免已經出現的子回路再次出現。松弛的TSP的最優解可以生成4個新的子回路：1→9→8→1、2→3→2、4→6→4和5→7→5。此時，總的出行費用為35.773，并可以生成新的子回路消除約束如下：

x19+x98+x81≤2，

(14)

x23+x32≤1，

(15)

x46+x64≤1，

(16)

x57+x75≤1。

(17)

將約束條件(14)～(17)添加到上述松弛的TSP中，可以得到新的松弛的TSP。通過求解該松弛的TSP，我們可以得到最優解為1→2→3→4→6→5→7→8→9→1，總的出行費用為35.834。該最優解只含有一個子回路，因此也是原始TSP的最優解。

3.2 TSP庫中的TSP

我們采用TSP庫中的問題來驗證提出的方法的有效性,采用IBM ILOG CPLEX 12.5求解LIP子問題。所有計算均在具有Intel(R)Core(TM)i5-2400 3.10GHz CPU和8GB RAM的計算機上運行。已有的研究表明，DL模型的求解速度在整體上比其他模型快[16-17]。因此，本文只對比所提出的方法和直接求解DL模型。

表1中給出的結果表明，所提出的方法和DL模型都可以得到TSP的最優解，且大多數情況下，提出的松弛方法具有更高的求解效率。通過求解一些規模較大的問題(如rbg323、rbg358)可以明顯看到，本文方法比求解DL模型具有更快的求解效率,所提出的方法對求解效率的提升主要得益于子回路消除約束條件數量的減少。表1中的結果表明，所提出的方法只需要小于3n個起作用子回路消除約束。因此，對于某些TSP，有效子回路消除約束的大小是O(n)。

表1 松弛算法與DL模型求解TSP的結果對比

4 結論

本文提出了通過求解松弛的TSP來確定TSP問題的有效子回路消除約束，并基于有效子回路消除約束實現TSP的全局最優求解。所提出方法的每個松弛問題的約束規模大小可以減少到O(n)，可以大大減少TSP求解所需要的迭代次數和CUP時間。通過求解大量TSP，驗證了本文方法的可行性以及求解效率。結果表明，本文提出的方法在計算效率方面明顯優于直接采用Cplex求解TSP的DL模型。