一個(gè)求解旅行商問題的松弛算法

董傳波

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

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

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

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

1 數(shù)學(xué)模型

TSP的數(shù)學(xué)模型可以表述如下：

(1)

(2)

(3)

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

(4)

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

(5)

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

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

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

(6)

約束條件(6)具有城市數(shù)量指數(shù)級(jí)的子回路消除約束，但可以完全排除任何可能的子回路。我們提出的松弛策略生成的子回路消除約束是約束條件(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)

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

2 求解TSP的松弛算法

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

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

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

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

(9)

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

求解TSP的松弛方法的詳細(xì)步驟總結(jié)如下：

Step 1 初始化。設(shè)已經(jīng)生成的子回路集合C0=?，將迭代次數(shù)設(shè)為k=0。

Step 3 求解松弛的TSP。求解得到松弛的TSP的最優(yōu)解xk。

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

Step 5 檢驗(yàn)。如果新生成的回路個(gè)數(shù)|Tk|=1，則xk為TSP的最優(yōu)解，停止迭代；否則，更新已經(jīng)生成的子回路集合Ck+1=Ck∪Tk，設(shè)k=k+1，轉(zhuǎn)到Step 2。

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

3 算例分析

3.1 9個(gè)城市的TSP

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

x12+x21≤1，

(10)

x34+x43≤1，

(11)

x56+x67+x75≤2，

(12)

x89+x98≤1。

(13)

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

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

x19+x98+x81≤2，

(14)

x23+x32≤1，

(15)

x46+x64≤1，

(16)

x57+x75≤1。

(17)

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

3.2 TSP庫中的TSP

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

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

表1 松弛算法與DL模型求解TSP的結(jié)果對(duì)比

4 結(jié)論

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