A Fast and Simple Algorithm for the Resource Constrained Shortest Path Problem

This paper presents a novel and straightforward label-setting framework built upon A*, called NWRCA*, which incorporates effective search and lazy pruning strategies to accelerate constrained pathfinding in large-scale networks with negative costs and resources. We evaluate the framework in two variants that differ slightly in how they maintain search labels, and we investigate a faster method for computing A*’s heuristics that can potentially replace the conventional reweighting approach when dealing with negative-weight graphs. Extensive experiments demonstrate the success of the framework in solving difficult RCSP instances several orders of magnitude faster than ERCA* and RCBDA*.

Many real-world RCSP problems deal with attributes that are negative in nature, such as energy recuperation in electric vehicles, or attributes that may exhibit negative values in specific circumstances, such as negative reduced costs in column generation or pricing problems [19]. Although recent A*-based RCSP solutions, such as ERCA* and RCBDA*, are primarily designed and evaluated for problem instances with non-negative edge attributes, they can be adapted to be used for instances with negative weights (but no negative cycles). This can be achieved through a graph reformulation phase, where all edge weights are shifted to non-negative values, for example, using Johnson’s reweighting technique [21]. However, as we will show in this section, our constrained search framework can be applied directly to graphs with negative edge weights, provided that its $\mathrm{𝑐𝑜𝑠𝑡}$ heuristic is consistent. With this introduction, we now describe our new RCSP algorithm.

Algorithm 1 presents the pseudocode of NWRCA*, our A*-based RCSP method that employs lazy dominance checks and can handle problem instances with negative edge weights (but no negative cycles). The algorithm begins by initializing a priority queue $𝒬$ and a global cost upper bound $\overline{f}$, which maintains the best-known cost of any feasible solution found during the search. For each vertex $v\in V$, it also initializes a list $𝒳(v)$ to store the non-dominated labels resulting from all prior expansions (i.e., closed labels) associated with vertex $v$. Like other A*-based RCSP algorithms, NWRCA* requires a $\mathrm{𝑐𝑜𝑠𝑡}$ heuristic function $h_c$ to establish $f$-values. To enhance pruning of unpromising paths, we also compute lower bounds on $\mathrm{𝐫𝐞𝐬𝐨𝐮𝐫𝐜𝐞𝐬}$ using an admissible heuristic function ${𝐡}_r:V\to {ℝ}^d$. These cost and resource heuristics can be computed using $1+d$ single-objective Dijkstra runs [11], with re-expansions allowed to accommodate negative weights [20], assuming there are no negative cycles on any path from $v_s$ to $v_g$ in any dimension (cost or resources). A similar strategy has been explored in [1] for multi-objective search. As we will demonstrate in the experimental section, this heuristic construction method, despite its exponential worst-case complexity, often outperforms alternatives such as Johnson’s reweighting technique [21] in practice. NWRCA* then initializes a label with $v_s$ and inserts it into $𝒬$. Each iteration of the main search starts at line 8. Let $𝒬$ be a non-empty queue. The algorithm extracts in each iteration a label $l$ with the smallest $f$-value (line 9) and attempts the following steps.

NWRCA* borrows a lazy label pruning technique from the multi-objective search literature and delays dominance check of newly generated labels until they are extracted from $𝒬$, as in [18] and [1]. Let $l$ be a label extracted from $𝒬$ with $f$-value within the global upper bound. Also let $v$ be the end vertex associated with $l$. Because the first dimension is always explored in sorted $f$ order (guaranteed in A* with a consistent heuristic), we observe that $l$ is already weakly dominated by previous expansions in terms of $\mathrm{𝑐𝑜𝑠𝑡}$. Note that all expansions with $v$ use $h_c(v)$ as lower bound. As a result, all prior expansions of $v$ must have exhibited $g$-value no smaller than $g_l$. This means that the dominance test can only be done by comparing the resource vector of $l$, that is, ${𝐫}_l$, with that of (potentially all) previous expansions stored in $𝒳(v)$. This process can be further improved by prioritizing the most recent expansion of $v$ as the first (potentially more informed) candidate for a quick dominance check, prior to a more rigorous dominance check against the labels of $𝒳(v)$ [1]. The expansion of label $l$ can be skipped if it is found to be dominated by any previously expanded label (lines 13-16). If $l$ is determined to be non-dominated, NWRCA* removes from the $𝒳(v)$ list any label $l^{\prime }$ whose resource vector is weakly dominated by ${𝐫}_l$ (lines 18-19), and then adds $l$ to $𝒳(v)$ for future dominance checks at vertex $v$ (line 20). This removal is correct because any future label that would be dominated by $l^{\prime }$ will also be dominated by $l$, making it unnecessary to keep the now-redundant label in $𝒳(v)$.

