基于二维欧式空间的MTSP近似算法
发布时间：2018-12-12 07:03
【摘要】：Delaunay三角剖分作为处理空间中实体聚类分析中的有效技术之一,本文将其引入并将MTSP问题限制在二维欧式平面内结合最小支撑树和双生成树算法思想,从而得到树分解算法。通过对树分解算法的理论分析,得到该算法能在输入规模O(nlogn)时间内生成一个不会超过最优解的2倍的近似解。为了分析树分解算法在具体实例上的表现,在数值模拟部分中,通过多角度的对比,首先是该算法和Zhou Xu等人的(2-1/k)算法的比较,得出树分解算法能在复杂度和解的质量上都优于Zhou Xu等人的算法,接着对比近似比同为2的Rathinam等人的算法,并通过模拟TSPLIB上的多个实例,得出随着实例规模的增大,树分解算法在解的质量上要比Rathinam等人的近似算法精度高10%。在文章最后的实际应用中,我们选取了易果生鲜的配送路线作为案例,通过建立简单的数学模型来比较传统配送方案和树分解算法给出的配送路线,发现树分解算法能在物流成本上节省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.
【学位授予单位】：华东理工大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP311.13
本文编号：2374148
[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.
【学位授予单位】：华东理工大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP311.13
【参考文献】
相关期刊论文 前1条
1 徐永安,杨钦,吴壮志,陈其明,谭建荣;三维约束Delaunay三角化的实现[J];软件学报;2001年01期
，本文编号：2374148
本文链接：https://www.wllwen.com/guanlilunwen/wuliuguanlilunwen/2374148.html
