首页> 外文期刊>Networks >An exact bidirectional A~* approach for solving resource-constrained shortest path problems
【24h】

An exact bidirectional A~* approach for solving resource-constrained shortest path problems

机译:解决资源受限的最短路径问题的精确双向A〜*方法

获取原文
获取原文并翻译 | 示例
获取外文期刊封面目录资料

摘要

Bidirectional dynamic programming is an algorithm that searches for paths in a network from both the starting and the ending nodes that optimize a given objective function. In recent years, bidirectional dynamic programming has been shown to be an effective means for solving resource-bounded shortest path problems. While many researchers have observed that bidirectional A(⋆) approaches perform poor computationally, we exploit the presence of resource constraints to overcome the source of these computational challenges. Our main contribution in this paper is an exact bidirectional A(⋆) algorithm for resource-constrained shortest path problems (RCSPPs) that is capable of solving large-sized instances that challenge the state-of-the-art in the literature. We also analyze, both computationally and theoretically, the sensitivity of the algorithm's performance to its inputs.
机译:双向动态规划是一种算法,可从起始节点和终止节点搜索网络中的路径,以优化给定的目标函数。近年来,双向动态规划已被证明是解决资源有限的最短路径问题的有效手段。尽管许多研究人员已经观察到双向A(⋆)方法在计算方面表现不佳,但我们利用资源约束的存在来克服这些计算挑战的根源。本文的主要贡献是针对资源受限的最短路径问题(RCSPP)的精确双向A(⋆)算法,该算法能够解决挑战文献中最新技术的大型实例。我们还在计算和理论上分析了算法性能对其输入的敏感性。

著录项

相似文献

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

客服邮箱:kefu@zhangqiaokeyan.com

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

  • 服务号