改进A*算法，高效求解含负权资源的大规模路径规划问题。
Resource Constrained Pathfinding with A* and Negative Weights
- 基于A*构建新框架，支持负代价与负资源约束。
- 在大规模网络上实测，速度比现有方法快100倍。
- 适合需要多资源限制的复杂路径规划场景。
受限路径规划是广泛存在于现实应用中的经典网络优化难题。多资源约束路径问题（Resource Constrained Shortest Path Problem, RCSP）旨在满足资源使用上限的前提下，寻找成本最优的路径。尽管近年来在带约束和多目标搜索方面基于A*的方法取得进展，本文提出一种新的基于A*的资源受限搜索框架，可在存在负代价和负资源的情况下，高效求解大规模网络中的RCSP。我们在一系列大规模实例上进行了实验评估，结果表明，该算法相比文献中现有最先进方法，性能提升高达两个数量级。
原文摘要 · Abstract (English)
Constrained pathfinding is a well-studied, yet challenging network optimisation problem that can be seen in a broad range of real-world applications. Pathfinding with multiple resource limits, which is known as the Resource Constrained Shortest Path Problem (RCSP), aims to plan a cost-optimum path subject to limited usage of resources. Given the recent advances in constrained and multi-criteria search with A*, this paper introduces a new resource constrained search framework on the basis of A* to tackle RCSP in large networks, even in the presence of negative cost and negative resources. We empirically evaluate our new algorithm on a set of large instances and show up to two orders of magnitude faster performance compared to state-of-the-art RCSP algorithms in the literature.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。