基于最優插入子集的動態規劃算法求解旅行商問題

但 開 段隆振

(南昌大學信息工程學院 江西 南昌 330031)

0 引 言

經典的旅行商問題(Travelling Salesman Problem,TSP)可以描述為：給定一組城市,這些城市之間的距離已知,尋找一條經過所有城市一次且僅一次并返回起始城市的最短路線。旅行商問題有著廣泛的實際應用,生活中經常出現的各類組合優化問題都可以歸為旅行商這類問題。如物資運輸路線中,汽車應走怎樣的路線使路程最短[1]；大型工業制件在增材制造中的路徑規劃[2]；CNC在線檢測中,如何盡可能縮短檢測路徑長度[3]；在航海相關問題中,無人駕駛船舶路徑規劃或船舶航線自動生成[4]；多無人機協同作業中,規劃出符合無人機機動性能約束和安全要求的最優航跡的問題[5]等。

三角不等式是TSP的一個很自然的限制：對任意三座城市A、B和C,從A到C的路程加上從C到B的路程應該大于等于從A到B的路程。旅行成本是對稱的,而且滿足三角不等式的題目稱為TSP的度量(metric)題目。當把城市視為平面上的點,許多距離計算方式都滿足這個自然條件,例如城市距離為歐幾里得距離(Euclidean distance)、曼哈頓距離(Manhattan distance)、切比雪夫距離(Chebyshev distance)的TSP都屬此類。如果兩個城市之間的距離是相應的歐幾里得距離,且兩個城市之間的距離在兩個方向上都是相同的,這樣的TSP稱為對稱的Euclidean TSP。許多自然實例都是對稱的Euclidean TSP。

旅行商問題的最優化求解非常困難,其最根本的原因是求解這些問題的現有算法需要極長的運行時間以及極大的存儲空間,以至于根本不可能在現有的計算機上實現,即存在所謂的“組合爆炸”。例如31個城市的旅行商問題,使用窮舉法需要遍歷30!/2種排列。如果使用目前我國排名第一的超級計算機——神威太湖之光(Sunway TaihuLight,含有10 649 600個處理器,運算速度可達每秒125 436萬億次),假設檢驗每條路線只需要一次算術運算,那么解決這道31個城市的TSP問題預計需要超過3 352萬年。

通過Cook[6]和Karp[7]的理論,可以將旅行商問題和許多其他問題聯系起來。很多的組合優化問題,比如背包問題、車間調度問題、分配問題都和旅行商問題同屬于NP完全問題。如果其中任意一個能用多項式確定性算法解決,那么其他所有NP完全問題也能用多項式算法解決。事實上,有很多方法本來是研究旅行商問題時提出來的,經過不斷的發展,后來又推廣到了其他NP完全問題上去。

動態規劃(Dynamic Programming)是解決多階段決策過程最優化的一種數學方法。在多階段決策過程中,動態規劃方法將問題的過程分成幾個相互聯系的階段,恰當地選取狀態變量和決策變量及定義最優值函數,從而把一個大問題化成一組同類型的子問題,然后逐個求解。即從邊界條件開始,逐段遞推尋優,在每一個子問題的求解中,均利用了它前面的子問題的最優化結果,依次進行,最后一個子問題所得的最優解,就是整個問題的最優解。動態規劃的方法在電網調峰[8]、航天航空[9]和保險金融[10]等領域中都有廣泛的應用。

已知求解旅行商問題的精確算法的運行時間界限是Held-Karp[11]動態規劃法的O(n22n),這個紀錄已經保持了58年。如果能突破這個界限,哪怕只是一點點改進,也有可能獲得更快的時間界限,就有可能適用于實際應用,從而推進旅行商問題的實戰前線。

1 簡單插入與兩個猜想

1.1 簡單插入

插入算法(Insertion Algorithm)的思路是從一條周游幾個城市的子路線出發,逐個增加新的城市并插入到合適位置,直至得到一條包含所有城市的新路線。算法核心部分的偽代碼為：

Begin

設算法運行過程中M為當前子路線；

根據新城市選取函數選取待插入城市i；

根據插入位點選取函數選取插入位點p；

M.insert(p,i)；

if所有城市均在M中：

返回M；

else：

進行下一步插入操作；

End

其中插入位點選取的規則是遍歷所有可插入位點,計算插入后的路線長度,其中最短路線長度所對應的位點作為插入位點。將這條規則稱作簡單選取規則,通過簡單選取規則進行的插入稱為簡單插入。

1.2 一個插入法的實例

例1十三個城市的TSP,城市從0到12依次編號,城市橫坐標依次為{466,826,555,79,781,251,329,336,978,793,489,496,735},城市縱坐標依次為{407,389,485,264,618,766,640,670,195,15,714,218,438}。

