基于Delaunay三角剖分處理二維歐式空間MTSP的近似算法

壽 濤, 劉朝暉

(華東理工大學數學系,上海 200237)

基于Delaunay三角剖分處理二維歐式空間MTSP的近似算法

壽 濤, 劉朝暉

(華東理工大學數學系,上海 200237)

考慮了在二維歐式平面內的多旅行商問題,通過Delaunay三角剖分的方法,將問題轉化為求解多個旅行商問題。樹分解算法的核心是Delaunay邊的空圓性質并且可以證明該算法的近似比為2。最后,通過數值模擬驗證了算法的有效性。

MTSP; Delaunay三角剖分; 近似算法

多旅行商問題(MTSP)是TSP問題的推廣[1]。通常可以把MTSP問題拆分成2個子問題,即:先確定每個旅行商訪問客戶點集;再對每個旅行商訪問的點求解TSP問題。對于MTSP問題的研究,最早可以追溯到1990年Li等[2]的5近似算法。之后Harks等[3]給出了該問題的4近似比算法。Rathinam等[4]在2006年給出了基于歐式距離下MDVRP問題的2近似算法。Malik[5]則在2007年給出了推廣的多旅行商問題的2近似算法。上述文獻中的算法大多基于雙生成樹算法[6]。此外,鄰域搜索算法也是處理MTSP的經典方法,如Aarts等[7]討論了組合優化中鄰域算法的重要性以及Angel[8]對于鄰域算法在各種條件下的最壞情況研究。直到2011年Zhou等[9]給出了理論近似比為(2-1/k)的算法,其中k為旅行商個數,該算法主要基于Christofides算法[10]。

本文將討論在二維平面內MTSP問題:對于平面中點集V={v1,v2,…,vn},D為旅行商集,使得每個V中的每個點當且僅當被一個旅行商訪問,并最小化訪問總路程。隨后引入Delaunay三角剖分概念,進而優化最優路線。

1 Delaunay三角剖分

網格剖分是平面可視化的關鍵技術,早期的網格剖分主要基于矩形和正六邊形,后來為了增加靈活性發展為三角形[11]。在20世紀80年代末,三角形的網格剖分技術已經在船體建模、橋梁受力等實際問題中有著廣泛的應用。本文給出三角剖分的概念,且介紹Delaunay三角剖分。

定義1若由平面上的點集V與其構成的邊集E組成的平面圖G(V,E),滿足下列條件,則稱其為三角剖分:(1) 平面中不含孤立點;(2) 每個面均為三角形,且三角面的合集為該點集的凸包。

若在生成三角剖分的過程中提出若干個優化條件,如最小化邊的總長度、最大化邊的總長度、最大化最小角等,將會得到不同意義下的三角剖分。Delaunay三角剖分是滿足最小角達到最大條件的三角剖分。在二維空間中,對于每個三角剖分總存在一個最小角,值得注意的是這種思想僅在二維空間中成立,因為在三維及更多維空間中,單純體的內角和并不是一個常值[12]。因為這個特性,Delaunay三角剖分總是盡可能避免生成“瘦長”的三角形,進而盡量生成“等邊”的三角形[13]。通常生成Delaunay三角剖分的過程,就是實現三角剖分中所有三角形的外接圓內不含其他點的過程[14]。

定義2給定點集V={v1,v2,…,vn,},將連接其中兩點v1,vj的邊e稱為Delaunay邊,當且僅當存在一個經過v1,vj兩點的圓,且圓內不包含V中的其他點。同時若V的一個三角剖分中只包含Delaunay邊,則稱這個三角剖分為Delaunay三角剖分。

對于給定的點集,通常情況下其Delaunay三角剖分是唯一的,但是當存在四點或多于四點共圓的情形,則該點集的Delaunay三角剖分不唯一。生成Delaunay三角剖分,若從貪心算法出發,則至少要在O(n2)時間內才能完成[13]。如果從最近點意義下的Voronoi圖出發,則可以通過Fortune算法構造Delaunay三角剖分,且時間復雜度為O(nlogn)。定義2可以通過局部變換法的思想實現,該算法通過將邊翻轉的方式來尋找Delaunay邊,直到所有的邊都滿足定義2從而算法終止[15]。事實上,尋找Delaunay邊的過程就是最大化最小角的過程,因為在將邊翻轉的過程中,總是優先生成“等邊”的三角形,同時避免生成“瘦長”的三角形。

