基本的に、TSPLIB http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/tsp/からいくつかの対称 TSP データを取得し、最初に都市をクラスター化し、サブツアーを構築してパスを構築しようとしました。各クラスターを接続してから、クラスターを接続します。しかし、完全なツアーで得られた結果は、最適値と比較して非常に低いです. これは私が何か間違ったことをしたと信じさせますが、それは完全に私の頭の中にあり、なぜこれが起こっているのか分かりません.
これはデータ ファイル「Burma14」です。
1 16.47 96.10
2 16.47 94.44
3 20.09 92.54
4 22.39 93.37
5 25.23 97.24
6 22.00 96.05
7 20.47 97.02
8 17.20 96.29
9 16.30 97.38
10 14.05 98.12
11 16.53 97.38
12 21.52 95.59
13 19.41 97.13
14 20.09 94.55
このデータをファイルから読み取り、各ポイントの都市オブジェクトを生成します。
その後、個人をプロデュースします。これらは基本的に、利用可能な都市からランダムに作成されるサブパスです。City1 -> City2 などの 2 つの都市間の個人旅行。
次に、基本的に TSP のソリューションであるパスを作成します。
まず、クラスターは次のように生成されます。
1 cluster cities [City_3, City_4]
2 cluster cities [City_1, City_8, City_9, City_11, City_2, City_10]
3 cluster cities [City_5, City_6, City_12]
4 cluster cities [City_7, City_13, City_14]
次に、次のように、クラスターごとにサブツアーが作成されます。
SubTour: | [[City_4, City_3]] |
Cost: 2.445178930058085
SubTour: | [[City_10, City_9], [City_9, City_11], [City_11, City_8], [City_8, City_1], [City_1, City_2]] |
Cost: 6.29233886113867
SubTour: | [[City_12, City_6], [City_6, City_5]] |
Cost: 4.107068449867602
SubTour: | [[City_14, City_7], [City_7, City_13]] |
Cost: 3.5647520864865525
これらのサブツアーは、次のように接続されて完全なツアーを形成します。
Complete Tour: [| [[City_14, City_7], [City_7, City_13]] |, | [[City_12, City_6], [City_6, City_5]] |, | [[City_4, City_3]] |, | [[City_2, City_1], [City_1, City_8], [City_8, City_11], [City_11, City_9], [City_9, City_10]] |]
Complete Tour Cost: 34.92630477283413
これは、ユークリッド距離を計算する方法です。
public static double calculateDistance(double x1, double y1, double x2, double y2){
double xDistance = Math.abs(x1 - x2);
double yDistance = Math.abs(y1 - y2);
double distance = Math.sqrt( (xDistance*xDistance) + (yDistance*yDistance) );
return distance;
}
最適なコストが 34.92630477283413 である理由が本当に理解できませんが、このサイトhttp://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/STSP.htmlの burma14 の最適なコストは 3323 です。ulysses16 データセットを試しました（いくつかのWebサイトから）そして私はまだ同じ問題を抱えています。あらゆる種類のガイダンスの助けに本当に感謝しています。
ありがとうございました。