巡回セールスマン問題

■ 概要

いわゆる巡回セールスマン問題を解くプログラムです．
こんな問題です．

行かなきゃならない場所が，多数ある
それらは１回，行けばいい
それらの場所を順番に行くとして，どういう順番で行けば最短で行けるか？という問題

■ 問題点

これは組み合わせ最適化問題というものなのですが，組み合わせ最適化問題には，以下のような課題があります．

行く場所が例えば４箇所あるとして，A地点，B地点，C地点，D地点とする．
これらの場所の最短の行きかた(経路)のパターンを，すべて網羅して調べるとするなら，以下のパターンで行くときの距離をすべて調べて，その中で最短のものを探せばいい．
- A→B→C→D，A→B→D→C，A→C→B→D，A→C→D→B，A→D→B→C，A→D→C→B
- B→A→C→D，B→A→D→C，B→C→A→D，B→C→D→A，B→D→A→C，B→D→C→A
- C→A→B→D，C→A→D→B，C→B→A→D，C→B→D→A，C→D→A→B，C→D→B→A
- D→A→B→C，D→A→C→B，D→B→A→C，D→B→C→A，D→C→A→B，D→C→B→A
つまり４箇所なら24通りのパターン．このパターン数を計算で出すなら，４×３×２×１通りのパターンということになる．
５箇所なら５×４×３×２×１通りのパターンで，120通りの調査が必要になる．
(ただ実際には反対の順番で行く場合等，同じ経路と言えるものもあったりするが，ここでは気にしないことにする)
これが100箇所とかになると，100×99×98×... となって，パターン数が爆発的に大きくなり，現実として調べることが不可能(コンピュータでも不可能)
しかし最適なパターン(最適解)を導こうとすると，すべてのパターンを網羅して調べなければならない．困ったなあ．

■ ここでの解きかた

そうした課題はあるのですが，以下のように条件を緩めることができれば，「簡単なプログラムで，ほどほどの時間で，ほどほどに良い解を得る」ということができます．

最短でなくても，ほどほどに良い経路が見つかればそれでいい
最も効率良く解けなくても(要するに時間がかかっても)，現実として許容できる時間内にそこそこに良い経路が見つけられればそれはそれでいい

ここでは以下の方法で，「簡単なプログラム」で「ほどほどに良い解」を「現実的な時間内」で解いてみます．

まず乱数で適当に経路を決める
その経路を部分的に修正する(順番を適当に入れ替える，など)
修正することで，経路の総距離が短くなるならその修正を反映して経路を新たにする．長くなるならその修正は却下する
それらを延々と繰り返す

■ 準備

まず，NLLをインストールしてください．
インストールの方法は以下を参照してください．

インストール

次に，以下のプログラムをひととおりダウンロードしてください．

プログラム

Windowsの場合は，NLLを解凍したディレクトリ(nll.exeがあるディレクトリ)にダウンロードしたプログラムを置いてください．

適当な地図の画像をダウンロードし，BMP形式にしておいてください．
(注意：地図画像のライセンスに留意してください)
(無い場合や面倒な場合は，上記からダウンロードできるmap.bmpを利用してください(ただの真っ白な画像です))

■ チュートリアル

Windowsの場合は，コマンドプロンプトを起動して「cd」コマンドでNLLのディレクトリに入り，実行してください．

ビューワを起動する

まず，適当な地図の画像を背景にして，ビューワを起動します．

$ nll -q view.nll position.dat map.bmp

背景にmap.bmpを利用した場合，ビューワはこのような真っ白の画面になります．

ビューワ上で追加したい場所(経由地)をマウスの左クリックで指定します．
クリックで指定した順番に，経由地を繋ぐとりあえずの経路が描かれます．
右クリックで，最も新しく指定した経由地を削除します．
経路は，スタート地点に戻ってくるように(つまり１周してくるように)なっています．

とりあえず適当に，30箇所くらいを指定するといいでしょう．

このようにして経由地を指定してもいいのですがここでは面倒なので，以下で乱数でランダムに100箇所を指定します．

$ nll -q makedata.nll position.dat 100 500 1

500は範囲，1は乱数の種です．

乱数の種が同じだと，同じパターンで乱数を発生します．
いろいろ変えて試す場合は，乱数の種を2や3のように別の値にしてください．

とりあえず，乱数で経路を作る

