起源の異なるセールスマンのメンバーの旅行を計画してください

Question

私はこの問題を「相互乗り継ぎセールスマンの相互の問題」と言います。私は都市の異なる場所にいる人々のグループを持っています。彼らは特定のお店を見にツアーを計画したい。どうすればこの問題を解決できますか？ GAやACOなどのメタヒューリスティックアルゴリズムを使用するために問題をモデル化するにはどうすればよいですか？

Answer 1

私は次のように問題があると仮定します。

• 各ユーザーは、大きな地図から任意の都市のセットを見たい場合があります。

• 2人以上が

• 2人以上が同時に同じエッジを使用することができ、同時に同じ都市にすることができます。

遺伝的アルゴリズムの場合、各染色体は次のようになります。

人のためのルート1 | 人2のルート | 人のためのルート3 ..

生成の例は次のとおりです。

Chromosome1 = 2,6,7,1 | 4,7,2 | 3,5,6
Chromosome2 = 6,7,2,1 | 2,4,7 | 3,5,6

各ルートごとにクロスオーバー操作と突然変異操作を別々に適用する必要があります。パーミュテーション表現には、PMX（Partial-mapped Crossover）のようなクロスオーバ・メソッドを使用できます。ランダムスワップ、挿入、突然変異のスクランブルなどの操作を使用できます。

Ant Colony Optimizationでは、各Antは各反復ですべての人物のソリューションを構築する必要があります。また、人の経路ごとに異なるフェロモン値を保存する必要があります。たとえ彼らが共通の場所を持っていても（例えば、両方とも都市2と3を持っている）、それはこれらの都市間のエッジが同じ望ましさを持たなければならないということを意味しない（2と3の間のエッジは人1に適しているかもしれない。人に望ましくない2）。

だから、それぞれの人のルートを別々に見つけるのが最善だと思います。個人のルートごとにソリューション間で情報交換ができないためです。