定義3在V的Delaunay三角剖分的邊集中,包含一棵V的歐幾里得最小支撐樹,即EMST。

證明 運用反證法,假設T為點集V上的一棵歐幾里得最小支撐樹且在T的邊集中除了邊e其他邊均為Delaunay三角剖分中的邊,那么記T1,T2為邊e連接的2個子樹,且v1,v2為邊e相關聯的點。根據定義2,則可以得到對于經過任意v1,v2兩點的圓內都包含其他點,考慮以邊e為直徑的圓的情況,其中存在一個其他的點a,假設點a為T1上的點。此時將a與v2連接,那么會得到一條比e更短的邊,與假設矛盾,故得證。

2 算法

2.1 樹分解算法

對于給定的點集V,其中點的個數為n,若直接生成EMST,則算法的復雜度為O(n2logn),但是當引入Delaunay三角剖分的方法,則可以將復雜度降低到O(nlogn)。樹分解算法的詳細步驟如下:

(1) 基于所給的點集V,產生Delaunay三角剖分;

(2) 對于Delaunay三角剖分,生成最小支撐樹;

(3) 對最小支撐樹中的邊ei,進行降序排列,即為S;

(4) 從S中依次對最小支撐樹進行刪邊處理:若刪去ei,能保證每個連通分支至少有一個旅行商,則刪去,否則保留;

(5) 重復第4步,直到生成的k個連通分支,其中k為旅行商個數;

(6) 運用雙生成樹算法,產生k條漢密爾頓回路。

2.2 算法近似比

首先介紹一些算法中的記號,把W記作樹分解算法得到的解,d(W)記作W的解值,此外,Wi代表的是由第i個旅行商在近似算法中訪問的客戶點集,TWi表示在近似解中的第i棵子樹。作為對應,在最優解中,OPT記為最優解,d(OPT)記為最優解值,Hi代表的是由第i個旅行商在最優中訪問的客戶點集,THi表示在最優解中的第i棵子樹。

定義4樹分解算法的近似比為2。

證明 情況1:Wi與Hi相同,其中i為1～k中的任意值。

在這種情況下必定會有d(TW)=d(TH),可用反證法證明,將邊重復并刪去重復點生成回路,可得到d(W)≤2d(OPT),故得證該算法的近似比為2。

情況2:在近似解和最優解的子樹中,除了i=k,k′這兩棵子樹不同外,其他子樹均相同,具體細節如圖1所示。

圖1 情況2中的最優解與近似解的子樹Fig.1 Subtree of OPT and W in case 2

在上述情形中,假定Hk包含n1個點,而Hk′包含n2個點,在Wk中包含(n1+1)個點,在Wk′包含(n2-1)個點。對于點xi,根據樹分解算法,若可去邊為e2而不是e1時,則必有e1≤e2,所以必有d(TWk)+d(TWk′)≤d(THk)+d(THk′),從而得證。

情況3:情況3為情況2的補充,具體細節如圖2所示。

圖2 情況3中的最優解與近似解的子樹Fig.2 Subtree of OPT and W in case 3

由于邊e3不與點xi相關聯,可得到d(TWk)+d(TWk′)≤d(THk)+d(THk′)。因為根據算法,若有e3>e2,則最小支撐樹中一定會包含e2。此外由于e1

3 數值模擬

將從TSPLIB數據庫上選取一些例子用于數值模擬,并將結果與Rahinam的2近似算法進行對比。

從TSPLIB數據庫中挑選9個實例(Ei151,Ei176,Rat99,Ch130,Rat195,Tsp225,A280,Lin318,Rd400)并隨機設定旅行商點來對比算法的表現。將Rathinam的2近似算法作為參照[16],下面以ei151為例進行演示。

首先,隨機挑選第3,7,11,25,34,41這6個點作為旅行商。運行樹分解算法,將得到6個環游,依次如下:第1個為14,25,14;第2個為3,20,35,36,3;第3個為11,32,1,22,11;第4個為43,7,23,24,43;第5個為13,41,19,40,42,13;第6個為2,29,21,50,34,30,9,38,5,49,10,16,39,33,45,15,44,37,17,4,18,47,12,46,51,27,48,6,8,26,31,28,2。運行Rathinam的算法可得6個環游:第1個為14,25,14;第2個為43,7,23,24,43;第3個為5,38,11,32,1,22,5;第4個為43,7,23,24,43;第5個為13,41,19,42,40,13;第6個為2,29,21,50,34,30,9,49,10,16,39,33,45,15,44,37,17,4,18,47,12,46,51,27,48,6,8,26,31,28,2。具體細節如表1所示。

