ExcelとGoogle Mapsで巡回セールスマン問題をやってみる(TSPソルバー)


地図上にランダムに置かれた地点を最短距離(距離のコストが最小)の一筆書きで結んでみようというものです。直線で結ぶので実際とは合わないかもしれませんが目安にはなるでしょう。

Earthで見るとこういう感じ。

tsp-6


Excelブックのダウンロード

このTSPソルバーはVBAで実装しているのでそこそこ速い………はず(^^)。

このブックには2つのシートがあります。

latlngシート

tsp-1

attributeシート

ここではTSPルートの線の属性を変えられます。

文字の色が線の色になります。

tsp-2

attributeシートからlatlngシートに戻る場合

latlngシート保護になっていたら解除してください。

tsp-3

地図上をクリックして位置情報などを取得してデータをセットします。

行を選択すると地図上にマーカーを表示。

tsp-4

メニュの「TSPソルバー」を使って巡回する順番を計算します。

tsp-5

KMLで保存すればEarthで表示できます。

TSPのウィンドウは閉じないでください。


ところで、巡回セールスマン問題の解を求めるのにこういうやり方もあります。

粘菌に学ぶ。

モジホコリ

 


 

2 Comments on ExcelとGoogle Mapsで巡回セールスマン問題をやってみる(TSPソルバー)

  1. スクリプトエラーという表示が出て、マップが表示されないのですが、
    どのようにすれば利用できるようになるのでしょうか?

    • Google Mapsではいろいろな部分が有償化されてきています。WisteriaHillは何とか「安く、あるいはタダで」あげる必要があるのですが、対応が間に合っていないところがあります。
      ご不便をおかけしておりますが、今しばらくお待ちくださいませ。

Leave a Reply

Your email address will not be published.


*