巡回セールスマン問題

■ 概要

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

■ 問題点

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

■ ここでの解きかた

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

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

■ 準備

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

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

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

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

■ チュートリアル

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

ビューワを起動する

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

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

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

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

とりあえず適当に,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は以下の最適化を行う回数です.

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

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

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

  1. 経由地を2箇所,適当に選ぶ
  2. その2箇所の順番を入れ替える
  3. 入れ替えによって総距離が短くなるようなら,その入れ替えをした状態で1に戻る
  4. 短くならないなら順番を元に戻して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
良くはなっているようです.
しかしこれ以上はほとんど変化しなくなっています.
それでも経路を見たところ,あっちに行ってはまた同じほうに戻ってみたいなことを繰り返しているのはあまり変わっていません.
まだまだ無駄があって,最適な経路からはまだまだ遠そうです.

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

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

先ほどは「2箇所を入れ替える」というアルゴリズムでしたが,別のアルゴリズムを試してみましょう.
これは1箇所を抜き出して,別の位置に移動してみるというものです.それを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

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

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

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

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

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

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

収束させる

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

$ 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

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

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

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

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

ここから今までの4つのアルゴリズムを,乱数の種を変えてもう一度ひととおり試してみましょう.
今度は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

今度は乱数の種を2にして,シャッフルしてみます.

$ 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

ビューワの操作

経由値を増やす

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


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