以下で，経由地の順番を適当にシャッフルします．

$ nll -q shuffle.nll position.dat 1 100

1はシャッフルするための，乱数の種です．
100はシャッフルする回数です．

この段階では，乱数で適当に経路を決めただけなので，かなり無駄な経路になっていると思います．
というより，ぐちゃぐちゃですね．

以下で，現時点での経路の総距離を計算します．

$ nll -q distance.nll position.dat
23760

経路を最適化してみる

以下で，経路を最適化していきます．

$ nll -q change.nll position.dat 1 10000

1は乱数の種，10000は以下の最適化を行う回数です．

これをやると，経路がどんどん最適化されていく様子がリアルタイムでビューワで見えます．

見た目にも，かなりすっきりしました．まだ無駄はありそうですが，とりあえず近いところどうしが繋がっているので，さっきよりはずっとマシそうです．

このときのアルゴリズムは，以下のようなものです．

経由地を２箇所，適当に選ぶ
その２箇所の順番を入れ替える
- 例えばA→B→C→D→Eのような順番のとき，BとDの２箇所を選んで入れ替えたなら，新しい順番はA→D→C→B→Eになる，という感じ
入れ替えによって総距離が短くなるようなら，その入れ替えをした状態で1に戻る
短くならないなら順番を元に戻して1に戻る

このように
「経由地の順番に，乱数で何らかの入れ替えをして，それによって総距離が短くならないか試してみる」
ということを繰り返して，より短い経路を少しずつ探っていきます．

総距離を計算してみましょう．

$ nll -q distance.nll position.dat
6835

だいぶ短くなりました．
しかしビューワの画像では，あっちに行ってはまた同じほうに戻ってみたいなことを繰り返しています．
一度行ったらその付近の経由地はぜんぶ行っておけ！っていう感じがします．
まだまだ無駄な経路があり，もっと最適化できそうです．

さらに最適化を進めてみる

乱数の種を変えて，もう少し最適化してみます．

$ nll -q change.nll position.dat 2 10000
$ nll -q change.nll position.dat 3 10000
$ nll -q change.nll position.dat 4 10000
$ nll -q change.nll position.dat 5 10000
$ nll -q change.nll position.dat 6 10000

やってみるとわかるのですが，だんだん変化が少なくなり，やがてはほとんど変化しなくなっていまいました．
総距離を見てみます．

$ nll -q distance.nll position.dat
5484

良くはなっているようです．
しかしこれ以上はほとんど変化しなくなっています．
それでも経路を見たところ，あっちに行ってはまた同じほうに戻ってみたいなことを繰り返しているのはあまり変わっていません．
まだまだ無駄があって，最適な経路からはまだまだ遠そうです．

別のアルゴリズムを試してみる

同じアルゴリズムでいくら試しても，これ以上は良くはならなさそうです．

先ほどは「２箇所を入れ替える」というアルゴリズムでしたが，別のアルゴリズムを試してみましょう．
これは１箇所を抜き出して，別の位置に移動してみるというものです．それを10000回繰り返します．

$ nll -q move.nll position.dat 1 10000

経路に変化がありました．効き目がありそうです．
乱数の種を変えながら，繰り返しやってみましょう．

$ nll -q move.nll position.dat 2 10000
$ nll -q move.nll position.dat 3 10000
$ nll -q move.nll position.dat 4 10000
$ nll -q move.nll position.dat 5 10000
$ nll -q move.nll position.dat 6 10000

さらに最適化が進みましたが，やはりこれ以上はほとんど変化しなくなりました．

まだまだ，別のアルゴリズムが必要そうです．

経路には，交差している部分がいくつもあります．ここはまだ最適化ができそうです．

交差しているということは，順番を反転させるようなことができれば，効果がありそうです．
そこで「２箇所の経由地を選んで，その間の経由地の順番をぜんぶ逆にする」というアルゴリズムを試してみましょう．

$ nll -q reverse.nll position.dat 1 10000
$ nll -q reverse.nll position.dat 2 10000
$ nll -q reverse.nll position.dat 3 10000

これは効果がありました．最適化が一気に進み，交差が無くなりました．

収束させる

これでもう一度「１箇所を別の位置に移動する」というアルゴリズムを試してみましょう．

