RCSPとは、

 Resource Constraint Shortest Path Problemの略です。問題をサブ問題に分割した時に、結局この形となるのがNSPの本質的なところです。

で、何が難しいかというと、この問題自体が、NP困難という問題分野に分類されます。しかも、

結論だけ先に言うと、はい、Resource‑Constrained Shortest Path（RCSP／RSCP）は一般に NP 困難（NP‑hard）です。しかも「最短路＋複数リソース制約」という構造のせいで、強 NP 困難（strongly NP‑hard）に分類されます。

最短路自体は P（多項式時間）で解ける → しかし「累積制約」が入った瞬間に NP-hard へジャンプする

これは RCSP の本質的な性質で、 どんなにグラフが単純でも、累計制約がある限り避けられません。

つまり、Cardinality　累計制約が入っただけで、途端に難しくなる、ということです。子問題が、強NP困難なら、当然子を含む問題NSPは、強NP困難ということになります。子だけでも難しいのにさらにもう一次元加わります。

インスタンス24の求解にこんなにも手間取っているのは、このシフト数32にプラス強烈なCardinality制約のおかげです。