A tentative solution path is found if the search extracts a non-dominated label associated with the goal vertex $v_g$ (line 21). Expansion of solution labels is not necessary. However, in the absence of tie-breaking in $𝒬$, new solutions may offer better resources than previous ones. NWRCA* takes care of this situation by maintaining only non-dominated labels associated with the goal vertex in $𝒳(v_g)$.

$l$’s expansion involves generating new descendant labels through $v$’s successors (adjacent vertices). Given ${𝐡}_r$ as an admissible heuristic function, descendant labels with estimated resource usage exceeding the given limit $𝐑$ cannot lead to a feasible solution and can be pruned (line 30). Note that in the case of negative resources, new labels whose usage of $\mathrm{𝐫𝐞𝐬𝐨𝐮𝐫𝐜𝐞𝐬}$ exceeds the budget (i.e., ${𝐫}_{l^{\prime }}⋠𝐑$) can be pruned, provided that all partial paths are also required to satisfy the resource constraints (which is not assumed in this work). As part of NWRCA*’s lazy dominance pruning rule, newly generated labels are not checked for dominance against previously expanded labels or those still in $𝒬$; instead, they are only checked when extracted from the queue. Thus, each descendant label will be added to $𝒬$ if its estimated usage of $\mathrm{𝐫𝐞𝐬𝐨𝐮𝐫𝐜𝐞𝐬}$ to $v_g$ is within $𝐑$.

NWRCA* explores labels based on their $f$-value in ascending order. Given $\overline{f}$ as global $\mathrm{𝑐𝑜𝑠𝑡}$ upper bound, the search can terminate safely once it extracts a label with $f$-value greater than $\overline{f}$ (line 10). Although this upper bound is initially unknown, it will get updated as soon as a feasible solution is discovered (line 22). The algorithm returns $𝒳(v_g)$, a set containing $\mathrm{𝑐𝑜𝑠𝑡}$-optimal labels with non-dominated $\mathrm{𝐫𝐞𝐬𝐨𝐮𝐫𝐜𝐞𝐬}$ (line 32). If there is no solution to a given instance (i.e., $v_g$ is never reached), this set would remain empty.

We further elaborate on the key steps of NWRCA* by solving a sample RCSP instance with three edge attributes (two resources), depicted in Figure 1. We assume resource limits are $(R_1,R_2)=(3,3)$. The vertices $v_s$ and $v_g$ denote $\mathrm{𝑠𝑡𝑎𝑟𝑡}$ and $\mathrm{𝑔𝑜𝑎𝑙}$, respectively. The graph is free of negative cycles, and the values inside each vertex denote $h_c$ and $(h_{r1},h_{r2})$, calculated prior to the main search via three single-objective backward searches. We briefly explain all iterations (It.) of NWRCA* for the given instance, with the trace of $𝒬$ and $𝒳$ sets provided in Table 1. Pruned labels of each iteration are shown in the third column. For label extractions, we adopt the Last-In, First-Out (LIFO) strategy in the event of ties in $f$-values of labels present in $𝒬$. The queue is initialized with the first label $l_1$ associated with $v_s$.

• $\mathrm{■}$

  It.1: The search starts with expanding the initial label $l_1$. Since $l_1$ is the first expansion of $v_s$ and thus non-dominated, it is stored in $𝒳(v_s)$. Expansion of $l_1$ generates three new labels: $l_2$, $l_3$, and $l_4$. $l_2$ and $l_4$ are added to $𝒬$ but $l_3$ is pruned as its resource estimates are out of bounds, i.e., we have ${𝐫}_{l_3}+{𝐡}_r(v_2)⋠𝐑$.

• $\mathrm{■}$

  It.2: There are two labels in $𝒬$. $l_2$ has the smallest $f$-value and is expanded first. $l_2$ is non-dominated and its expansion generates $l_5$ and $l_6$ with $v_2$ and $v_4$, respectively. Both labels are pruned since their resource estimates are out of bounds.

