• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>IEEE Global Communications Conference >A fast Lagrangian relaxation algorithm for finding multi-constrained multiple shortest paths
【24h】

A fast Lagrangian relaxation algorithm for finding multi-constrained multiple shortest paths

机译：快速拉格朗日松弛算法，用于找到多约束的多个最短路径

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Finding a multi-constrained shortest path (MCSP) between a pair of nodes arises in many important applications such as quality of service provisioning in the next-generation network. While this problem subject to a single constraint has been well studied, efficient algorithms solving this problem with two or more constraints are still quite limited. In this paper, we propose a new Lagrangian relaxation algorithm for solving a generalized version of the MCSP problem, where we search for multiple shortest paths subject to multiple constraints. As in some related work, our algorithm first identifies the lower and upper bounds, and then tries to close the gap with a path enumeration procedure. However, our algorithm is based on the recognition that the Lagrange multipliers found by existing methods usually do not give the best search direction for minimizing path enumerations even though they can provide near-optimized lower bounds. We provide a solution to meet both of these goals. Through experiments on the most challenging benchmark instances, we show that our algorithm performs significantly better than the best known algorithm in the literature.
机译：在一对节点之间找到多约束的最短路径（MCSP），在许多重要的应用程序中出现，例如下一代网络中的服务质量提供。虽然这一问题受到单一约束的研究已经很好地研究，但是解决了两个或更多限制的解决这个问题的有效算法仍然非常有限。在本文中，我们提出了一种新的拉格朗日放松算法，用于解决MCSP问题的广义版本，在那里我们搜索多个约束的多个最短路径。与某些相关的工作一样，我们的算法首先识别下限和上限，然后尝试用路径枚举过程关闭间隙。然而，我们的算法基于识别现有方法发现的拉格朗日乘法器通常不会给出最佳搜索方向，以便最小化路径枚举，即使它们可以提供近优化的下限。我们提供解决这些目标的解决方案。通过对最具挑战性的基准实例的实验，我们表明我们的算法显着优于文献中的最佳已知算法。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号