表1 不同實例下解值的對比

4 結束語

Delaunay三角剖分是計算幾何中常用的方法,但是在MTSP問題的研究中,卻很少涉及。本文將MTSP問題限定在二維平面中,并將Delaunay三角剖分應用于此,同時引入樹分解算法。該算法的理論性能比與時間復雜度比較穩定,并且在實際的數值模擬中,能處理一些中型的實例問題,且能給出較優的解。

[1] GAREY M R,JOHNSON D S.Computers and Intractability:A Guide to the Theory of NP-Completeness[M].New York:W.H.Freeman,1979:206-218.

[2] LI C L,SIMCHI-LEVI D.Worst-case analysis of heuristics for multidepot capacitated vehicle routing problems[J].Informs Journal on Computing,1990,2(1):64-73.

[3] HARKS T,KONIG F G,MATUSCHKE J.Approximation algorithms for capacitated location routing[J].Transportation Science,2013,47(1):3-22.

[4] RATHINAM S,SENGUPTA R,DARBHA S.A resource allocation algorithm for multivehicle systems with nonholonomic constraints[J].IEEE Transaction on Automation Science,2007,4(1):98-104.

[5] MALIK W,RATHINAM S,DARBHA S.An approximation algorithm for a symmetric generalized multiple depot,multiple travelling salesman problem[J].Operations Research Letters,2007,35(6):747-753.

[6] ROSENKRANTZ D J.An analysis of several heuristics for the traveling salesman problem[J].SIAM Journal of Computing,1977,6(3):563-581.

[7] AARTS E,LEBSTRA J.Local search in combinatorial optimization[D].USA:Princeton University Press,2003.

[8] ANGEL E.A survey of approximation results for local search algorithms[M].Heidelberg:Springer,1970:30-73.

[9] XU Z,XU L,RODRIGUES B.An analysis of the extended Christofides heuristic for the k-depot TSP[J].Operations Research Letters,2011,39(3):218-223.

[10] CHRISTOFIDES N.Worst-Case Analysis of a New Heuristic for the Travelling Salesman Problem[D].USA:Carnegie Mellon University,1976.

[11] 徐永安,楊欽,吳壯志,等.三維約束Delaunay三角化的實現[J].軟件學報,2001,12(1):103-110.

[12] JOE B.Delaunay versus max-min solid angle triangulations for three dimensional mesh generation[J].International Journal of Numerical Methods in Engineering,1991,31(5):987-997.

[13] DE BERG M,VAN KREVELD M,OVERMARS M.Computational geometry:Algorithms and applications[J].Computational Geometry Algorithms & Applications,2013,19(3):333-334.

[14] LEE D T,SCHACHTER B J.Two algorithm for constructing a Delaunay triangulation[J].International Journal of Parallel Programming,1980,9(3):219-242.

[15] MARCUM D L,WEATHERILL N P.Unstructured grid generation using iterative point insertion and local reconnection[J].AIAA Journal,1995,33(9):1619-1625.

[16] RATHINAM S,SENGUPTA R,DARBHA S.A resource allocation algori-thm for multivehicle systems with nonholonomic constraints[J].IEEE Transactions on Automation Science and Engineering,2007,4 (1):98-104.

ApproximateAlgorithmofMTSPon2DEuclideanSpacewithDelaunayTriangulation

SHOUTao,LIUZhao-hui

(DepartmentofMathematics,EastChinaUniversityofScienceandTechnology,Shanghai200237,China)

This paper discussed Multi Travelling Salesman Problem (MTSP) on 2D Euclidean space.This problem could be simplified to solve several TSP by Delaunay Triangulation.It could be proven that the approximate ratio of Tree Decomposed Algorithm was 2 and the core proof was based on empty circle property of Delaunay edge.The paper testified the performance and efficiency of the algorithm by some numerical examples.

MTSP; Delaunay triangulation; approximate algorithm

1006-3080(2017)06-0895-04

10.14135/j.cnki.1006-3080.2017.06.022

2017-01-16

壽 濤(1991-),男,上海人,碩士生,研究方向為優化理論與應用。E-mail:603077928@qq.com

劉朝暉,E-mail:zhliu@ecust.edu.cn

O224

A