• $\mathrm{■}$

  It.3: $l_4$, associated with $v_3$, is the only label in $𝒬$ and is extracted. $l_4$ will be stored in $𝒳(v_3)$ as a non-dominated label. $l_4$’s expansion generates three new labels: $l_7$, $l_8$, and $l_9$. However, only two of these are within the resource bounds and can be added to $𝒬$. $l_9$ is out of bounds as we have $3+1\nleqq 3$ for its second resource estimate.

• $\mathrm{■}$

  It.4: There are two labels in $𝒬$, both with the same $f$-value. $l_8$ is extracted based on the LIFO strategy. $l_8$ is non-dominated, as this is the first expansion with $v_4$. Expansion of $l_8$ generates two new labels ($l_{10}$ and $l_{11}$, both within the bounds) and adds them to $𝒬$.

• $\mathrm{■}$

  It.5: $l_{11}$ is extracted based on the LIFO strategy. $l_{11}$ is non-dominated and its expansion generates two labels $l_{12}$ and $l_{13}$, but only $l_{12}$ is added into $𝒬$ as the second resource estimate for $l_{13}$ is not within the bound, i.e., we have $3+1\nleqq 3$.

• $\mathrm{■}$

  It.6: There are three labels in $𝒬$, all with the same $f$-value. The recent insertion $l_{12}$ is extracted with $v_g$. This yields the first solution path, followed by updating $\overline{f}\leftarrow 3$. $l_{12}$ does not get expanded.

• $\mathrm{■}$

  It.7: $l_{10}$ is extracted, and it appears as a non-dominated solution. However, $l_{10}$’s resource vector $(0,3)$ dominates that of the previous solution. Thus, $l_{10}$ replaces $l_{12}$ in $𝒳(v_g)$.

• $\mathrm{■}$

  It.8: $l_7$ is extracted. $l_7$ is a non-dominated label but dominates and replaces $l_{11}$ in $𝒳(v_5)$. Expansion of $l_7$ generates two new labels ($l_{14}$ and $l_{15}$). Both labels are within the resource bounds and thus added into $𝒬$.

• $\mathrm{■}$

  It.9: $l_{14}$ is extracted with $v_g$. $l_{14}$ is non-dominated and is added to $𝒳(v_g)$. $l_{14}$ does not dominate the previous solution.

• $\mathrm{■}$

  It.10: $l_{15}$ is extracted. Given the $\mathrm{𝑐𝑜𝑠𝑡}$ upper bound updated in It.6, the search terminates due to $f_{l_{15}}$ surpassing the upper bound $\overline{f}$, i.e., we have $f_{l_{15}}=4>3$.

The example above shows how NWRCA* processes labels in the order of their $f$-value. As we observed in It.6, NWRCA* may capture a dominated solution in the absence of tie-breaking, but we discussed in It.7 how the search refines the set $𝒳(v_g)$ in such circumstances to keep $\mathrm{𝐫𝐞𝐬𝐨𝐮𝐫𝐜𝐞𝐬}$ of solution paths non-dominated. We now briefly discuss the key differences of NWRCA* with two recent RCSP approaches, namely ERCA* and RCBDA*.

Although both algorithms utilize best-first search to guide their constrained search, they differ in four key aspects regarding how labels are handled: (1) ERCA* checks labels for both dominance and resource usage once during expansion and again before expansion, whereas NWRCA* performs upper bound pruning only during expansion and dominance check only before expansion; (2) ERCA* explores labels in lexicographical order of their $\mathrm{𝐫𝐞𝐬𝐨𝐮𝐫𝐜𝐞𝐬}$ in case of ties between $f$-values in the queue (i.e., it compares labels based on resources in order, starting from the first resource), whereas NWRCA* does not perform tie-breaking; (3) ERCA* uses a specialized and relatively complex data structure (balanced binary search tree) to organize and dominance check labels during the search, whereas expanded labels in NWRCA* are stored in simple lists; (4) ERCA* immediately terminates upon finding a feasible solution, whereas NWRCA* terminates with all non-dominated solutions.

The algorithms differ in four key aspects: (1) RCBDA* conducts a bidirectional A* search, requiring a specialized and time-intensive procedure to handle frontier collisions (joining bidirectional labels), whereas NWRCA* performs a simple unidirectional search. (2) RCBDA* checks new labels for dominance against all previous expansions of the vertex, whereas NWRCA* only checks against labels with non-dominated $\mathrm{𝐫𝐞𝐬𝐨𝐮𝐫𝐜𝐞𝐬}$; (3) RCBDA* checks labels for dominance only during expansion, which can lead to the expansion of dominated labels, whereas NWRCA* performs dominance checks before expansion; (4) Similar to ERCA*, RCBDA* does not compute all non-dominated solutions.

