リソース制約を持つ最短パス

Question

私は有向非循環グラフを持っており、リソース制約をもった最短パスを見つける必要があります。私の制約は、選択されたパスが、消費されたセットリソースの最小数を持たなければならないということです。

現在、私はYen's K Shortest Path algorithmを使用してKの最短経路を計算し、次に自分の制約を満たすものだけを受け入れます。ここでの問題は、誤って選択されたように、実現可能なパスが見つからない可能性があるため、Kを推測することです。

私はこのトピックに関する多くの文献を見つけました。thisは私が考えている良い概観を提供しています。しかし、私はそれを理解して実装することができる簡潔なアルゴリズムを見つけるのには苦労しています（私はPythonを使用していますが、明確なアルゴリズム上のアイディアは素晴らしいでしょう）。

私はこの問題はNP-Completeであることを理解しています。そのため、私は良い近似アルゴリズムと正確なアプローチに興味があります。

誰でも良い推薦がありますか？あなたは何ができるか

Answer 1

は

• P(v)(V',E')にあなたのグラフ(V,E)を変換することで、元のノードの価格v
• Rが最大のリソースの使用です。
• E'((v,k),(w,l)) = E(v,w) and k+P(w)=l

V' = {(v,k) | v in V and k in [0..R]}

は、その後、あなたは (v0,P(v0))からダイクストラ検索を行います。 v1へのパスを見つけることができた場合、その距離の最短距離は (v1,k)頂点の中で最短になります。

明らかに、実際の展開グラフは作成しません。変更されたダイクストラでは、これまでの距離に加えて、これまでもリソースの使用を維持することができます。制限を超えていない場合は、パスをたどるだけです。 dist[v]の代わりに、正確にkのリソースを使用して、これまでのvへの最短パスを表すdist[v,k]を保持します。

リソースの境界が非常に大きい場合、これは潜在的に大きくなる可能性があります。したがって、NP完全性。しかし、リソースの境界が小さい場合、または10,100,1000に近い値に四捨五入しても構わない場合は、高速多項式時間で実行されます。 特に、一度停止する最適化を実装すると、使用可能な(v1,k)に達しました。

Answer 2

k-最短経路としてこの問題を解決するには、kを選択する方法がわからないという問題があります。

これは、ソースからノードvに到着するすべての異なるパスから潜在的にすべてのkの値に対してdist[v,k]を維持する必要があるという事実に苦しんでいます（アルゴリズムが非常に効率的ではありません）。

この問題を解決するための擬似多項式時間アルゴリズムがあります。これは、「リソース制約付き最短経路問題」（SPPRC）と呼ばれています。この問題は、Vehicle Routing Problems（VRP）とCrew Pairing Problems（運行上の問題で、主にOperations Researchで扱われています）によく現れます。 G. Desaulniers、J. Desrosiers、M. Solomon（eds）：Column Generation、Springer、1986）には、以下の（レビュー）論文が掲載されています：S. Irnich & G. Desaulniers、 "リソース制約の最短経路問題" 2005.

あなたはこの論文のタイトルをgoogleすることができます。無料でダウンロードすることができます。私は、あなたの問題には珍しい制約構造があると言及するべきです：つまり、あなたは、リソースの「過度に」過ごさないことを確実にする代わりに、リソースの少なくとも一定量を "費やす"必要があります。