TSP_Solver　Ver. 2.11 リリースノート　　　　　　　　　　      　1996年9月1日
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　     東京商船大学
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　     久保　幹雄
このファイルには  TSP_Solver Ver. 2.11 の情報を記述しています。
ご使用の前に必ずお読みください。

TSP_Solverについて
==================================
　　TSP_Solverは巡回セールスマン問題(Traveling Salesman Problem: 以下TSP)を解く
    ためのシステムです．もとはと言えば，TSPや組合せ最適化やメタ解法に関する
    講演をするときのデモ用として作成したもので，それを余暇の間に書き足しながら
    増殖させていったものです．
    個人の研究用に作成したものなので，操作にヘルプや暴走防止のガードもつけていません．
    
    中で用いられている各アルゴリズムの詳細および理論的背景については，朝倉書店から出版された「巡回セールスマン問題への招待」
    (山本芳嗣氏との共著) およびそこにある参考文献をご参照下さい．

操作方法
==================================
   - Fileメニューを開いて，データを作成(Random Data)またはTSPLIB形式
    のデータを読む(Load TSPLIB Data)．
    (Matrix形式のデータは読めません.これらの問題は，画面表示もできず，
    また規模が小さくてつまらないので実験の対象外にしています．)
    TSPLIBによって提供されている最適巡回路は，Load Tourで読み込むことが
    できます．また，得られた巡回路およびデータも保存，読み込みができます．
   - Constructメニューを開いて巡回路を作る．
   - Improveメニューを開いて巡回路を改善する．
    注意: Simulated AnnealingおよびLSM (Life Span Method) は非常の長い時間を要するので
    大規模な問題での実行は避けてください．
   - Parameterメニューでは，Simulated Annealing, LSMのパラメータおよび
     Serpentine Rack, Spiral Rack, Sinuous Rackなどのバケット法における
     パラメータを調節できます．パラメータの意味については，関連する論文
     をご参照ください．
   - Lower Boundメニューは， TSPの下界を算出するためのルーチンです．Held & Karpの
     下界算出法(最小一木に基づくラグランジュ双対法)は，スパースなグラフ上でPrimの
     最小木を解くことによるものですので，スパーシティを決めるパラメータ(m)が十分に
     大きくないときには正確な下界にならない場合があります．まあ，解の精度に関する
     目安と考えて下さい．
   - Experimentメニューは，バケット法のパラメータを決めるための実験や，Nearest Neighbor
     法による初期解の影響，Iterated Local Searchなどの実験を自動的に行います．
   - Postscriptメニューでは，得られた巡回路をPostscript Fileに出力します．
    「巡回セールスマン問題への招待」にある図の多くは，この機能によって作られたものです．
 
基本パラメータ
====================
    n: 都市(点)数.
    m: 保管している近接点の数. 一般に，mを小さくすると高速になるが，解の精度は
       悪化します．nが大きくなるとメモリの上限値に達さないように，自動的にmの
       値を小さくします．また，nが3500を超える場合は，Spacefilling Curve,
       Serpentine Rack, Spiral Rack, Sinuous Rack法以外の解法は推奨できません．

TSPLIBについて
==================================
TSPLIB はGerhard Reineltによって収集された巡回セールスマン問題のベンチマーク問題集です．
TSP Solverでは数個のデータのみ収めてあります．
より多くの問題を入手されたい方は，以下の場所からインターネットを利用して入手可能です．
 
http://www.iwr.uni-heidelberg.de/iwr/comopt/soft/TSPLIB95/TSPLIB.html

-- elib at ZIB Berlin (data collection MP_TESTDATA)
  http://www.zib-berlin.de/\\
  Datext-P: +45050939033 (WIN)  +2043623939033 (IXI)
  Internet: telnet elib.zib-berlin.de (130.73.108.11)
          rlogin elib.zib-berlin.de (130.73.108.11) (userid: elib)
          gopher elib.zib-berlin.de (130.73.108.11)
  Anonymous ftp: elib.zib-berlin.de (130.73.108.11)

-- Rice University Houston
  gopher://softlib.rice.edu/11/softlib/tsplib

ユーザーサポート
===================================
　　連絡先
　　　　　東京商船大学　久保研究室
          e-mail kubo@ipc.tosho-u.ac.jp 

TSP_Solver セットアップ
============================
  TSP_Solverは Microsft Windows 95 もしくは NT 3.51 以上のバージョンで稼動します．
  配布ディスクの setup を起動することによって自動的にハイドディスク上にインストールされます． 
  
以上、TSP_Solverをお楽しみください。