ポイントのセットがいくつかあり、「静的」としてマークされたポイントのサブセットがあります。そのため、TSP を解く必要があります。これにより、静的な位置にマークされたポイントを含む最適なパスが作成されます。どうすれば解決できますか？
私の問題は別の方法で解決できるかもしれません: ポイントには 2 つの主な特徴があります - お互いの距離と時間です。この物流タスクを解決する問題のクラスはありますか?
UPDわかりません。非静的ポイントの TSP を静的ポイントの TSP とマージするにはどうすればよいですか?
TSP には基本的に 3 つのアプローチがあります。
ブルート フォースの使用は、ノード数が少ない場合のオプションです。すべての(n-1)!順列を生成し、それらの長さを計算するだけです。問題に合わせて変更する必要があるのは、静的ポイントが割り当てられた場所にないものを除外するために可能なラウンドトリップを生成するアルゴリズムだけです。
ヒューリスティック (シミュレートされたアニーリングなど) を使用すると、はるかに大きな問題の TSP を計算できますが、完全なラウンドトリップは保証されません。これらは多くの場合、既存のソリューションを使用して、そこからランダムに異なるソリューション (または複数のソリューション) を導き出します。問題に合わせて、静的点が割り当てられた位置にあるという要件に違反する場合は、派生したソリューションを破棄します。
3 番目のバリアントは、多項式時間で往復するアルゴリズムを使用します。たとえば、最小スパニング ツリーに沿って歩いたり、一方向に掃引したり、それらを貪欲にトラバースしたりします。これらは良いタイミングを提供しますが、結果として得られるラウンドトリップの品質とのトレードオフになります。特定のポイントが特定の位置にあることを必要とするソリューションにこれらを適応させる方法が明確にわかりません。それらは単純であるため、これらの追加要件に簡単に適応することはできません。
私があなたの質問を正しく理解していれば、それはあなたの静的、非静的な場所と距離/時間マトリックスによって定義される単なる巡回セールスマンの問題です. オリジンの問題が非常に大きい場合は、オリジンの問題の TSP を最初に (そして 1 回だけ) 解決することが理にかなっている場合があります。生成されたソリューションは、「非静的」またはユーザー定義の場所を考慮して、新しい初期ソリューションを指定するために使用できます。たとえば、単純な最良の挿入だけです。次に、Lin-Kernighan ( http://en.wikipedia.org/wiki/Lin%E2%80%93Kernighan_heuristic )によって開発および適用された k-opt ヒューリスティックなどを使用して、この初期ソリューションを改善できます。
オリジンの問題が小さい場合は、別の TSP を解決してください (「静的な」場所と「静的でない」場所の両方を考慮してください)。