其最優路線為[7,6,2,0,3,11,9,8,1,12,4,10,5],最優路線長為3 082個單位長度,如圖1所示。

圖1 例1的最優路線

對于旅行商問題,有兩個最基本定理,分別是交叉避免和凸包規則。

交叉避免：最優路線不會自交,因此在解題過程中應避免出現交叉的情況。

用一步2-opt可以證明這個事實,若巡回路徑中存在交叉路徑,則打開交叉路徑得到的路徑長度一定小于原路徑長度。

凸包規則：最優路線中經過邊界各點的順序和凸包邊界經過邊界各點的順序相同。它們在邊界上的順序與在最優路線上的順序相同,其余城市的順序則是由邊界向內側拐入短的子路徑而得。

最優路線需要避免自交,所以經過邊界各點的順序必須和凸包邊界經過邊界各點的順序相同。

對于例1,使用凸核插入法,即初始子路線從城市點集的凸包開始,插入位點選取規則不變,遍歷所有可能的插入順序,可能得到的結果只有4種,如圖2所示。其中路線長度最小為3 106個單位長度,大于最優路線的3 082個單位長度。

圖2 凸核插入法求解例1的所有可能結果

作為近似算法而言,在插入法中加入能夠把握整體形狀的初始子路線可以在插入城市的過程不斷完善細節,往往能得到比不加入初始子路線更優質的路線。但在尋找最優解方面,由于插入法在插入過程中不會改變已插入的城市排列,所以加入的初始子路線首先必須保證其排列與其在最優路線上的排列一致。即使找到凸包這種特殊的初始子路線滿足排列一致的條件,例1也說明了其有可能無法達到最優解。

1.3 簡單插入最優性猜想

例1已經指出增加初始子路線的做法會使得最優解被排除在算法的解空間之外,那么,不指定初始子路線,用簡單插入的方式,遍歷所有的城市插入順序,是否必定能得到最優解呢？對于例1,按照插入順序5→10→4→12→11→1→8→6→2→0→9→3→7,可以得到最優解,如圖3所示。

圖3 不指定初始子路線基于簡單插入的例1最優解插入過程

針對對稱的Euclidean TSP,考慮如下猜想。

簡單插入最優性猜想：對于任意TSP,依據簡單選取規則的插入法的所有可能中,必定包括TSP的最優解。

1.4 插入過程與插座

定義1對于任意的TSP,從其最優路線中選擇任一城市a剔除,剩下的城市排列為城市a的插座。

定理1通過將a簡單插入a的插座中得到的必定是最優路線。

證明：用反證法。

若將a簡單插入a的插座中得到的不是最優路線,設a插入的位點為i,最優路線中a的插入位點為j,根據簡單插入的定義,有插入i后的路線長度tour(i)小于插入j后的路線長度tour(j),這與最優路徑長度最短的定義矛盾。證畢。

插座本身可以看作原問題規模減一的TSP,如果插座中的城市排列恰好是這個子問題的最優解,這樣的插座稱為同型插座,其他的不是子問題最優解的則稱為異型插座。城市數量為n的TSP,插座總數為n。

1.5 同型插座猜想

易知,存在異型插座數量為0情形(n個城市的凸包),那么存在同型插座數量為0的情形嗎？

針對對稱的Euclidean TSP,考慮如下猜想。

同型插座猜想：對于任意TSP,必然存在同型插座。

根據定理1,對于任意TSP,其最優解可以由其中一個城市通過簡單插入操作插入到與其對應的插座中得到。而根據同型插座猜想,對于任意TSP,必然存在同型插座,同型插座即為子集的最優解。結合定理1以及同型插座猜想,由數學歸納法即可推出下面的同型插座猜想的推論。

同型插座猜想的推論：對于任意TSP,依據簡單選取規則,必然存在這樣插入過程：插入中每一步的子路線都是當前的TSP最優解。

這樣的插入過程中可以根據子路線中不同城市的數量分為n個階段,每個階段所有子路線的集合稱為該階段的最優插入子集。

圖3中的插入過程就是這一推論的一個例子,在每一步的插入過程中,其插入后形成的路線都是當前已插入城市組成的子問題的最優解。

1.6 同型插座數量分布規律的統計分析

在1 000×1 000正方形區域內隨機取m個點的坐標數據,這些數據構成了城市規模為m的旅行商問題,用X表示這個旅行商問題的同型插座數量,X是一個隨機變量,它的概率密度記為f(x),其均值為μ,標準差為σ。設X1,X2,…,Xn表示來自f(x)的一列獨立的隨機變量。根據中心極限定理,當n很大時(在實際的抽樣中,一般當樣本容量大于等于30時就可以應用中心極限定理),隨機變量Yn近似地服從正態分布N(nμ,nσ2)。