$ nll -q move.nll position.dat 7 10000
$ nll -q move.nll position.dat 8 10000
$ nll -q move.nll position.dat 9 10000
$ nll -q move.nll position.dat 10 10000

多少は変化がありましたが，やはりほとんど変化しなくなりました．

「２箇所を選んで，その間の順番をひっくり返して別の位置に移動する」というアルゴリズムを試してみます．

$ nll -q rmove.nll position.dat 1 10000
$ nll -q rmove.nll position.dat 2 10000
$ nll -q rmove.nll position.dat 3 10000

さらに最適化が進みました．

ここから今までの４つのアルゴリズムを，乱数の種を変えてもう一度ひととおり試してみましょう．
今度は30000回ずつ試してみます．

$ nll -q change.nll position.dat 99 30000
$ nll -q move.nll position.dat 99 30000
$ nll -q reverse.nll position.dat 99 30000
$ nll -q rmove.nll position.dat 99 30000

しかし，変化はありませんでした．

乱数の種を変化させて試してもほとんど変化しませんので，ひとまずほぼ収束しているようです．

総距離を見てみましょう．

$ nll -q distance.nll position.dat
3584

初期経路を変えてみる

ある程度収束しましたが，別の収束した形があるかもしれません．

シャッフルしなおして，再度収束させてみましょう．
まず，データを再生成します．乱数の種を同じにすることで，同じデータが再生成できます．

$ nll -q makedata.nll position.dat 100 500 1

今度は乱数の種を２にして，シャッフルしてみます．

$ nll -q shuffle.nll position.dat 2 100

収束させていきます．

$ nll -q change.nll position.dat 1 60000
$ nll -q move.nll position.dat 1 60000
$ nll -q reverse.nll position.dat 1 30000
$ nll -q rmove.nll position.dat 1 80000

前回の経路と並べて見てみましょう．(左が今回，右が前回)

前回とは違った経路に収束しているように見えます．

$ nll -q distance.nll position.dat
3432

総距離はさっきよりも短くなっています．

もう一度，ひととおりのアルゴリズムを試しておきます．

$ nll -q change.nll position.dat 99 30000
$ nll -q move.nll position.dat 99 30000
$ nll -q reverse.nll position.dat 99 30000
$ nll -q rmove.nll position.dat 99 30000
$ nll -q distance.nll position.dat
3432

総距離に変化はありませんでした．ここでほぼ収束しているようです．

このように初期経路や最適化の順番を変えることで，違った経路に収束するようです．

最も，これはまだ収束しきっていないかもしれないし，そもそもこれが最短経路かどうかはわかりません． (それを調べるためには，すべての経路パターンを調べなければならない，ということになります)

しかしこのようにして，いくつかの初期経路で繰り返し収束させ，最も短い総距離の経路を選ぶことで (最適ではないかもしれないが)「ほどほどに良い解」を得ることができます．

ビューワはビューワ上で[q]を押すと終了します．

■ 応用

経由地を追加してみる

経由地を乱数で生成した場合や，経路の最適化後でも，ビューワで左/右クリックすることで，経由地の追加/削除が可能です．

またそのようにして修正したデータに対して，経路の最適化を再度行うこともできます．

経由地をいろいろ修正して，繰り返し試してみましょう．

その他の操作

最も近い経由地に行くというアルゴリズムで経路を作成 (最後のほうに無駄が大きくなる)

$ nll -q near.nll position.dat

スタート位置の移動(スタート位置は赤で表示されます)

$ nll -q up.nll position.dat
$ nll -q down.nll position.dat

全体の順番を反転

$ nll -q inv.nll position.dat

ビューワの操作

画像の保存
- ビューワ上で[s]を押すと，そのときの画像を「route.bmp」というファイル名で保存します．
  経路のベスト５などを作って印刷し，最適経路を当てるクイズなどができます．
  (注意：地図画像を用いている場合は，ライセンスに留意してください)
線や色の調整
- 以下のキー操作ができます．
  - [o][l] ... 線の太さの調整
  - [i][k] ... ×印の太さの調整
  - [u][j] ... ×印の大きさの調整
  - [y][h] ... 色の数の調整

経由値を増やす

以下はメロンではなく，経由値を1000にして収束させてみたものです．
さすがにこの数になると収束に時間はかかりますが，それなりに良い経路が見つけられている…ように思います．

メールは kozos(アットマーク)kozos.jp まで