The Resource Constrained Shortest Path Problem (RCSPP) seeks to determine a minimum-cost path between a start and a goal location while ensuring that one or multiple types of resource consumed along the path do not exceed their limits. This problem is often solved on a graph where a path is incrementally built from the start towards the goal during the search. RCSPP is computationally challenging as comparing these partial solution paths is based on multiple criteria (i.e., the accumulated cost and resource along the path), and in general, there does not exist a single path that optimizes all criteria simultaneously. Consequently, the search needs to maintain and explore a large number of partial paths in order to find an optimal solution. While a variety of algorithms have been developed to solve RCSPP, they either have little consideration about efficiently comparing and maintaining the partial paths, which reduces their overall runtime efficiency, or are restricted to handle only one resource constraint as opposed to multiple resource constraints. This paper develops Enhanced Resource Constrained A* (ERCA*), a fast A*-based algorithm that can find an optimal solution while satisfying multiple resource constraints. ERCA* leverages both the recent advances in multi-objective path planning to efficiently compare and maintain partial paths, and techniques from the existing RCSPP literature. Furthermore, ERCA* has a functional parameter to broker a trade-off between solution quality and runtime efficiency. The results show ERCA* often runs several orders of magnitude faster than an existing leading algorithm for RCSPP.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    ERCA*: A New Approach for the Resource Constrained Shortest Path Problem



    Published in:

    Publication date :

    2023-12-01


    Size :

    7751359 byte




    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English



    The Variance-Constrained Shortest Path Problem

    Sivakumar, Raj A. | Online Contents | 1994


    A Reference Point Approach for the Resource Constrained Shortest Path Problems

    Di Puglia Pugliese, L. / Guerriero, F. | British Library Online Contents | 2013



    Resource Constrained Shortest Path Problems in Path Planning for Fleet Management

    Avella, P. / Boccia, M. / Sforza, A. | British Library Online Contents | 2004


    Enhanced bi-directional dynamic programming algorithm for the resource constrained shortest path problem

    Salani, Matteo / Basso, Saverio / Righini, Giovanni | Elsevier | 2024

    Free access