已知Yn的概率分布模型,可以利用樣本的密度構造似然函數求出μ和σ2的極大似然估計值。Yn的似然函數為：

(1)

對式(1)兩邊取對數：

(2)

對式(2)求偏導：

解得：

考慮一般情況,假設城市個數為n的所有TSP組成一個集合Un,用Cm表示Un中異型插座的數量為m個的所有元素集合,m=0,1,…,n。如果同型插座猜想成立,那么對于任意Un,可知Cn=??？紤]三個城市的TSP,其所有排列方式都是等價的,換言之,三個城市的TSP只有一條路線,這條路線即為最佳路線。根據插座理論可知,四個城市的TSP有四個插座,這些插座都是三個城市,又因為三個城市只有一種可能路線(即最佳路線),所以四個插座皆為同型插座。如果同型插座猜想不成立,則存在城市個數為k的TSP不存在同型插座。綜上所述,k應該大于等于5。

表1 插座型號數量分布實驗的數據

從表1同型插座數量頻數分布的實驗數據中可以看出,同型插座為1的情形,在城市數量大于7時開始出現,且不同城市數量的3萬次獨立實驗中出現的頻數均為個位數,計算其平均頻率為0.000 103；同型插座為0的情形,在實驗中沒有出現過一次。這樣的實驗結果有兩種可能：(1) 同型插座猜想成立,任意TSP至少存在一個同型插座；(2) 存在同型插座猜想的反例,即存在同型插座數量為0的TSP,但反例的出現是極小概率的事件,以至于在本次實驗中未出現。

假設同型插座猜想存在反例。根據伯努利大數定律,當n足夠大時,事件A出現的頻率將接近于其發生的概率。比如同型插座數量為1的情形,用頻率估計其概率,概率約為萬分之一。同型插座數量為0的情形,頻率為0,根據假設其概率不為0,那么,其概率必然遠小于萬分之一。

