数週間前、私は、巡回セールスマン問題のバリエーションに事実上分解した問題に遭遇しました。ねじれは次のとおりです。
複数の売り子がいます。都市のリストは動的に増加します (ライブ入力のように) 各都市は限られた時間だけ完全に利益を上げます.一定時間後に都市が返す報酬が少なくなります.全体的な時間制限があります.
明らかに、この問題は NP です。この問題に適合するように修正できる、適切な TSP 近似があるかどうか疑問に思っていました。
質問する
208 次
1 に答える
2
Coin-ORなど、いくつかのオペレーションズ リサーチ ソフトウェアを使用して問題を解決できる場合があります。その理由は、OR 制約/線形/整数/その他のプログラミング ソルバーに新しい制約/目的を追加する方が、特殊なソルバーなどよりも一般的に簡単だからです。 C や Fortran などで書かれた TSP ソルバー (正確な問題を解決するための C/Fortran コードが見つかる可能性は低いです)。 これは、Coin-OR を使用して基本的な TSP を解決するためにタブー検索をコーディングする方法に関するチュートリアルです。さらに、時間依存の TSP のモデル化に関する記事はこちら(この記事では分枝限定法を使用して問題を解決していますが、これはおそらく 100 都市程度を超えて拡張できないため、問題には適切ではありませんが、モデルは Coin-OR のような近似ソルバーに引き継ぐ必要があります) .
複数のセールスマンがいることを説明するために、グラフ分割を調べて、さまざまなセールスマン間で都市を分割することをお勧めします。たとえば、高速なオンライン グラフ分割アルゴリズムを次に示します。利点は、グラフを分割すると、異なるセールスマン間の同期を削減または排除できることです。
于 2013-07-08T17:52:46.003 に答える