...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Computers, IEEE Transactions on >Finding Multi-Constrained Multiple Shortest Paths
【24h】

Finding Multi-Constrained Multiple Shortest Paths

机译：查找多约束的多个最短路径

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

摘要

Numerous algorithms have been proposed for the well-known multi-constrained shortest path (MCSP) problem, but very few have good practical performance in case of two or more constraints. In this paper, we propose a new Lagrangian relaxation algorithm to solve a generalized version of the MCSP problem where we search for 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, and incorporate feasibility checks into a state-of-the-art K-shortest paths algorithm to further reduce path enumerations. Through experiments on various networks including the most challenging benchmark instances, we show that our algorithm can solve a significantly larger number of instances to optimality with less computational cost, often by one or two orders of magnitude, when compared with the best known algorithm in the literature.
机译：已经针对众所周知的多约束最短路径（MCSP）问题提出了许多算法，但是在两个或更多约束的情况下，只有极少数具有良好的实用性能。在本文中，我们提出了一种新的拉格朗日松弛算法来解决MCSP问题的广义版本，在该版本中，我们搜索受多个约束约束的最短路径。像在一些相关的工作中一样，我们的算法首先确定上下限，然后尝试使用路径枚举过程来缩小差距。但是，我们的算法基于以下认识：现有方法发现的拉格朗日乘子通常无法提供最佳的搜索方向来最小化路径枚举，即使它们可以提供近乎优化的下限。我们提供了满足这两个目标的解决方案，并将可行性检查合并到最新的K最短路径算法中，以进一步减少路径枚举。通过在包括最具挑战性的基准实例在内的各种网络上进行的实验，我们表明，与算法中最知名的算法相比，我们的算法可以用更少的计算成本将大量实例求解为最优，而计算成本通常降低一到两个数量级。文献。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号