We distinguish two cases: i) if $l_{i+1}$ was available in $𝒬$ at the time $l_i$ was extracted, the lemma is trivially true. ii) otherwise, $l_{i+1}$ is the descendant label of $l_i$. For an edge $(v,u)$ linking $l_i$ to its descendant $l_{i+1}$, $h_c$’s consistency ensures $h_c(v)\le h_c(u)+\mathrm{𝑐𝑜𝑠𝑡}(v,u)$. Adding the cost $g_{l_i}$ to both sides of the inequality yields $f_{l_i}\le f_{l_{i+1}}$. $◀$

Since $l$ is extracted before $l^{\prime }$, we have $f_l\le f_{l^{\prime }}$ according to Corollary 4, and consequently $g_l\le g_{l^{\prime }}$. The other condition ${𝐫}_l⪯{𝐫}_{l^{\prime }}$ means that $l^{\prime }$ is no smaller than $l$ in all resources, verifying $l^{\prime }$ is weakly dominated by $l$. $◀$

We prove this by contradiction, assuming that $l$’s expansion is necessary to obtain a $\mathrm{𝑐𝑜𝑠𝑡}$-optimal and non-dominated solution path. As $l$ weakly dominates $l^{\prime }$, it holds that $g_l\le g_{l^{\prime }}$ and ${𝐫}_l⪯{𝐫}_{l^{\prime }}$. In this scenario, the partial path represented by $l^{\prime }$ can be replaced with the one represented by $l$, resulting in a path that is better than or equal to the optimal solution path obtained via $l^{\prime }$. If the resulting path is better, it contradicts the assumption of $l^{\prime }$’s expansion leading to a non-dominated or optimal solution. If both paths are identical in terms of $\mathrm{𝑐𝑜𝑠𝑡}$ and $\mathrm{𝐫𝐞𝐬𝐨𝐮𝐫𝐜𝐞𝐬}$, it becomes clear that the expansion of $l$ has been sufficient, and thus expanding $l^{\prime }$ is unnecessary, again contradicting the assumption. Therefore, we conclude that expanding the weakly dominated label $l^{\prime }$ is not necessary. $◀$

Given that ${𝐡}_r$ is admissible, the second condition ensures that expanding $l$ towards $v_g$ cannot yield a solution within the resource limits. Similarly, since $h_c$ is admissible, the first condition guarantees that $l$’s expansion cannot produce a solution with a $\mathrm{𝑐𝑜𝑠𝑡}$ better than the best-known upper bound $\overline{f}$. Therefore, expanding $l$ cannot contribute to any optimal solution path, and thus is not necessary. $◀$

The algorithm explores all feasible search labels from $v_s$ towards $v_g$ in best-first order, in search of all optimal solutions. Labels are checked for dominance (Lemma 5) before expansion, and weakly dominated ones can be safely pruned, as they offer no improvement over previously expanded labels (with the same vertex) in either $\mathrm{𝑐𝑜𝑠𝑡}$ or $\mathrm{𝐫𝐞𝐬𝐨𝐮𝐫𝐜𝐞𝐬}$ (Lemma 6). Labels violating the upper bounds can similarly be pruned safely (Lemma 7). The algorithm also retains only non-dominated labels in the $𝒳$ lists. This procedure is correct because if a recently extracted label $l^{\prime }$ weakly dominates a previously explored label $l$, then any future label $l^{\prime \prime }$ that would have been weakly dominated by $l$ is already weakly dominated by $l^{\prime }$, rendering the storage of $l$ redundant. Building on the above, we just need to show that the algorithm terminates with returning non-dominated labels. NWRCA* prunes all weakly dominated labels, but captures all non-dominated labels with $v_g$. However, since it does not process labels in any specific order of their $\mathrm{𝐫𝐞𝐬𝐨𝐮𝐫𝐜𝐞𝐬}$, some tentative solutions may later appear dominated. Let $l^{\prime }$ be a new non-dominated solution extracted after solution $l$. We must have $f_l=f_{l^{\prime }}$, otherwise the algorithm was terminated if $f_{l^{\prime }}>\overline{f}=f_l$. In this case, the dominance check in lines 18-19 of Algorithm 1 removes $l$ from $𝒳(v_g)$ if it is deemed to be weakly dominated by new solution $l^{\prime }$ (in terms of $\mathrm{𝐫𝐞𝐬𝐨𝐮𝐫𝐜𝐞𝐬}$). Once the search exceeds $\overline{f}$, Corollary 4 ensures that expanding the remaining labels in $𝒬$ cannot produce solutions with a primary cost better than $\overline{f}$. Thus, the termination criterion is correct, and NWRCA* returns $𝒳(v_g)$ as the set of all $\mathrm{𝑐𝑜𝑠𝑡}$-optimal, non-dominated solution labels. $◀$

