FIer: 投資でセミリタイアする九条日記

九条です。資産からの不労所得で経済的独立を手に入れ、自由な生き方を実現するセミリタイア、FIerを実現しました。米国株、優待クロス、クリプト、太陽光、オプションなどなどを行うインデックス投資家で、リバタリアン。ロジックとエビデンスを大事に、確率と不確実性を愛しています。

複数地点の最短巡回ルートをMapFanで検索する【巡回セールスマン問題】

 巡回セールスマン問題(TSP)という言葉を聞いたことはあるでしょうか。これは、「セールスマンがいくつかの都市を1度ずつすべて訪問して出発点に戻ってくるときに、移動距離が最小になる経路」を求める問題です。都市の数が増えると計算量が爆発的に増えるため、スーパーコンピューターでも簡単には解けなくなります。NP困難問題といわれたりもします。

 

こんな巡回セールスマン問題を、実際の地図の上で、最適ルートを表示してくれるサービスがあります。「MapFan」のマップツールです。

MapFan「マップツール」

MapFanはGoogleマップ全盛のいまとなってはかなりマイナーな地図サービスですが、インクリメントPという老舗の地図屋がやっているものです。パイオニアのカーナビの地図は同社が提供しているのが有名ですね。

 

この中の「マップツール」はMapFanのAPIを利用して提供されているサービスです。1つのマップに、最大30件を登録し、それを最短で回るルートを計算できます。下記のように、巡回したい場所を登録します。

f:id:kuzyo:20210309083855p:plain

次に、今回巡回したい場所にチェックを入れて、「訪問ルート作成」を押します。自宅から出発して自宅に帰ってくるので、「S」と「G」をそれぞれ自宅にします。

f:id:kuzyo:20210309084107p:plain

続いて、画面下の「ルート検索」を「最短で並び替え」がチェックされていることを確認して押します。

f:id:kuzyo:20210309084242j:plain

するとこの通り。巡回地点が自動的に並び替えられて、最短ルートを計算してくれます。計算にかかる時間は10秒程度。総所要時間、高速料金、総距離なども計算されます。今回だと、アクアラインを渡って先に千葉を周り、そこから東金道路、京葉道路を経て外環から常磐道で茨城に向かうというルートが引かれました。所要時間7時間55分、446キロに及ぶ大ルートです。

f:id:kuzyo:20210309084422p:plain

しかしこのサービスは、都内の店舗を効率よく回るために使うような用途が想定されているようで、あまりに移動距離が長くなるとエラーが出てしまいます。まぁ、500キロというのはクルマで巡回するにしても1日に回れる上限ではありますね。

f:id:kuzyo:20210308204949j:plain

都内のブックオフを巡ってみる

このツールの実力を見るには、都内で複数箇所を巡るルートを引かせてみたほうがわかりやすいですね。都内ブックオフ13店舗をランダムにピックアップしてみました。練馬の江古田店を出発して戻ってくるとして、どんなルートが最適でしょうか? これは頭で考えてもかなり難しいですね。

f:id:kuzyo:20210309085229j:plain

検索させてみると次の通りです。まず池袋に向かい、そこから下道で中野、そして新宿を回ってから東中野に戻ります。そこから板橋、赤羽、王子と南下して亀戸。首都高に乗って永福で降り、豪徳寺、烏山、そして環八で光が丘に寄って、江古田に戻るルートです。

f:id:kuzyo:20210309085408j:plain

こちら面白いことに、出発日時を夜の9時に変更すると、また少し違ったルートを引きます。渋滞情報なども一応加味しているということなのでしょうか。

巡回セールスマン問題

ちなみに、巡回セールスマン問題は巡回箇所が増えると、組み合わせの数が爆発的に増えることから難問と呼ばれています。今回のサービスのように、スタートとゴールが決まっていて、30箇所くらいならどうなるでしょうか? シンプルに力技で考えると、28の階乗になるので、パターンは304888344611713860501504000000通り。

f:id:kuzyo:20210310205232j:plain

このグラフは巡回地点の数と、その組み合わせ数の増え方のグラフです。注意点は縦軸が対数だということ。恐ろしい勢いで数が増加します。9の階乗は36万2880ですが、10の階乗はその10倍。12の階乗だと4億7900万通り。そこから爆発的に組み合わせが増加します。

 

28箇所でもこの数なので、何かうまくプラクティカルなアルゴリズムを用意しているのでしょう。スタート地点からの到達時間を最初に計算して、近いところと遠いところをグループ化する……なんてことが考えられますが、なかなかスゴイですね。

 

今回は、このサービスを使って、発電所の巡回ルートを作って行ってみました。本当は電車を使った巡回ルートも作成できれば、JR東のポケモンラリーなどにも応用できてよかったのですが。