A* algorithm

 https://ja.wikipedia.org/wiki/A*

が詳しいです。推定値があるときのダイカクストラアルゴリズムの一般形で、これより速いアルゴリズムは知られていないと思います。問題は、これに制約が加わったRCSPP(Resource Constraint Shortest Path Problem)であり、NP完全な問題になることが知られています。前述のアイデアは、このA*アルゴリズムの一種です。このベンチマークについては、よく知らないのですが、とりあえず、まとまった後の話ですが、NSP問題中に現れる問題をMPS形式にして、MIPソルバーとの比較で速度比較してみたいと思います。

多分、現在でも、コンパイル可能なものについては、スケジュールナースのそれが、Gurobi/Cplexよりも速く最速な筈です。コンパイルが出来ていないものも、前述したアイデアにより、コンパイル可能となり、やはり最速になる予定です。これは、問題構造を良く分かっているからで、一般的に強い解法と、局所的に強い解法の違いであります。