• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Constraints >Cost-based Filtering for Shorter Path Constraints
【24h】

Cost-based Filtering for Shorter Path Constraints

机译：基于成本的筛选以缩短路径约束

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

摘要

Many real world problems, e.g. personnel scheduling and transportation planning, can be modeled naturally as Constrained Shortest Path Problems (CSPPs), i.e., as Shortest Path Problems with additional constraints. A well studied problem in this class is the Resource Constrained Shortest Path Problem. Reduction techniques are vital ingredients of solvers for the CSPP, that is frequently NP-hard, depending on the nature of the additional constraints. Viewed as heuristics, these techniques have not been studied theoretically with respect to their efficiency, i.e., with respect to the relation of filtering power and running time. Using the concepts of Constraint Programming, we provide a theoretical study of cost-based filtering for shorter path constraints on acyclic, on undirected, and on directed graphs that do not contain negative cycles. We then show empirically how reasoning about path-substructures in combination with CP-based Lagrangian relaxation can help to improve significantly over previously developed problem-tailored filtering algorithms for the resource constrained shortest path problem and investigate the impact of required-edge detection, undirected versus directed filtering, and the choice of the algorithm optimizing the Lagrangian dual.
机译：许多现实世界的问题，例如人员调度和运输计划可以自然地建模为约束最短路径问题（CSPP），即带有附加约束的最短路径问题。在该课程中，一个经过充分研究的问题是资源约束最短路径问题。还原技术是CSPP求解器的重要组成部分，它通常是NP难的，具体取决于附加约束的性质。从启发式的角度来看，这些技术在效率方面，即在滤波能力和运行时间之间的关系上，在理论上尚未得到研究。使用约束规划的概念，我们对基于成本的过滤进行了理论研究，以针对非循环，无向和有向图上的较短路径约束，其中不包含负循环。然后，我们从经验上展示与基于CP的拉格朗日松弛相结合的路径子结构的推理如何可以大大改善先前开发的针对资源受限的最短路径问题的问题量身定制的过滤算法，并研究要求边缘检测（无向与无向）的影响定向滤波，以及优化拉格朗日对偶的算法选择。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号