...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>European Journal of Operational Research >On estimating the distribution of optimal traveling salesman tour lengths using heuristics
【24h】

On estimating the distribution of optimal traveling salesman tour lengths using heuristics

机译：使用启发式估计最佳旅行推销员巡回行程的分布

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

The traveling salesman problem is an important combinatorial optimization problem due to its significance in academic research and its real world applications. The problem has been extensively studied and much is known about its polyhedral structure and algorithms for exact and heuristic solutions. While most work is concentrated on solving the deterministic version of the problem, there also has been some research on the stochastic TSP. Research on the stochastic TSP has concentrated on asymptotic properties and estimation of the TSP-constant. Not much is, however, known about the probability distribution of the optimal tour length. In this paper, we present some empirical results based on Monte Carlo simulations for the symmetric Euclidean and Rectilinear TSPs. We derive regression equations for predicting the first four moments of the distribution of estimated TSP tour lengths using heuristics. We then show that a Beta distribution gives excellent fits for small to moderate sized TSP problems. We derive regression equations for predicting the parameters of the Beta distribution. Finally we predict the TSP constant using two alternative approaches. (c) 2007 Published by Elsevier B.V.
机译：由于其在学术研究和其实际应用中的重要性，因此旅行商问题是一个重要的组合优化问题。已经对该问题进行了广泛研究，关于其多面体结构和用于精确和启发式解决方案的算法已广为人知。虽然大多数工作都集中在解决问题的确定性版本上，但也对随机TSP进行了一些研究。关于随机TSP的研究集中于渐近性质和TSP常数的估计。然而，关于最佳行程长度的概率分布知之甚少。在本文中，我们基于蒙特卡罗模拟给出了对称欧几里得和直线型TSP的一些经验结果。我们使用启发式方法得出回归方程，用于预测TSP行程估计长度分布的前四个时刻。然后，我们证明Beta分布可以很好地解决中小型TSP问题。我们导出回归方程，以预测Beta分布的参数。最后，我们使用两种替代方法来预测TSP常数。 （c）2007年由Elsevier B.V.

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号