既知のグローバルオプティムを備えた巡回セールスマンの例

Question

PythonでMemetic Algorithmを作成しました 旅行セールスマンの問題。ただし、私が遭遇したすべてのテストデータ（都市間の距離のリスト）が最適なソリューションの情報がないため、アルゴリズムがグローバルにどれだけ近いかを知ることはできません。

TSPテストデータ（できればマトリックス形式で、何でも良いこと）を見つけることができる場所を知っている人はいますか？

Answer 1

グーグルしましたか？

http://www.tsp.gatech.edu/data/index.html

そのページには、16が最適なソリューションがあるいくつかのテストケースを提供します。

Answer 2

おそらくあなたはあなた自身のテストデータを生成することができますか？

これは間違いなく包括的なテストではありませんが、役立つかもしれません。注：以下はハミルトニアンパスに関するものであり、サイクルを探している場合、同様のものが機能します。

以下を行うことができます。

Nノードを使用した無向グラフGが与えられているとします。

これで、Gのエッジの重量を1に設定し、Gではないエッジを追加し、ランダムな重みを> 1にすることにより、加重グラフG 'を作成します。そのエッジ。

これで、G 'で有効なTSPアルゴリズムを実行し、サイズN-1のパスを生成すると、Gにはハミルトニアンパスがあります。それ以外の場合は、Gにはハミルトニアンパスがありません。

これで、グラフを使用できます 知る それはハミルトニアンの道を持っている/持っていない（例： ハイパーキューブ ハミルトニアンパスがあります）、TSPアルゴリズムのテストデータを生成します。

このページには、ハミルトニアンパスを持つグラフを生成するのに役立つ可能性のある十分な条件があります。 http://www-math.cudenver.edu/~wcherowi/courses/m4408/gtln12.html

ハミルトニアンパスの有無にかかわらず、グラフにデータを見つけるのに苦労することはないと思います。

それが役に立てば幸い。幸運を！

Answer 3

TSPLIBは、さまざまなソースおよびさまざまなタイプのTSP（および関連する問題）のサンプルインスタンスのライブラリです。

http://comopt.ifi.uni-heidelberg.de/software/tsplib95/