【摘要】：Delaunay三角剖分作為處理空間中實(shí)體聚類分析中的有效技術(shù)之一,本文將其引入并將MTSP問(wèn)題限制在二維歐式平面內(nèi)結(jié)合最小支撐樹(shù)和雙生成樹(shù)算法思想,從而得到樹(shù)分解算法。通過(guò)對(duì)樹(shù)分解算法的理論分析,得到該算法能在輸入規(guī)模O(nlogn)時(shí)間內(nèi)生成一個(gè)不會(huì)超過(guò)最優(yōu)解的2倍的近似解。為了分析樹(shù)分解算法在具體實(shí)例上的表現(xiàn),在數(shù)值模擬部分中,通過(guò)多角度的對(duì)比,首先是該算法和Zhou Xu等人的(2-1/k)算法的比較,得出樹(shù)分解算法能在復(fù)雜度和解的質(zhì)量上都優(yōu)于Zhou Xu等人的算法,接著對(duì)比近似比同為2的Rathinam等人的算法,并通過(guò)模擬TSPLIB上的多個(gè)實(shí)例,得出隨著實(shí)例規(guī)模的增大,樹(shù)分解算法在解的質(zhì)量上要比Rathinam等人的近似算法精度高10%。在文章最后的實(shí)際應(yīng)用中,我們選取了易果生鮮的配送路線作為案例,通過(guò)建立簡(jiǎn)單的數(shù)學(xué)模型來(lái)比較傳統(tǒng)配送方案和樹(shù)分解算法給出的配送路線,發(fā)現(xiàn)樹(shù)分解算法能在物流成本上節(jié)省8%。
[Abstract]:Delaunay triangulation is one of the effective techniques in dealing with solid cluster analysis in space. In this paper, we introduce it and limit the MTSP problem to two dimensional Euclidean plane, combining the idea of minimum spanning tree and double spanning tree, and then get the tree decomposition algorithm. Through the theoretical analysis of the tree decomposition algorithm, it is obtained that the algorithm can generate an approximate solution not more than 2 times of the optimal solution in the input scale O (nlogn) time. In order to analyze the performance of the tree decomposition algorithm in concrete examples, in the numerical simulation part, the comparison between the algorithm and Zhou Xu et al (2-1 / k) algorithm is given. It is concluded that the algorithm of tree decomposition is superior to that of Zhou Xu et al in terms of complexity and quality, and then compared with that of Rathinam et al., which is approximately 2, and by simulating many instances on TSPLIB, it is concluded that with the increase of the scale of the instance, The accuracy of the tree decomposition algorithm is 10% higher than that of Rathinam et al. In the last practical application of the article, we choose the distribution route of Yiguo fresh and fresh as a case, and compare the distribution route given by traditional distribution scheme and tree decomposition algorithm by establishing a simple mathematical model. It is found that the tree decomposition algorithm can save 8% of logistics cost.
【學(xué)位授予單位】：華東理工大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2017
【分類號(hào)】：TP311.13

【參考文獻(xiàn)】

相關(guān)期刊論文 前1條

1 徐永安,楊欽,吳壯志,陳其明,譚建榮;三維約束Delaunay三角化的實(shí)現(xiàn)[J];軟件學(xué)報(bào);2001年01期

，

本文編號(hào)：2374148