トップページ > ダウンロード > 巡回セールスマン問題

巡回セールスマン問題・マルチ巡回セールスマン問題(TSP、MTSP)

1.概要

◆機能概要
  巡回セールスマン問題(Traveling Salesman Problem)および複数巡回セールスマン問題(Multiple
     Traveling Salesman Problem)を遺伝的アルゴリズム(genetic algorithm、略称:GA)を用いて解く。
     TSPLIB形式のファイルおよび、VRPLIB形式のファイルを読み込み、最短巡回経路、および
     複数人での最短巡回経路を出力する。
     ただし、VRPファイルにある負荷(Capacity)の考慮は行わない。(VRP問題(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ファイルは、サンプル書式を参考に作成してください。

 
◆アルゴリズム概要
   TSP:GAを用い、巡回セールスマン問題を解いています。適応度が大きくなる(総距離の短くなる)
         ルートを探します。
         GAの交差オペレータは、7種類用意されています。
         ( 0:ノーマル 1:順序型 2:位置型 3:部分写像型 4:循環型 6:辺再組合せ型 9:SeqConstruct型 )
         最良解を求めるため、GAで求めた解について、LS( 交換、並べ替え)を行っています。

   MTSP:VRP用のデータのトラック数をセールスマンの人数としてMTSPを解いています。
         適応度は、各ルートの最大値が短いほど大きく、加えて総距離が短いほど大きくなっています。
         TYPEがVRPまたはCVRPの時は、入力のトラック数分の拠点を追加し、その点と他拠点との
         距離を0と入力されたとして解いています。
         TYPEがMTSPの時は、TSPで求めたルート(1人セールスマン問題の解)を
         人数(トラック数)に分け、その各ルートについて再度GA、LSを行い、最短のルート
         を求めています。

2.入力ファイル形式

    @TSPLIB VRPLIBファイル
      TSPLIBにあるデータ、VRPLIBにあるデータがほぼそのまま使えます。
      (LIBにある全データについてテストしたわけではないので、以下の例および添付のファイルを参考にしてください)
    
     例)TSPファイルの例 berlin52.tsp
     --------------------------------------------------------
     NAME: berlin52
     TYPE: TSP                   ・・・TSPタイプ
     COMMENT: 52 locations in Berlin (Groetschel)               
     DIMENSION: 52                 ・・・拠点数
     EDGE_WEIGHT_TYPE: EUC_2D        ・・・2次元ユークリッド距離
     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) ・・・トラック数=8
     TYPE : CVRP                               ・・・CVRPタイプ
     DIMENSION : 22                              ・・・拠点数
     EDGE_WEIGHT_TYPE : EUC_2D                    ・・・2次元ユークリッド距離
     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"に変更すると、TSPを実行した後に人数(トラック数)でルート分割し、
     再GAを実行して最大ルート長が 最小になるルートを探します。
     自分で作成するときは、COMMENT行のtrucks:の後の数値が分割数になりますので、要注意です。
    
    Aopttourファイル、optファイル
      TSPLIBにあるデータ、VRPLIBにあるデータがほぼそのまま使えます。
     例)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
     --------------------------------------------------------
    
    BGA(遺伝的アルゴリズム)パラメータファイル
      添付のga1_def.txtファイルの中に簡単な説明があります。
      そちらをご覧ください。  
      パラメータを変えると、結果が変わります。

3.出力ファイル

    (1)ルートファイル
       ****rout_0.csv ・・・opttourファイルおよびoptファイルのルートファイル(解答ルートファイル)
       ****rout_3.csv ・・・今回の計算で求められたルートファイル
       ルートファイルをエクセルで立ち上げ、座標の数値をすべて選び、挿入→散布図(直線とマーカー)
       を選択すると今回のルートが散布図で表示されます。





    (2)結果ファイル・・・今回の実行パラメータと結果、optファイルとの差異を出力しています。
    (3)ログファイル・・・今回実行のログです。

4.使用方法

◆ダウンロード(ダウンロードのページからもダウンロードできます)
  
      sample09.zip     115 KB (117,983 バイト)  
      sample09.lzh     117 KB (120,285 バイト)  

    3.1 インストール

     (1)ダウンロードしたファイルを、任意のディレクトリに解凍します。 下記ファイルが解凍されます。
    
        (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-n22-k8.vrp
        (k)P-n22-k8.opt
        (l)P-n100-k4.vrp
        (m)P-n100-k4.tsp
        (n)P-n100-k4.opt
    
    3.2 アンインストール
    
     (1)インストール時に作成したディレクトリごとファイルを削除します。
    
    3.3 起動方法
     2016/12/31 まで実行できます。
    
      run.bat または コマンドラインでパラメータ付きでTSP_GA.exeを実行させて下さい。

5.開発環境

Microsoft Visual Studio 2008 C++

6.その他の機能

    現在、交差の種類を以下の6種類用意していますが、どの交差がターゲットの問題に適しているか
    テストすることができます。
     1:順序型交差
     2:位置型交差
     3:部分写像型
     4: 循環型
     6:辺再組合せ型
     9:SeqConstruct

   各交差について5回、またループ回数も変えて計測した適応度の表が出ます。
   以下は、berlin52.tspについて実行した結果と、その結果をエクセルのグラフで表示したものです。
   ループ回数を10000回にすると、解答ファイルの値と一致する結果になるものもありました。
   このテストをされてみたい方はメールでお問い合わせください。




Copyright 2011 Sogen System Co.,Ltd. All Rights Reserved.