Research map / Learning theory and algorithms / Combinatorial and search optimization
A Fast Exact Algorithm for the Resource Constrained Shortest Path Problem
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the full RC-EBBA* initialisation and bidirectional search heuristics instead of existing algorithms | RCSPP · 440 benchmark instances | average runtime (s): 10.701 vs 993.609 | Helped |
| Use bounded A* initialisation instead of unidirectional Dijkstra initialisation | RC-EBBA* · Overall benchmark instances | average initialisation time (s): Ours 10.701; Uni-Dij. 993.609 | Helped |
| Use bounded A* initialisation instead of bidirectional Dijkstra initialisation | RC-EBBA* · Overall benchmark instances | average initialisation time (s): Ours 10.701; Bi-Dij. 1496.869 | Helped |
| Update the initial solution during bounded searches | RC-EBBA* initialisation · NY | maximum initial-solution gap (%): 38.69 -> 4.64 | Helped |
| Bias the bidirectional search budget according to node distribution | RC-EBBA* · RCSPP benchmark instances | runtime | Helped |
| Use bucket queues instead of heaps (ablation) | RC-EBBA* · Benchmark instances | average runtime (s): 37 -> 10.7 | Helped |
Closest papers by meaning
- Resource Constrained Pathfinding with Enhanced Bidirectional A* Search (AAAI 2025 · similarity 0.89)
- Efficient Constraint Generation for Stochastic Shortest Path Problems (AAAI 2024 · similarity 0.84)
- Paths, Proofs, and Perfection: Developing a Human-Interpretable Proof System for Constrained Shortest Paths (AAAI 2024 · similarity 0.83)
- Exact Algorithms and Lowerbounds for Multiagent Path Finding: Power of Treelike Topology (AAAI 2024 · similarity 0.83)
- Solving Multiagent Path Finding on Highly Centralized Networks (AAAI 2025 · similarity 0.82)
- Exact Algorithms for Multiagent Path Finding with Communication Constraints on Tree-Like Structures (AAAI 2025 · similarity 0.82)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.