We used the publicly available C++ implementations of ERCA* and developed an improved version of RCBDA* in C++ based on its provided description. In doing so, we addressed a potential inefficiency in the design related to the label matching strategy of RCBDA*: rather than storing all expanded labels in a large pool and searching for complimentary labels (which adds unnecessary overhead in identifying the same matching vertex), we allocated a separate set for each vertex, optimizing the matching of partial paths during the bidirectional search. Additionally, the original description of RCBDA* does not include any dominance or infeasibility pruning rules. Nonetheless, our implementation incorporates these strategies, thereby improving its search efficiency. Both RCBDA* and ERCA* were provided with reweighted graphs (and budgets), ensuring that instances can be handled correctly in the presence of negative weights. We implemented our NWRCA* algorithm in C++, providing two variants that differ slightly in their label ordering mechanisms:

• $\mathrm{■}$

  NWRCA*_v1: (i) labels in $𝒳$ lists are maintained in lexicographical order based on their $𝐫$-value, (ii) unexplored labels are ordered in a bucket-based queue and extracted using a LIFO strategy in the event of ties in their $f$-values (as in WCA* [6]).

• $\mathrm{■}$

  NWRCA*_v2: (i) labels in $𝒳$ lists are not maintained in any specific order, (ii) unexplored labels are ordered in a binary heap queue and extracted in lexicographical order of their resource estimates (i.e., $𝐫+{𝐡}_r$) in the event of ties in their $f$-values.

These variants allow us to investigate the impact of lexicographical label ordering in both $𝒳$ and $𝒬$ lists on search performance. Note that the correctness of NWRCA* does not depend on labels being ordered lexicographically by $\mathrm{𝑐𝑜𝑠𝑡}$ and $\mathrm{𝐫𝐞𝐬𝐨𝐮𝐫𝐜𝐞𝐬}$ in $𝒬$. Keeping non-dominated labels in lexicographical order within each $𝒳$ list in the first variant allows for partial traversal over labels of the list for both dominance checking and removal of dominated labels, but it incurs an additional sorting overhead (see [1] for more details). In contrast, the second variant provides faster insertion/removal of labels to/from the list (with minimal ordering overhead), but requires two linear scans over all labels in $𝒳$, one to ensure that a newly extracted label is non-dominated and another to remove any dominated labels from the list.

We compiled all C++ code using the GCC7.5 compiler and optimization level O3. The experiments were conducted on a single core of an Intel Xeon Platinum 8175 processor, clocked at 2.5GHz, with 16GB of RAM and a one-hour time limit per run. It is worth mentioning that RCBDA* and both variants of NWRCA* were implemented within the same framework, using the same data structures to manage labels. Therefore, the performance comparisons between the algorithms are head-to-head. Our code is publicly available³³3https://bitbucket.org/s-ahmadi/multiobj.

Our first analysis explores two approaches for computing heuristic functions for instances with three resources: (i) graph reformulation using Johnson’s technique (as in ERCA*), and (ii) a modified version of Dijkstra’s algorithm that allows for re-expansions. For the first approach, we used the improved Bellman-Ford algorithm [23, 8, 14] to reweight edge costs, followed by Dijkstra’s to compute lower bounds. In case of RCBDA*, two rounds of lower-bound computation are required (one for the forward search and another for the backward search). Table 2 compares the average computation time for both approaches, assuming unidirectional heuristics are needed (as in ERCA* and NWRCA*). We observe that, the approach (i) requires a considerable amount of time to preprocess the graphs but enables faster computation of lower bounds, whereas the second approach, using modified Dijkstra’s algorithm, delivers 3.5 to 4 times faster overall processing time without the need for reweighting in our (sparse) road networks. While approach (ii) can be advantageous in scenarios where the graph configuration changes between queries, it may be up to twice as slow compared to approach (i) when the search graph is static and already reweighted, though the difference is less than 0.5 seconds. Nonetheless, computing heuristic functions for NWRCA* using approach (ii) offers several benefits: i) it provides a simple yet efficient setup for constrained A* search with negative weights; ii) it eliminates the need for a time-intensive graph reformulation step, which is advantageous in dynamic scenarios; iii) it performs comparably to conventional methods when weights are non-negative (would be equivalent to standard Dijkstra).