從圖4中可以看出,同型插座的分布形態隨著城市個數的增加,越來越接近兩邊少、中間多的鐘形分布概率模型。在典型的鐘形分布即正態分布中,如果a小于標準差μ,那么P{x

圖4 同型插座的頻數分布

如果考慮同型插座數量小于4的情形,從圖5中可以看到隨著城市個數的增加,其出現的次數是遞減的,這意味著隨著問題規模增加,同型插座數量小于4出現的概率在下降。

圖5 同型插座數量小于4的頻數隨城市規模的變化

綜上所述,同型插座猜想的反例即使存在,也是小概率事件,而且隨著城市規模越大,這個概率呈減小的趨勢。

2 算法設計與實現

2.1 基于簡單插入子集的動態規劃法

考慮n座城市的TSP題目,城市從1到n依次編號命名。依據簡單插入子集中的城市數量可以劃分為不同的階段,用k表示,k分別等于1,2,…,n。

以城市集{1,2,3,4,5}為例,城市數量為3的子集有{1,2,3}、{1,2,4}、{1,2,5}、{1,3,4}、{1,3,5}、{1,4,5}、{2,3,4}、{2,3,5}、{2,4,5}、{3,4,5}共10個,因為三個城市的路線實際只有一條,這里每一個城市子集對應一個子路線,所以第三階段有10個狀態。

其城市數量為4的子集有{1,2,3,4}、{1,2,3,5}、{1,2,4,5}、{1,3,4,5}、{2,3,4,5}共5個。其中{1,2,3,4}可由{1,2,3}插入4、{1,2,4}插入3、{1,3,4}插入2、{2,3,4}插入1這四種情況得到相應的簡單插入子路線,這四條路線有可能重復,記錄下不同的成為第四階段的一個狀態。一般第四階段以后,每個城市子集都有可能對應多個子路線,至少為一個,且不同題目對應不同的數量。

第五階段的城市子集為{1,2,3,4,5},可由{1,2,3,4}插入5、{1,2,3,5}插入4、{1,2,4,5}插入3、{1,3,4,5}插入2、{2,3,4,5}插入1得到。以{1,2,3,4}插入5的情況為例,在第四階段找到城市子集{1,2,3,4}對應的簡單插入子路線,假如有a條子路線,那么就將城市5逐個插入其中,記錄下不重復的新的子路線。

在最后一個階段的狀態轉移完成后,會得到{1,2,3,4,5}所對應的多條簡單插入子路線,根據簡單插入最優性猜想,最優解必在其中,此時只要計算這些路線的長度,最短的那條即為該旅行商問題的最短旅行路線。

2.2 基于最優插入子集的新動態規劃法

依據同型插座猜想的推論,TSP的最優解可以通過同型插座進行簡單插入得到,城市個數為n的TSP有n個插座,這些插座可能為同型,也可能為異型。同型插座猜想指出這n個插座中必然存在一個同型插座。n個插座對應n個TSP的子問題,這些城市個數為n的TSP都有最優解,它們與插座的關系是,同型插座等價于子問題的最優解,異型插座不是子問題的最優解。

假設我們知道所有城市個數為n的子問題的最優解,那么這些最優解中必然至少有一個會是原問題的同型插座,對所有這些最優解進行簡單插入,假設a為插入城市,那么可能的結果只有兩種,(1) (城市a)+(a的同型插座)=最優解；(2) (城市a)+(非插座)=非最優解,由前文得知第一種結果必定存在,因此可以遍歷所有結果,其中路線長度最小的即為最優解。同時,城市個數為n-1的子問題的最優解可以如法炮制,從城市個數為n-2的子問題中得到,即滿足無后效性(馬爾可夫性)。因此,可以從城市個數為3(3個城市無須排列即為最優路線)開始,逐步求得城市個數為4,5,…，n的最優解。

根據同型插座猜想的推論,必然存在這樣插入過程：插入中每一步的子集都是當前的TSP最優解,這樣的子集稱為最優插入子集。這是簡單插入最優性猜想的一個特例。與基于簡單插入子集的動態規劃法相比,新動態規劃法只需關注簡單插入子集中最優的部分,有效減少了每個階段的狀態數量,因此,算法的效率得到了提升。

城市個數為n的TSP,共有2n個子集(包括它自己和空集,事實上算法是從城市數目為3的子集開始的,為方便計算,此處增加到最大值2n),在每一個子集中,至多有n個插座,對每一個插座,主要操作為復雜度為n的簡單插入。2n乘以n再乘以n,所以新動態規劃法的時間復雜度為O(n22n)。

由于動態規劃法本身存在的“維數障礙”,在電子計算機上計算時,每遞推一段,都必須把前一段算出的最優值函數在相應的狀態集合上的全部值存入內存中,因而當維數增大時,所需的內存量會呈指數倍增長。在新動態規劃法中,每一個城市子集都對應一個狀態,一共有2n個城市子集,每個城市子集最多有n個城市,因此空間復雜度為O(n2n)。

2.3 算法實現

算法運行的硬件環境為Intel Core i5- 3320M CPU,2.6 GHz,4 GB內存,開發環境為Python 3.7。實驗采用TSPLIB上的不同數據集,驗證算法在各種潛在樣本上的有效性。實驗采用了eg7146、kz9976、mo14185、xqg237和xql662的實驗數據,每次實驗隨機選擇數據集中的12個城市,用Held-Karp動態規劃法(HK),基于簡單插入子集的動態規劃法(簡插法),基于最優插入子集的動態規劃法(優插法)計算得到結果,表2是一次實驗的數據。

表2 在不同數據集上的一次實驗結果

這樣的實驗重復進行一萬次,實驗結果解異同均為TRUE,即三種算法的解都是最優解。這初步表明在不同數據集中,基于最優插入子集的動態規劃法能有效求得最優解。

3 結 語

基于簡單插入子集的動態規劃法的理論依據是簡單插入最優性猜想。這一猜想理論上的證明或許能帶來對TSP結構上的深入認識。

基于最優插入子集的動態規劃法的理論依據是同型插座猜想。對于同型插座猜想,實驗測試的統計分析表明它有可能存在反例,但是即使存在反例,其在實際情況中出現的概率極小。而且城市規模越大,反例出現的概率越接近0。

如果無數多的猴子在無數多的打字機上隨機地打字,并持續無限久的時間,那么在某個時候,它們必然會打出莎士比亞的全部著作。這個設想本身在現實生活中是不可能重現的,就像一個房間內的空氣總是均勻分布的。同型插座猜想可能也有類似的性質,理論上存在反例,但實際遇到的TSP都滿足同型插座猜想。算法實現中采用了TSPLIB上的不同數據集,基于最優插入子集的動態規劃法均能找到最優解,實驗結果在一定程度上支持了這種觀點。

新動態規劃算法為求解旅行商問題提供了新的思路,對于認識、分析眾多復雜問題具有一定的啟示,對促進組合優化問題的研究有著積極的作用。如果將其與其他啟發式算法融合或許會催生出性能優異的新算法,這將給實際解決大規模TSP問題提供新的方案。