optimization - 粒子群の最適化

Question

PSO アルゴリズムを使用してトラフィックの問題を解決する方法について質問があります。n 台の車両 (ここでは 4 台の車両に限定) があると仮定すると、これらの車両には同じ目的地があります。出発都市が異なります (位置 (x,y) がわかっているとします) D: 出発都市と目的地の間の距離。d: ガスがなくなるまでに移動できる最大距離。D >> d : 各車両は、N=D/d で N 回燃料を補給する必要があります。すべての車両がたどるべき経路は定義されていません。タスク: すべての車両が故障しないように、最小限の数のガソリン スタンドを探しています (もちろんガソリンのためです)。ガソリンスタンドの数とその場所。

Answer 1

これは、標準のダイクストラ検索アルゴリズムを少し拡張するだけで解決できると思います。

まず、開始点をハードコードされた場所に設定します。いつものように Dijkstra 検索を行います。遭遇したガソリン スタンドをメモしておきますが、ここでは多少無視します。ガスを止めずに目的地に到達しようとしますが、ガスが不足する可能性のあるすべてのノードの検索をキャンセルします。ガソリンを切らさずに目的地に到着した場合、それが最短経路であり、ガソリンスタンドは必要ありません。

ただし、ガソリンがなくなった場合は、以前の検索で見つけたガソリン スタンドに開始点 (および開始距離) を設定してください。これで、複数の潜在的な開始点が得られます。そして、それが繰り返されるだけです。再び目的地にたどり着けない場合は、前回の検索で見つけたすべてのガソリン スタンドから検索します。

前のクエリのすべての出発点から目的地に到達するまで、これを続けます。距離を集計し、最短経路を選択します。

これで、ガソリンスタンドがなくなって最終目的地にたどり着けないステージに到達した場合、ガスを切らなければ最終目的地にたどり着くことができなくなります。