Google MapでTSP問題(巡回セールスマン問題)を解決！複数地点を経由する最短ルート検索ツールの開発と活用方法

Google Mapはとても便利なツールで、旅先、あるいは仕事、遊びなど非常に幅広い用途がある。Google Mapsさえあれば何処へでも自由に行ける。ただし、スマホにダウンロードしたアプリやパソコンのブラウザで使うマップの機能に多少の違いはあるにしても、「こんな機能があったらいいのに」と思っている人は多い。そのうちの一つが「巡回セールスマン問題（TSP: Traveling Salesman Problem）」だ。場所を一度ずつ訪れて出発地点に戻る最短経路を求めるという問題だが、Google Mapにはその機能は無い。パソコン版グーグルマップでは10箇所の場所を指定してルートを求めることができるが、どんな順番で回れば最短距離で回れるのかは示してくれない。唯一考えられる方法が経由地の順番をいろいろと変えて試してみるという「総当たり法」を手作業で行うしかない。おまけに、この方法はパソコンのブラウザ版のGoogle Mapでしか使えない。スマホだと無理だ。

不忍池弁天堂、カヤバ珈琲、大平製パン、森鴎外記念館、夏目漱石旧居跡、根津神社楼門、Hagiso、菊寿堂いせ辰、夕焼けだんだん、以上9か所を回るルートを考える場合、回る順番はドラッグ＆ドロップで入れ替えることができるので、どの順番で回ると最短なのかはなんとなく検討がつく。

しかし、この方法は時間がかかるし、必ずしも正確とは限らない。総当たり法ですべての組み合わせを確認するわけにはいかない。膨大な時間がかかってしまい非効率的となる。

Google Cloud APIでGoogle Mapをカスタマイズして最短距離を瞬時に求める

以下の地図の任意の地点をクリックすると、地点リストが地図の上部に表示される。回りたい地点を何か所か(現状10箇所までに制限してある)クリックする。最初にクリックした地点が地図上部の地点リストで黄色で表示される。そして、ゴールにしたい地点をクリックするとブルーに変わる。そして「calculate route」をクリックすると最短ルートが表示される。

上記のGoogle Mapで使用されているAPIは、Maps Javascript APIとDirections API、Geolocation APIである。

巡回セールスマン問題の最短ルートをGoogle Cloud APIで求めた結果は？

さて、訪問したい場所をクリックしたら、地図上部のリストでゴールにしたい地点をクリックすると、青に変わるので、そのあと「Calculate Route」ボタンを押す。すると、

ブラウザ版Google Mapでルート検索した際にもなるべく最短になるように訪問地点の順番は考えていたので、結果的に訪問順に変わりはなかったが、根津神社から菊寿堂いせ辰へのルートの取り方で差が付いたようである。

複数地点を最短距離で回るGoogle Mapルート検索ツールの応用

巡回セールスマン問題では、十分にこのGoogle Cloud APIをつかったツールは使えるだろうが、ほかに応用できないだろうか？

ナビゲーションスポーツへの応用

ナビケーションスポーツには、大きく分けて3種目ある。

1.オリエンテーリング

2.ロゲイニング

3.タウントレッキング

１のオリエンテーリングは競技中のGPSやWEBマップの使用は禁止されているのだが、コース設定や、コースの試走には応用できそうだが、Google Mapの特性上、オリエンテーリングが行われる山間部には精度が不足しているため今後さらなるツールの改善が必要と思われる。実際にはオリエンテーリング用地図作成用のCADであるO-CADにはその機能があるようなので、それを使えばよいともいえる。

２のロゲイニングも競技中のスマホ地図などの使用は基本的に禁止だが、スマホの利用が認められている場合もある。たとえば「NAVI TABI」などを使ったロゲイニングだが、現在位置確認機能はオフにセットされている場合が多い。ただし、競技後のルート選択などの振り返りには十分使えるだろう。

3のタウントレッキングも地図と磁石を使った競技だが、タウンで行われるため利用は可能と考えらるが、主催者によってGPSの使用は禁止されていることも多いため、競技後の反省、「もっといいルートはなかったかな」とか、「どんな順番で回ればよかったのか」ということを考える助けにはなるであろう。

ウーバーイーツなど、配送系の仕事への応用

配送ルートが決まっている仕事の場合は別として、日ごとに配送ルートが変わる仕事、ウーバーイーツなどでは活用できると思われる。

日常生活のなかの散歩やハイキングへの応用

近隣といっても、まだまだ未知の場所が多いものである。そんな場所をGoogle Mapでピックアップしておいて、天気が良く、時間の余裕のある時に効率よく訪れてみようという時はとても最短距離検索ツールは役に立つ。