Table 3 presents the experimental results for both scenarios ($d=2,3$). It displays the number of test cases successfully solved ($|𝒫|$), the arithmetic and geometric mean (Mean_A and Mean_G) and maximum constrained runtime observed (in seconds) by each algorithm. To enable a fair comparison of actual search performance across algorithms, and since all algorithms use same heuristic functions, we exclude preprocessing times (graph reformulation and lower bounding) from our runtime analyses. Therefore, the runtimes reported in this table refer solely to resource-constrained search time. All algorithms solved their easiest instances in less than 0.1 seconds. For unsolved cases, the search time is recorded as the timeout. It can be observed that both variants of NWRCA* have successfully solved almost all instances for each map in both scenarios, except for the BAY map where NWRCA*_v2 leaves four instances unsolved. The outperformance is even more pronounced in the BAY and COL maps with $d=3$, where ERCA* and RCBDA* could solve less than 75% of cases. In terms of computation time, both variants of NWRCA* deliver significantly better performance than ERCA* and RCBDA* in all metrics. The detailed results reveal that NWRCA*_v1 consistently outperforms other algorithms, including NWRCA*_v2, across nearly all instances, successfully solving its most challenging case in under 31 minutes.

The parameter $\varphi$ in the last column of Table 3 presents the (arithmetic) average slowdown factor for each algorithm relative to the top-performing algorithm, NWRCA*_v1. This factor is calculated by comparing the search time of each mutually solved instance with the corresponding search time of NWRCA*_v1, highlighting the relative slowdown. We also show in Figure 2 (Left) the runtime distribution of NWRCA*_v1 against other algorithms over instances of all maps with three resources ($d=3$). Based on the results, NWRCA*_v2 performs nearly 2.5 times slower than NWRCA*_v1. This difference in performance is primarily due to NWRCA*_v2’s costly queuing process, which requires lexicographical ordering of labels in $𝒬$ (tie-breaking with $\mathrm{𝐫𝐞𝐬𝐨𝐮𝐫𝐜𝐞𝐬}$), and NWRCA*_v1’s more efficient label pruning mechanism. This improved pruning efficiency, in particular, stems from the partial traversal of the $𝒳$ lists, where non-dominated labels are maintained in lexicographical order of their $\mathrm{𝐫𝐞𝐬𝐨𝐮𝐫𝐜𝐞𝐬}$.

Larger slowdown factors are observed for ERCA* and RCBDA*, with both algorithms being outperformed by up to two orders of magnitude on average. The more than one order of magnitude performance gap between ERCA* and NWRCA* is primarily due to NWRCA*’s more efficient lazy pruning strategy and its simpler yet effective data structure for dominance checks, both contributing to significantly faster search times. In contrast, ERCA* suffers from a more rigid dominance pruning strategy that attempts to eliminate dominated and infeasible labels both at generation time and again upon extraction from the queue. While early dominance checks can help reduce queue size, they add computational overhead when applied to non-dominated labels. Furthermore, rechecking resource feasibility after extraction is redundant, as resource limits remain unchanged throughout the search, resulting in wasted computation and reduced efficiency.

Figure 2 (Right) also shows the number of solved cases for each algorithm, sorted by runtime, on the COL map with three resources. We observe that both variants of NWRCA* solve 60% of instances within 50 seconds, whereas ERCA* and RCBDA* require above 17 minutes to achieve the same success rate. In summary, both variants of NWRCA* demonstrate significantly faster performance than the state of the art in terms of computation time, with NWRCA*_v1 being approximately twice as fast as NWRCA*_v2.

No performance comparison was provided between ERCA* and RCBDA* by the authors of ERCA*. Our results show that, while the improved RCBDA* algorithm solves more instances and achieves better average runtimes than ERCA* on certain maps, it does not consistently outperform ERCA*. The strong performance of RCBDA* in many instances is due to its bidirectional framework, which combines perimeter and alternating search strategies. In terms of worst-case runtime performance (Figure 2 (Left)), ERCA* generally performs better than RCBDA* but tends to be consistently around two orders of magnitude slower than NWRCA*_v1, whereas RCBDA* can be over three orders of magnitude slower than NWRCA*_v1 in some cases.