問題タブ [traveling-salesman]

いくつかの異なる巡回セールスマンプロジェクトがあることは知っていますし、 LKHで少し遊んだこともありますが、他のプロジェクトについて何か推奨事項があるかどうか疑問に思っていました。

私のプロジェクトは GPL であるため、そのライセンスと互換性のあるものが必要です。

私は大学で NP 完全性の文脈で TSP を学びました。実際の問題に適用される状況は実際にはありませんでした。少しの調査によると、ドリルを移動するための最も安価な経路、つまり回路基板に穴をあける方法を選択するために使用されていることが示されています。それは私が見つけることができたほとんどすべてです。

使っていますか？TSA には他にどのような実用的なアプリケーションがありますか?

Google Maps API を使用して、一連のウェイポイントを指定して「最適化された」ルートを取得する方法はありますか (つまり、巡回セールスマンの問題に対する「十分な」解決策)、または常にルートを返す方法はありますか?指定された順序でポイントしますか?

ここ数日、遺伝的アルゴリズムを使用した TS ソリューションを紹介しているいくつかのWeb サイトに注目しました。

TSP 問題で、最も短いツアーを生成するアプローチはどれですか?最近傍または遺伝的アルゴリズム?

これは、巡回セールスマンの最適化問題とハミルトニアン パスまたはサイクル決定問題のヒューリスティックを実装するように求められたプロジェクトです。実装自体に支援は必要ありませんが、今後の方向性について質問があります。

私はすでに、遺伝的アルゴリズムに基づく TSP ヒューリスティックを持っています。これは、完全なグラフを想定し、母集団として一連のランダムな解から開始し、世代数にわたって母集団を改善するように機能します。ハミルトニアン パスまたはサイクルの問題を解くためにも使用できますか? 最短経路を取得するように最適化する代わりに、経路があるかどうかを確認したいだけです。

これで、完全なグラフにはハミルトニアン パスが含まれるため、TSP ヒューリスティックを任意のグラフに拡張する必要があります。これは、2 つの都市の間にパスがない場合にエッジを無限値に設定し、有効なハミルトニアン パスである最初のパスを返すことで実行できます。

それはそれにアプローチする正しい方法ですか？または、ハミルトン パスに別のヒューリスティックを使用する必要がありますか? 私の主な関心事は、TSP 最適化が機能することをある程度確信できるため (ソリューションから始めてそれらを改善するため)、それが実行可能なアプローチであるかどうかです。

最善のアプローチは自分でテストすることだと思いますが、時間に制約があるため、このルートをたどる前に尋ねると思いました...（代わりに、ハミルトンパスの別のヒューリスティックを見つけることができました）

複数回の訪問でTSPの分枝限定法について話し合うことを検討しています（つまり、すべての都市を1回だけではなく、少なくとも1回訪問する必要があります）

編集：

Jitseが指摘したように、関連性がなかったため、疑いを取り除きました。これで、質問はより明確になります。

強く接続された有向グラフがあります（つまり、グラフGのノード（i、j）の各ペアに対してiからjおよびjからiへのパスがあります）。このグラフから、すべてのエッジの合計が最小になるように、強く接続されたグラフを見つけたいと思います。

別の言い方をすれば、エッジを削除した後でもグラフが強力に接続され、エッジの合計のコストが最小になるように、エッジを削除する必要があります。

NP困難な問題だと思います。20ノードのような小さなデータセットに対して、近似ではなく最適なソリューションを探しています。

編集

より一般的な説明：グラフG（V、E）が与えられた場合、Gにv1からv2へのパスが存在する場合、Gにv1とv2の間にパスが存在するように、グラフG'（V、E'）を見つけます。 'およびE'の各eiの合計は可能な限り最小です。したがって、最小の同等のグラフを見つけるのと似ていますが、ここでのみ、エッジの合計ではなく、エッジの重みの合計を最小化します。

編集：

これまでの私のアプローチ：複数回の訪問でTSPを使用して解決することを考えましたが、正しくありません。ここでの私の目標は、各都市をカバーすることですが、最小コストのパスを使用します。ですから、それはカバーセット問題のようなものだと思いますが、正確にはわかりません。総費用が最小の小道を使ってすべての都市をカバーする必要があるので、すでに訪れた小道を何度も訪れても費用は増えません。

遺伝的アルゴリズムで巡回セールスマン問題（TSP）を解決しようとしています。私のゲノムは、グラフ内の頂点の順列です（セールスマンのパス）。

ゲノムに対してクロスオーバー操作をどのように実行する必要がありますか？

問題の実装はC＃のどこにありますか？

(a) と (b) では、2 交換変換演算子を想定して、パス表現で TSP ツアーである解 A と B を、ツアー C、D、E、F、G の中の可能な隣接に接続します。

これが私に何を求めているのか、私にはわかりません。

分岐限定アルゴリズムで TSP を解決しようとしています。

コストを含むマトリックスを作成する必要がありますが、この問題があります。座標 x と y を持つ都市があります。

旅費はceil(ceil(sqrt((x1-x2)^2+(y1-y2)^2))/v)+ 市内滞在日数です。Vは速度です。

都市で過ごす日は、w が都市に来る日によって異なります。たとえば、月曜日(t1)に都市 1 に到着した場合、9 日間滞在しますが、火曜日に到着した場合、都市に 4 日間滞在します。

分岐限定アルゴリズムを使用してこの問題を解決するにはどうすればよいですか?