用嵌套插队算法解决旅行推销员问题(英文)

提出了一种求解 TSP问题的近似算法—嵌套插队算法。这种算法结合了启发式算法和随机化算法以及局部寻优的思想。实验结果表明对于较小规模的 TSP问题 ,直接用插队算法 ( QJA)就能以很大的概率获得已知最优解。对于规模较大的 TSP问题 ,嵌套插队算法 ( NQJA)能获得质量高于著名的启发式算法的解。另外 ,用嵌套插队算法找到的 China144的最短路径优于目前已知的最短路径。嵌套插队算法是专门针对 TSP问题而提出的 ,但其思想也可以给求解其他

用嵌套插队算法解决TSP问题

本文提出了一种求解TSP问题的近似算法—嵌套插队算法。这种算法结合了启发式算法和随机化算法以及局部寻优的思想。实验结果表明对于较小规模的TSP问题,直接用插队算法(QJA)就能以很大的概率获得已知最优解。对于规模较大的问题实例,嵌套插队算法(NQJA)能获得质量高于著名的启发式算法的解。另外,用嵌套插队算法找到的China144的最短路径优于目前已知的最短路径。嵌套插队算法是专门针对TSP问题而提出的,但其思想也可以给求解其他NP难解的组合优化问题以启发。

求解TSP的插队算法中初始回路的选择

插队算法是求解旅行商问题(TSP)的一种较好的近似算法。插队算法中初始回路的选择对算法的性能具有至关重要的影响。文章在考虑了城市分布特点的基础上,选用能大致模拟密集城市分布的三角形作为初始回路,以包罗同一方向上更多的城市,然后按照子回路增加路径最短规则依次将其余城市加入到路径中,形成旅行商问题较优的近似解。与其他启发式算法比较,该方法不需迭代,且解的质量更好。TSP测试文件berlin52.tsp仿真结果证明了该方法的优越性。

基于梯森分割的城市物流配送路线优化选择

物流配送车辆路径优化问题是一个典型的NP难题,也是近年来物流研究中的一个热点。文章利用先分组再排路线的思想,把城市零售商品物流配送车辆路径优化问题分解成一个分派问题和一个类似旅行商问题(TravelingSalesm an Problem,TSP)。应用空间分析中的梯森分割(Thiessen Tessellation)理论解决分派问题,同时改进用于求解TSP问题的插队算法,将其应用于对车辆巡回路线寻优问题的求解,最后,对此算法进行了应用举例。

Voronoi分割模式下连锁企业物流配送系统的设计与实现

综合考虑城市连锁企业物流配送的特点和Voronoi多边形的几何特性,提出Voronoi分割模式下连锁商店市场域划分的计算几何的方法,从而实现连锁商店配送区域的自动划分,以此为基础,对传统的运输巡回路线算法进行了优化,并将二者集成到城市连锁企业物流配送系统中。阐述了该系统的组织框架,并以福建省福州市为研究背景,以福州市著名仓储式连锁企业(某超市)为研究对象,列举了该系统的应用。结果表明,该系统对连锁企业的经营决策有较大的应用价值。