巡回セールスマン問題・マルチ巡回セールスマン問題(ＴＳＰ、ＭＴＳＰ)
１．概要
◆機能概要
巡回セールスマン問題（Traveling Salesman Problem)および複数巡回セールスマン問題（Multiple
Traveling Salesman Problem)を遺伝的アルゴリズム（genetic algorithm、略称：GA）を用いて解く。
TSPLIB形式のファイルおよび、VRPLIB形式のファイルを読み込み、最短巡回経路、および
複数人での最短巡回経路を出力する。
ただし、ＶＲＰファイルにある負荷（Capacity)の考慮は行わない。（ＶＲＰ問題（vehicle routing
problem、トラック配送問題）は行わない。）
◆起動引数
【TSPの実行時】
TSP_GA.exe TSPLIBﾌｧｲﾙ [TSPLIBopttourﾌｧｲﾙ]
・パラメータ定義ファイル（ga1_def.txt）が起動ﾃﾞｨﾚｸﾄﾘに必須です。
・TSPLIBファイルおよび、TSPLIBopttourﾌｧｲﾙは、サンプル書式を参考に作成してください。
【MTSPの実行時】
TSP_GA.exe VRPLIBﾌｧｲﾙ [VRPLIBoptﾌｧｲﾙ]
・パラメータ定義ファイル（ga1_def.txt）が起動ﾃﾞｨﾚｸﾄﾘに必須です。
・VRPLIBファイルおよび、VRPLIBoptﾌｧｲﾙは、サンプル書式を参考に作成してください。
◆アルゴリズム概要
ＴＳＰ：ＧＡを用い、巡回セールスマン問題を解いています。適応度が大きくなる（総距離の短くなる）
ルートを探します。
ＧＡの交差オペレータは、７種類用意されています。
（ 0:ノーマル 1:順序型 2:位置型 3:部分写像型 4:循環型 6:辺再組合せ型 9:SeqConstruct型 ）
最良解を求めるため、ＧＡで求めた解について、ＬＳ（ 交換、並べ替え）を行っています。
ＭＴＳＰ：ＶＲＰ用のデータのトラック数をセールスマンの人数としてＭＴＳＰを解いています。
適応度は、各ルートの最大値が短いほど大きく、加えて総距離が短いほど大きくなっています。
ＴＹＰＥがＶＲＰまたはＣＶＲＰの時は、入力のトラック数分の拠点を追加し、その点と他拠点との
距離を０と入力されたとして解いています。
ＴＹＰＥがＭＴＳＰの時は、ＴＳＰで求めたルート（１人セールスマン問題の解）を
人数（トラック数）に分け、その各ルートについて再度ＧＡ、ＬＳを行い、最短のルート
を求めています。
巡回セールスマン問題（Traveling Salesman Problem)および複数巡回セールスマン問題（Multiple
Traveling Salesman Problem)を遺伝的アルゴリズム（genetic algorithm、略称：GA）を用いて解く。
TSPLIB形式のファイルおよび、VRPLIB形式のファイルを読み込み、最短巡回経路、および
複数人での最短巡回経路を出力する。
ただし、ＶＲＰファイルにある負荷（Capacity)の考慮は行わない。（ＶＲＰ問題（vehicle routing
problem、トラック配送問題）は行わない。）
◆起動引数
【TSPの実行時】
TSP_GA.exe TSPLIBﾌｧｲﾙ [TSPLIBopttourﾌｧｲﾙ]
・パラメータ定義ファイル（ga1_def.txt）が起動ﾃﾞｨﾚｸﾄﾘに必須です。
・TSPLIBファイルおよび、TSPLIBopttourﾌｧｲﾙは、サンプル書式を参考に作成してください。
【MTSPの実行時】
TSP_GA.exe VRPLIBﾌｧｲﾙ [VRPLIBoptﾌｧｲﾙ]
・パラメータ定義ファイル（ga1_def.txt）が起動ﾃﾞｨﾚｸﾄﾘに必須です。
・VRPLIBファイルおよび、VRPLIBoptﾌｧｲﾙは、サンプル書式を参考に作成してください。
◆アルゴリズム概要
ＴＳＰ：ＧＡを用い、巡回セールスマン問題を解いています。適応度が大きくなる（総距離の短くなる）
ルートを探します。
ＧＡの交差オペレータは、７種類用意されています。
（ 0:ノーマル 1:順序型 2:位置型 3:部分写像型 4:循環型 6:辺再組合せ型 9:SeqConstruct型 ）
最良解を求めるため、ＧＡで求めた解について、ＬＳ（ 交換、並べ替え）を行っています。
ＭＴＳＰ：ＶＲＰ用のデータのトラック数をセールスマンの人数としてＭＴＳＰを解いています。
適応度は、各ルートの最大値が短いほど大きく、加えて総距離が短いほど大きくなっています。
ＴＹＰＥがＶＲＰまたはＣＶＲＰの時は、入力のトラック数分の拠点を追加し、その点と他拠点との
距離を０と入力されたとして解いています。
ＴＹＰＥがＭＴＳＰの時は、ＴＳＰで求めたルート（１人セールスマン問題の解）を
人数（トラック数）に分け、その各ルートについて再度ＧＡ、ＬＳを行い、最短のルート
を求めています。
２．入力ファイル形式
①TSPLIB VRPLIBファイル
ＴＳＰＬＩＢにあるデータ、ＶＲＰＬＩＢにあるデータがほぼそのまま使えます。
（ＬＩＢにある全データについてテストしたわけではないので、以下の例および添付のファイルを参考にしてください）
例）TSPファイルの例 berlin52.tsp
--------------------------------------------------------
NAME: berlin52
TYPE: TSP ・・・ＴＳＰタイプ
COMMENT: 52 locations in Berlin (Groetschel)
DIMENSION: 52 ・・・拠点数
EDGE_WEIGHT_TYPE: EUC_2D ・・・２次元ユークリッド距離
NODE_COORD_SECTION
1 565.0 575.0 ・・・拠点の座標
2 25.0 185.0
3 345.0 750.0
4 945.0 685.0
5 845.0 655.0
・・・
52 1740.0 245.0
EOF
--------------------------------------------------------
例）VRPファイルの例 P-n22-k8.vrp
--------------------------------------------------------
NAME : P-n22-k8
COMMENT : (Augerat et al, No of trucks: 8, Optimal value: 603) ・・・トラック数＝８
TYPE : CVRP ・・・ＣＶＲＰタイプ
DIMENSION : 22 ・・・拠点数
EDGE_WEIGHT_TYPE : EUC_2D ・・・２次元ユークリッド距離
CAPACITY : 3000
NODE_COORD_SECTION
1 145 215 ・・・拠点の座標
2 151 264
3 159 261
・・・
22 139 182
DEMAND_SECTION
1 0
・・・・
22 700
DEPOT_SECTION
1
-1
EOF
--------------------------------------------------------
（DEMAND_SECTION以下はなくて構いません。 負荷計算は行っていません。）
TYPEの"CVRP"を"MTSP"に変更すると、ＴＳＰを実行した後に人数（トラック数）でルート分割し、
再ＧＡを実行して最大ルート長が 最小になるルートを探します。
自分で作成するときは、COMMENT行のtrucks:の後の数値が分割数になりますので、要注意です。
②opttourファイル、optファイル
ＴＳＰＬＩＢにあるデータ、ＶＲＰＬＩＢにあるデータがほぼそのまま使えます。
例）TSPopttourファイルの例 berlin52.opt.tour
--------------------------------------------------------
NAME : berlin52.opt.tour
TYPE : TOUR
DIMENSION : 52
TOUR_SECTION
1 ・・・最短ルート（解）
49
32
45
・・・・
31
22
-1
EOF
--------------------------------------------------------
例）VRPoptファイルの例 P-n22-k8.opt
--------------------------------------------------------
Route #1: 19 ・・・各ルートの道順
Route #2: 21 17 12
Route #3: 18 20 14
・・・
Route #7: 9 2 1 6
Route #8: 7 5
cost 603
--------------------------------------------------------
③ＧＡ（遺伝的アルゴリズム）パラメータファイル
添付のga1_def.txtファイルの中に簡単な説明があります。
そちらをご覧ください。
パラメータを変えると、結果が変わります。
ＴＳＰＬＩＢにあるデータ、ＶＲＰＬＩＢにあるデータがほぼそのまま使えます。
（ＬＩＢにある全データについてテストしたわけではないので、以下の例および添付のファイルを参考にしてください）
例）TSPファイルの例 berlin52.tsp
--------------------------------------------------------
NAME: berlin52
TYPE: TSP ・・・ＴＳＰタイプ
COMMENT: 52 locations in Berlin (Groetschel)
DIMENSION: 52 ・・・拠点数
EDGE_WEIGHT_TYPE: EUC_2D ・・・２次元ユークリッド距離
NODE_COORD_SECTION
1 565.0 575.0 ・・・拠点の座標
2 25.0 185.0
3 345.0 750.0
4 945.0 685.0
5 845.0 655.0
・・・
52 1740.0 245.0
EOF
--------------------------------------------------------
例）VRPファイルの例 P-n22-k8.vrp
--------------------------------------------------------
NAME : P-n22-k8
COMMENT : (Augerat et al, No of trucks: 8, Optimal value: 603) ・・・トラック数＝８
TYPE : CVRP ・・・ＣＶＲＰタイプ
DIMENSION : 22 ・・・拠点数
EDGE_WEIGHT_TYPE : EUC_2D ・・・２次元ユークリッド距離
CAPACITY : 3000
NODE_COORD_SECTION
1 145 215 ・・・拠点の座標
2 151 264
3 159 261
・・・
22 139 182
DEMAND_SECTION
1 0
・・・・
22 700
DEPOT_SECTION
1
-1
EOF
--------------------------------------------------------
（DEMAND_SECTION以下はなくて構いません。 負荷計算は行っていません。）
TYPEの"CVRP"を"MTSP"に変更すると、ＴＳＰを実行した後に人数（トラック数）でルート分割し、
再ＧＡを実行して最大ルート長が 最小になるルートを探します。
自分で作成するときは、COMMENT行のtrucks:の後の数値が分割数になりますので、要注意です。
②opttourファイル、optファイル
ＴＳＰＬＩＢにあるデータ、ＶＲＰＬＩＢにあるデータがほぼそのまま使えます。
例）TSPopttourファイルの例 berlin52.opt.tour
--------------------------------------------------------
NAME : berlin52.opt.tour
TYPE : TOUR
DIMENSION : 52
TOUR_SECTION
1 ・・・最短ルート（解）
49
32
45
・・・・
31
22
-1
EOF
--------------------------------------------------------
例）VRPoptファイルの例 P-n22-k8.opt
--------------------------------------------------------
Route #1: 19 ・・・各ルートの道順
Route #2: 21 17 12
Route #3: 18 20 14
・・・
Route #7: 9 2 1 6
Route #8: 7 5
cost 603
--------------------------------------------------------
③ＧＡ（遺伝的アルゴリズム）パラメータファイル
添付のga1_def.txtファイルの中に簡単な説明があります。
そちらをご覧ください。
パラメータを変えると、結果が変わります。
３．出力ファイル
(1)ルートファイル
****rout_0.csv ・・・opttourファイルおよびoptファイルのルートファイル（解答ルートファイル）
****rout_3.csv ・・・今回の計算で求められたルートファイル
ルートファイルをエクセルで立ち上げ、座標の数値をすべて選び、挿入→散布図（直線とマーカー）
を選択すると今回のルートが散布図で表示されます。
(2)結果ファイル・・・今回の実行パラメータと結果、optファイルとの差異を出力しています。
(3)ログファイル・・・今回実行のログです。
****rout_0.csv ・・・opttourファイルおよびoptファイルのルートファイル（解答ルートファイル）
****rout_3.csv ・・・今回の計算で求められたルートファイル
ルートファイルをエクセルで立ち上げ、座標の数値をすべて選び、挿入→散布図（直線とマーカー）
を選択すると今回のルートが散布図で表示されます。
(2)結果ファイル・・・今回の実行パラメータと結果、optファイルとの差異を出力しています。
(3)ログファイル・・・今回実行のログです。
４．使用方法
◆ダウンロード（ダウンロードのページからもダウンロードできます）
sample09.zip 431 KB (441,953 バイト) ソース付き
４．１ インストール
(1)ダウンロードしたファイルを、任意のディレクトリに解凍します。 下記ファイルが解凍されます。
sample08フォルダの内容
(a)使用許諾契約書.txt
(b)TSP_GA.exe
(c)run.bat
(d)readme.txt
(e)ga1_def.txt
(f)berlin52.tsp ・・・以下サンプルファイル
(g)berlin52.opt.tour
(h)a280.tsp
(i)a280.opt.tour
(j)P-n23-k8.vrp
(k)P-n23-k8.opt
(l)P-n100-k4.vrp
(m)P-n100-k4.tsp
(n)P-n100-k4.opt
４．２ アンインストール
(1)インストール時に作成したディレクトリごとファイルを削除します。
４．３ 起動方法
run.bat または コマンドラインでパラメータ付きでTSP_GA.exeを実行させて下さい。
sample09.zip 431 KB (441,953 バイト) ソース付き
４．１ インストール
(1)ダウンロードしたファイルを、任意のディレクトリに解凍します。 下記ファイルが解凍されます。
sample08フォルダの内容
(a)使用許諾契約書.txt
(b)TSP_GA.exe
(c)run.bat
(d)readme.txt
(e)ga1_def.txt
(f)berlin52.tsp ・・・以下サンプルファイル
(g)berlin52.opt.tour
(h)a280.tsp
(i)a280.opt.tour
(j)P-n23-k8.vrp
(k)P-n23-k8.opt
(l)P-n100-k4.vrp
(m)P-n100-k4.tsp
(n)P-n100-k4.opt
４．２ アンインストール
(1)インストール時に作成したディレクトリごとファイルを削除します。
４．３ 起動方法
run.bat または コマンドラインでパラメータ付きでTSP_GA.exeを実行させて下さい。
５．開発環境
Microsoft Visual Studio 2005 C++
６．その他の機能
現在、交差の種類を以下の６種類用意していますが、どの交差がターゲットの問題に適しているか
テストすることができます。
1:順序型交差
2:位置型交差
3:部分写像型
4: 循環型
6:辺再組合せ型
9:SeqConstruct
各交差について５回、またループ回数も変えて計測した適応度の表が出ます。
以下は、berlin52.tspについて実行した結果と、その結果をエクセルのグラフで表示したものです。
ループ回数を10000回にすると、解答ファイルの値と一致する結果になるものもありました。
このテストをされてみたい方はメールでお問い合わせください。
テストすることができます。
1:順序型交差
2:位置型交差
3:部分写像型
4: 循環型
6:辺再組合せ型
9:SeqConstruct
各交差について５回、またループ回数も変えて計測した適応度の表が出ます。
以下は、berlin52.tspについて実行した結果と、その結果をエクセルのグラフで表示したものです。
ループ回数を10000回にすると、解答ファイルの値と一致する結果になるものもありました。
このテストをされてみたい方はメールでお問い合わせください。