一汁一菜 TOSY

沖縄には300を超えるキャッシュがあります。
このキャッシュをどう巡ると最も効率が良いのでしょうか?

これを解決する方法は「巡回セールスマン問題」、英語ではTSP(Traveling Salesman Problem)といって、本格的に研究している人たちがいます。プリント配線板の穴あけの最適化や物流の最適化といった分野で成果をあげているようです。

で、自分でもやってみようと思い、Excelでプログラムを作ってみました。
プログラムはこちらからダウンロードしてください。

複雑なことはできないので、2つの点を入れ替えたときに、全体のルートの距離が短くなるなら入れ替えるということだけでプログラムしました。
グラフでは、沖縄のキャッシュが点で、そのルートが線で見えています。縦軸は緯度、横軸は経度が度のラジアン表示になっています。

最初はこんなのが(全体の移動距離は7500km)、
(画像をクリックすると拡大します)


以下のように変化していきます。、






だんだんすっきりとしてきます。ここで全体の移動距離は2000kmを下回ります。

これはいい感じ。

と思っていたら、

この経路になってから、まったく距離が少なくなりませんでした。
Excelの乱数のせい? 2点の入れ替えしかしていないせい?

まだまだ、改良の余地がありそうです。
1ヶ月後の沖縄ツアーには間に合うのだろうか??