私はここ数年ブレインストーミングをしている個人的な研究プロジェクトを始めようとしています。私は、最も早く場所を訪れるための最良の順序を見つけるためのグラフとアルゴリズムを知っています。しかし、私は自分の研究の次のステップで立ち往生していますが、この問題を解決できる研究論文/アルゴリズムはありますか？訪問する必要のあるいくつかの「ウェイポイント」がある開始点と終了点が与えられます。また、一部のウェイポイントには時間制限があります。たとえば、ウェイポイント3は午後4時までに到着する必要があります。そのため、アルゴリズムは最初に場所の時間制限（存在する場合）に基づいて場所を並べ替えてから、各ウェイポイントにアクセスするための最適な順序を見つける必要があります。
私は多くの異なるアルゴリズム/ヒューリスティックを調べ、このトピックに関する研究論文を検索しましたが、決定的なものは何も見つかりません。
よろしくお願いします。
そのようなことをしたことは一度もありませんが... BlueRajaがすでにあなたに伝えたことを詳しく説明すると、おそらくあなたはすでに聖杯を見つけたと言わざるを得ません（そして、おそらく、あなたはそれに気付いていないだけです）。
あなたが解決しようとしている時間関連の問題は、グラフを移動するために既に解決しなければならなかったのと同じ空間関連のパス検索問題を言い換える別の方法のように見えます。
つまり、トラバースするグラフが2 つあるように見えます。1 つ目は空間的なもので、訪問する必要がある一連のウェイポイントで表されます。2 つ目は、バス、電車、船、飛行機などに乗り遅れないようにするために必要な「タイム ウィンドウ」の一時的な(別名「時間関連」) グラフです。
私が見る限り、通常のパス検索/グラフ交差アルゴリズム (ダイクストラ、A*、縮約階層など) を使用して、空間グラフを走査し、同じアルゴリズム (または非常に類似したアルゴリズム)を再利用できます。 ) 時間関連のグラフもトラバースします。
結局のところ、両方のグラフは「制約」のネット (空間または時間で通過するポイント) の単なる数学的表現であり、同じアルゴリズムを使用して通過できます。おそらく、「タイム ウィンドウ」を整理するために使用しているコードを見ると、非常に単純な空間関連のグラフ トラバース アルゴリズムに非常によく似ていることがわかるでしょう。
主な問題は、時間グラフ (尊重しなければならない「時間ウィンドウ」のネット) の適切な表現を見つけることのようです。最も可能性が高いのは、時間制約のある空間ウェイポイント (空間ポイント、または「ドア」であり、それぞれに「タイム ウィンドウ」が付加されている) のグラフである必要があります。
いずれにせよ、1 回の操作で 2 つの問題を解決する方法はありません。まず、時間グラフ内のすべてのタイム ウィンドウを (必要な順序で) 接続する「最短パス」を見つける必要があります (つまり、既に行っているように、それらを整理する必要があります)。次に、空間グラフ内のタイム ウィンドウの任意のペア間の最短パスを見つける必要があります (そして、最短/最速パスが次のタイム ウィンドウを満たすのに十分速いかどうかを確認します)。